题意:

求 f(1)=f(2)=1 的斐波那契数列中 f(i)|f(x) 的 i 之和

分析:

首先,我们发现一个规律:
比如在 mod 8 意义下,斐波那契数列是这样的:
(1 1 2 3 5 0 5 5 2 7 1 0 ) 循环
在 mod 13 意义下,斐波那契数列是这样的:
(1 1 2 3 5 8 0 8 8 3 11 1 0)
也就是说 f(i) 的倍数是每隔 i 个数存在一个的。
但是如何说明 0 会每隔 i 个出现一次不多不少呢?
对于这道题,我们可以采用粗略的证明来验证我们的思想:


引理 1: f(1) 到 f(i-1) 在 mod f(i) 下一定是没有 0 的斐波那契数列。
证明:显然他们都小于 f(i) 大于 0,因此不可能有 0。
引理2:f(i)与f(i+1)互质(i>=2)
证明:要证明这个,我们只需要说明 gcd(f(i),f(i+1))=1 即可。
由于 gcd 的过程是辗转相除,我们不妨模拟一下:
gcd(f(i),f(i+1))=gcd(f(i),f(i)+f(i-1))=gcd(f(i-1),f(i))
因此像这样递推下去,gcd(f(i),f(i+1))=gcd(f(1),f(2))=1;


由于引理 1 并且 f(i)=0 (mod f(i)),我们有:f(i+1)=f(i+2)=f(i-1)
所以:f(i+1) 到 f(2i-1) 是一组以 f(i-1),f(i-1) 开始的斐波那契数列。
设 f(1) 到 f(i-1) 为 S,f(i+1) 到 f(2i-1) 为 P
由于斐波那契数列的每一项是前两项的和,所以 f(x) 与首项线性相关,所以在 mod f(i) 意义下:
Pj = f(i-1)Sj (mod f(i))
下面我们要证 P 中没有 0.
由于引理 2:f(i) 与 f(i-1) 互质,那么 kf(i-1) != f(i) (mod f(i)) (k < f(i))
根据 P 的定义,Pj = f(i-1)Sj (mod f(i)),因此 Pj = Sj f(i-1) != f(i)
至此,又因为 f(2i)=f(i-1)f(i)=0,所以我们已经证明了 f(i)=f(i+1)=0 (mod f(i)),其余的各项不为 0.

证明了 f(1) 到 f(2i),我们依旧可以用上述方法证明 f(2i) 到 f(3i), 一直到 f(ki)
至此,我们的结论就证明完毕了。

分类: 文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注