37.9
連続する2つの整数の対(r, r+1)と(s, s+1)に対し(s>r)、
対(Fr, Fr+1)と(Fs, Fs+1)とが一致すれば、rからsまでの列が、
sからもう一度繰り返される。
Fj (mod m)の値lの選択は0≤l≤ m-1のm通りなので、
(Fj, Fj+1)の対は多くともm2種類しかない。
したがって、1≤i≤ m2 +1としてm2+1個の対(Fi, Fi+1)を考えれば、
鳩の巣原理により、mを法として合同な対の組(Fr, Fr+1),(Fs, Fs+1)
(1≤r<s≤m2 +1)が少なくとも一組ある。
したがって、mを法としたFibonacci数は、m2+1番目までに繰り返しが現れる。
いまr>1, N=s-rとすると、Fr-1=Fr+1-Fr ≡Fs+1-Fs= Fs-1=Fr-1+N (mod m)だから、
mod mでFr-1も周期Nで繰り返される。以下適当に繰り返せば、
F1がmod mで、周期Nで繰り返されることがわかる。
したがってmod mでF1からの数列が繰り返される。
37.10
(a)
FN=0, FN-1=1。
(b)
FN, FN-1,..., F1をmod mで逆順に書き、-m~-1に合同になるようにして負号を省略すると
m=2: 211
m=3: 32113122
m=4: 431233
m=5: 54133532115142252344
m=6: 651431253211615235413455
という並びになる。mod mで
FN≡-m, FN-1≡-m+1, FN-2≡-1, FN-3≡-m+2, FN-4≡-3となる模様。
(c)
FN+1≡F1=1≡-m+1, FN+2≡F2=1≡-m+1 (mod m)だから、
FN= FN+2-FN+1=0≡-m (mod m)
FN-1≡FN+1-FN≡1≡-m+1(mod m)
FN-2≡FN-FN-1≡-1 (mod m)
FN-3≡FN-1-FN-2≡-m+2 (mod m) (m=2なら-2),
FN-4≡FN-2-FN-3≡m-3≡-3 (mod m) (m=2なら-1),
37.11
以下の証明は英語版ウィキペのPisano周期
（mを法としたFibonacci数列の周期のこと）の項を参考にしている。
名前は「ピサのレオナルド(Leonardo Pisano)」=Fibonacciに由来するらしい。
まず以下の補題を証明する。
補題（Cassiniの恒等式）：Fn+1Fn−1−Fn2=(−1)n
∵) 数学的帰納法で証明する。n=2に対してF3F1-F22=1=(-1)2で正しい。
n-1で正しい、つまりFnFn−2-Fn−12=(-1)n-1と仮定すると、nでは
Fn+1Fn−1−Fn2=(2Fn−1+Fn−2) Fn−1-(Fn−1+Fn−2)2=Fn−12-Fn−2(Fn−1+Fn−2)=Fn−12-Fn−2Fn=(-1)n
となるので、nでも正しいから、Cassiniの恒等式が全てのn≥2で成り立つ。
Cassiniの恒等式により、FN(m)+1FN(m)−1−FN(m)2=(-1)N(m)。
練習問題37.10(c)からFN(m)+1≡FN(m)-1≡1 (mod m), FN(m)≡0 (mod m)なので、
1≡(-1)N(m) (mod m)を得る。これよりm≥3ではN(m)は偶数
(m=2では1≡-1 (mod 2)だから奇数でもよい)。
37.12
(a)(b)
gcd(m1, m2)=1のとき、
N(m1m2)=LCM(N(m1),N(m2))= N(m1)N(m2)/gcd(N(m1),N(m2))の模様。
(c)
N(5184)=N(26·34)=N(64)N(81)/gcd(N(61), N(81))=864,
N(6887)=N(71·97)=N(71)N(97)/gcd(N(71), N(97))=980。
(d)
以下の証明はRenault (1996)の修士論文を参考にしている。
Fi+N(m1m2) ≡Fi ≡a (mod m1m2), 0≤a<m1m2とすれば、
Fi =a+m1m2r, Fi+N(m1m2)=a+m1m2s (r,s≥0)とおける。
a≡a' (mod m1)とすると、a=a'+m1t (0≤a'<m1)として、
Fi+N(m1m2)=a'+m1(m2s+t)≡a'+m1(m2r+t)≡Fi (mod m1)となる。
すなわちN(m1m2)はmod m1でもFibonacci列の周期となるので、N(m1)|N(m1m2)。
同様にN(m2)|N(m1m2)なので、N(m1m2)はN(m1), N(m2)の公倍数だから、
LCM(N(m1), N(m2))|N(m1m2) (1)。
一方、N(m1)|LCM(N(m1), N(m2)), N(m2)|LCM(N(m1), N(m2))より、
F1+LCM(N(m1), N(m2))≡F1 (mod m1)かつF1+LCM(N(m1), N(m2))≡F1 (mod m2)で、
しかもgcd(m1, m2)=1だから、定理11.2（中国の剰余定理）により、
F1+LCM(N(m1), N(m2))≡F1 (mod m1m2)。同様にF2+LCM(N(m1), N(m2))≡F2 (mod m1m2)となるので、
全てのiに対しFi+LCM(N(m1), N(m2))≡Fi (mod m1m2)。
すなわちLCM(N(m1), N(m2))はmod m1m2でFibonacci列の周期になるから、
N(m1m2)|LCM(N(m1), N(m2)) (2)。
(1),(2)によりN(m1m2)=LCM(N(m1), N(m2))。
Fibonacci数であることは本質的でなく、Lucas数などの一般化列でも成り立つ
37.13
(a)
N(2)=3, N(22)=6
N(3)=8, N(32)=24
N(5)=20, N(52)=100
N(7)=16, N(72)=112
(b)
N(p2)=pN(p)と予想される。
(c)
N(2)=3, N(22)=6, N(23)=12, N(24)=24, N(25)=48, N(26)=96
N(3)=8, N(32)=24, N(33)=72, N(34)=216
N(pn)=pn-1N(p)と予想される。
(d)
N(2209)=N(472)=47N(47)=1504。
N(1024)=N(210)= 29N(2)=1536。
N(729)=N(36)= 35N(3)=1944。
(e)
数学的帰納法による証明がRenault (1996)の修士論文
(p=2について定理3.5, p≥3について定理3.8)にあるが少し長く、
またFibonacci数の行列表現なども説明しなければならないが、
それを記すにはこの余白は小さすぎる。
未解決問題として「全ての素数pと、t>1に対しN(pt)> N(p)」が、
証明も反証もされていないらしい。
0 件のコメント :
コメントを投稿