题意:

求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)
至此,我们的结论就证明完毕了。

分类: 文章

发表评论

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

你是机器人吗? =。= *