Fib的奇怪定理 : gcd(F[n],F[m])=F[gcd(n,m)]

2018/12/16 15:03
阅读数 128

引理1:gcd(F[n],f[n-1])=1

因为 F[n]=f[n-1]+F[n-2]

所以 gcd(F[n],f[n-1]) = gcd(F[n-1]+F[n-2],F[n-1])

gcd的更损相减的性质可知 gcd(a,b)=gcd(b,a-b)

故  gcd(F[n],f[n-1]) = gcd(F[n-1],F[n-2])

而 F[1]=F[2]=1故该定理成立

 

引理2:F[m+n]=F[m-1]F[n]+F[m]F[n+1] 

F[m+n] = F[m+n-1] + F[m+n-2] = (F[m+n-2]+F[m+n-3])+F[m+n-2]= 2F[m+n-2]+F[m+n-3]

 F[m] F[m+1] ..... F[m+n-2] F[m+n-1] F[m+n]

                                      1             1

                                  2

                2        3

        3      5

我们发现

r(m+n-2) 是 Fib 的第 1 项 所以 m+n-k是Fib的第k-1项

r(m+n-2) 是 Fib 的第 3 项 所以 m+n-k是Fib的第k+1项

r(m-1)=r(m+n-(n+1))=F[n]

t(m)=t(m+n-n)=F[n+1]

所以 F[m+n]=r(m-1)*F[m]+t(m+1)*F[m] = F[m-1]F[n]+F[m]F[n+1] 

 

引理3:gcd(F[n+m],F[n])=gcd(F[n],F[m])

由引理2可知: F[m+n]=F[m-1]F[n]+F[m]F[n+1] 

gcd(F[n+m],F[n]) = gcd(F[m-1]F[n]+F[m]F[n+1] ,F[n]) = gcd(F[n],F[m]F[n+1]) = gcd(F[m],F[n])

这之间用到了辗转相除法和引理1

 

gcd(f[m],f[n])=gcd(f[n],f[m-n])
辗转相减法 就是gcd(f[n],f[m%n])
辗转相除法 就是f[gcd(n,m)]

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
OSCHINA
登录后可查看更多优质内容
返回顶部
顶部