フィボナッチ数列の問題

質問

高校２年です
回答をみても今ひとつわからなかったので
わかりやすい回答をお願いしたいです

フィボナッチ数列において
任意の自然数mの対して
ar≡as (mod m)
a(r+1)≡a(s+1) (mod m)
となる自然数r,s(r<s)が存在することを示せ

よろしくお願いします

回答No.3

f272 · ベストアンサー

フィボナッチ数列は
1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,...
mod 1なら0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,...で0の繰り返し
mod 2なら1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,...で1,1,0の繰り返し
mod 3なら1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,0,1,1,2,0,...で1,1,2,0,2,2,1,0の繰り返し
mod 4なら1,1,2,3,1,0,1,1,2,3,1,0,1,1,2,3,1,0,1,1,...で1,1,2,3,1,0の繰り返し
mod 5なら1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0,...で1,1,2,3,0,3,3,1,4,0,4,4,3,2,0,2,2,4,1,0の繰り返し
mod 6なら1,1,2,3,5,2,1,3,4,1,5,0,5,5,4,3,1,4,5,3,...で1,1,2,3,5,2,1,3,4,1,5,0,5,5,4,3,1,4,5,3,2,5,1,0の繰り返し
mod 7なら1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0,1,1,2,3,...で1,1,2,3,5,1,6,0,6,6,5,4,2,6,1,0の繰り返し
mod 8なら1,1,2,3,5,0,5,5,2,7,1,0,1,1,2,3,5,0,5,5,...で1,1,2,3,5,0,5,5,2,7,1,0の繰り返し
で，どんな場合でも有限回で繰り返しに入ります。この繰り返しまでの回数をC(m)とすると
上の命題は例えばs=r+C(m)とすることで満足されます。
さてC(m)が必ず存在するかですが，証明は結構面倒なので省きますが，必ず存在します。そしてC(m)は
m=2のときC(m)=3
m=5のときC(m)=20
mがそれ以外の素数でm≡±1(mod 5)のときC(m)=(m-1の約数)
mがそれ以外の素数でm≡±2(mod 5)のときC(m)=(2(m+1)の約数)
mが素数の冪のときでm=p^eのときC(m)=(p^(e-1)*C(p)の約数)
それ以外のときでm=m1*m2のときC(m)=(C(m1)*C(m2)の約数)
になることが分かります。

お礼

回答ありがとうございました

こんな解答初めてみたので
とてもたのしかったです

回答No.2

Tacosan

これは「鳩の巣原理」というやつです.
「m で割った余り」は 0, 1, ..., m-1 の m通りしかありません. これを 2つならべているので, 全体でたかだか m^2通りです. 従って, (なんでもいいので) m^2個を「超える」数の対をもってくれば, その中には必ず同じものが存在します. m^2 を超えればいいので m^2+m でも 2m^2+5m+3 でも 7041m^30 でもいいんですが, あまり多くても意味がないので普通は m^2+1 とか m^2+m とか 2m^2 あたりを使います.
で「解答を見せてもらった方がいいような気がする」というのは, 逆に「同じ解答が出てきても意味ないでしょ?」ってこと. 「これと違う解答」って明記しておけば, 多分違う解答が (存在すれば) 出てくると思うよ.

回答No.1

Tacosan

その「今ひとつわからない」という解答を見せてもらった方がいいような気がするんだけど....
単純にやるなら
(a1 mod m, a2 mod m), (a2 mod m, a3 mod m), ..., (a(m^2+1) mod m, a(m^2+2) mod m) という m^2+1個の対を考えるとこの中には必ず等しいものが存在する
で終わり.

お礼

回答ありがとうございます

その解答を見せたら
その考え方以外の解答が
みれなくなるかもしれないと思い
あえてのせませんでした。

m^2+1個の対の m^2+1がどこから出て来たのかが
今ひとつわかりません・・・