- 704 名前：１３２人目の素数さん mailto:sage [2007/02/12(月) 14:57:21 ]
- >>703前半
F_0=0, F_1=1 とする。数列全体をmod Nで考えたとき「F_n≡0 ならば F_(kn)≡0」を示せばよい。
F_n≡0, F_(n+1)≡x と仮定すると、これは初項が0とxで生成されるフィボであり、
0と1から始まるフィボ全体をx倍したのと同じなので、F_(n+i)≡xF_i が成り立つ。
よって、たとえば F_(3n)≡F(n+2n)≡xF(2n)≡xF(n+n)≡(x^2)F(n)≡0。
一般のF_(kn)も、F_(kn)≡xF((k-1)n)≡‥‥≡(x^(k-1))F(n)≡0。
具体例：mod 5で考えると
0, 1, 1, 2, 3, 0, 3, 3,‥‥（5番目が0、次が3だから、その後は）
↓（3倍） ~~~~
0, 3, 3, 1, 4, 0, 4, 4,‥‥（全体を3倍したのと同じになる。だから5の倍数番目は全部0）
