シルヴァーマン 「はじめての数論」第3版 第37章練習問題1

37.1

(a)

F_m|F_mnと予想される。

(b)

黄金比γに対し、α₁=γ, α₂=1/γとして、F_n=(α₁ⁿ-α₂ⁿ)/√5。

F_mn=[(α₁^m)ⁿ-(α₂^m)ⁿ]/√5=(α₁^m-α₂^m)[(α₁^m)^n-1+(α₁^m)^n-2(α₂^m)¹+...+(α₂^m)^n-1]/√5

=F_m[(α₁^m)^n-1+(α₁^m)^n-2(α₂^m)¹+...+(α₂^m)^n-1]だから、F_m|F_mn。

(c)

パターンというと、例えばgcd(m,n)=1ならgcd(F_m, F_n)=1。

あとは、

F₁₀=55=5·11=11F₅

F₁₅=610=2·5·61=61F₃F₅

F₁₈=2584=2³·17·19=2²·19F₉

F₂₀=6765=3·5·1141=1141F₄F₅

F₂₁=10946=2·13·421=421F₃F₇

F₃₀=832040=2³·5·11·31·61=11·31·61F₅F₆

F₃₃=3524578=2·89·19801=19801F₃F₁₁

F₃₅=9227465=5·13·141961=141961F₅F₇

なども用いて、

gcd(m,n)=1, m>2, n>3ならF_m|F_mn, F_n|F_mnだがF_m²|F_mn, F_n²|F_mnでない。

m=2については、gcd(2,n)=1, n>3なら、F_n|F_mnだがF_n²|F_mnでない。

といったところか。

(d)

gcd(m,n)=gならgcd(F_m, F_n)= F_g| F_mn。証明は難しいらしい。

F_gがF_m, F_nの公約数であることは(a)と同様に示すことができるが、

最大公約数であることを示すのはややこしそうだ。

(e)

...

37.2

(a)

F₁= F₂=1=1², F₁₂=144=12²。

指数的に増大するFibonacci列と平方関数、つまり多項式関数が交差するのは

ここだけなんじゃないだろうか。つまりこれら以外に平方数はない？

・・・と思ったら、Cohn (1964)により、これら以外に平方数がないことが証明されたそうだ。

(b)

F₄=3とF₁₀=55。三角数も多項式関数なので、指数的に増大するFibonacci列と

無数に交差する気がしない。

37.3

(a)

F₃=2, F₄=3, F₅=5, F₇=13, F₁₁=89, F₁₃=233, F₁₇=1597, F₂₃=28657, F₂₉=514229。

(b)

「n>4なら素数である。」

(c)

F₁₉=4181=37·113, F₃₁=1346269=557·2417で合成数だから正しくなさそう。

(d)

F_nが素数でnが合成数であったとすると、n=lmとして、

練習問題37.1(b)よりF_l|F_n, F_m|F_n,である。

n>4なので、2<l<nまたは2<m<nだから、1<F_l<F_nまたは1<F_m<F_nとなるので、

F_nは1とF_n以外に約数を持つことになり矛盾。

したがってnは素数でなければならない。

37.4

(a)

1, 3, 4, 7, 11, 18, 29, 47, 76, 123

(b)

Binetの公式を求めたときのc₁,c₂の連立方程式のH₂の式の方を、

c₁α₁²+c₂α₂²=3に変えればよい。結果L_n=α₁ⁿ+α₂ⁿを得る。

(c)

n=1から順に、-4, 4, -4, 4, -4, 4, -4, 4, -4, 4。

L_n²-5F_n²=4(-1)ⁿ

∵) α₁α₂=-1だから、L_n²-5F_n²=(α₁ⁿ+α₂ⁿ)²-(α₁ⁿ-α₂ⁿ)²=4(α₁α₂)ⁿ=4(-1)ⁿ。

(d)

nについての数学的帰納法を用いると、n=1のときL₁=1, L₂=3は奇数でL₃=4は偶数。

n-1で成り立つとすると、L_3(n-1)+1= L_3n-2= L_3(n-1)+ L_3(n-1)-1は偶数+奇数で奇数。

L_3(n-1)+2= L_3n-1= L_3n-2+ L_3(n-1)も奇数+偶数で奇数だから、

L_3n= L_3n-1+ L_3n-2は奇数+奇数で偶数となり、nでも成り立つ。

F_3nについても同様。

(c)の公式から、(L_3n/2) ²-5(F_3n/2)²=(-1)³ⁿ=(-1)ⁿなので、

nが偶数の時L_3n/2, F_3n/2はD=5のPell方程式の解の無限列を与える。

またnが奇数の時はL_3n/2, F_3n/2は、練習問題32.1で調べた、

D=5のPell方程式類似の方程式x²-5y²=-1の解の無限列である。

実際n=1のときx²-5y²=-1の最小解は(x,y)=(2,1)が得られ、

n=3のとき次の解(x,y)=(38,17)が得られる。

Fibonacci数と、このLucas数やさらに拡張されたLucas数列が、

Pell方程式の解を生成する別の方法を与え、

ウィキペによるとさらに深い性質を持つらしい。

37.5

(a)

1, 3, 19, 87, 451, 2223,...

Binetの公式を導いたときと同様にして、A_n=[5ⁿ-(-2)ⁿ]/7。

(b)

0, -2, -4, 0, 16, 32, 0, -128, -256, 0, ...

Binetの公式を導いたときと同様に、漸化式からα₁=-1+i√3, α₂=conjg(α₁)より、

c₁=(√3-i)√3/12としてB_n=2Re(c₁α₁ⁿ)。

(c)

0, 0, 1, 4, 15, 50, 161, 504, 1555, ....

Binetの公式を導いたときと同様に、漸化式からα₁=-1, α₂=2, α₃=3より、

C_n=[-(-1)ⁿ-2ⁿ⁺¹+3ⁿ]/12

37.6

(a)

n=1から昇順に、1, 9, 1, 33, 1, 129, 1, 513, 1, 2049

(b)

nが奇数(odd=奇妙)の時P_n=1。

(c)

Binetの公式を導いたときと同様に、漸化式からα₁=1, α₂=2, α₃=-2より、

P_n=1+2ⁿ+(-2)ⁿ。nが奇数なら冪の項は打ち消し合ってP_n=1。

奇妙な振る舞いって言うから、もっとすごいことが起きるかと思ったら、

単にodd=奇数=奇妙とのシャレだったらしいｗ

37.7

(a)

黄金比をγとしてF_n=(γⁿ-γ^-n)/√5なので、

log F_n/n=-log 5/(2n)+log γ+log(1-γ^-2n)/n→log γ (n→∞)。

(b)

log A_n/n=-log 7/n+log 5+log[1-(-2/5)ⁿ]/n→log 5 (n→∞)。

(c)

|B_n|はn≡1 (mod 3)のとき0となるので、

log |B_n|はすべてのnに対しては定義できないから極限値はない。

n≡1 (mod 3)を除いた部分列をとれば0でない有限確定値を取る。

(d)

log C_n/n=-log 12/n+log 3+log[1-(-1/3)ⁿ-2(2/3)ⁿ]/n→log 3 (n→∞)。

すなわち、(b)のような特殊な例を除けば、

線形回帰数列の多くは指数的に発散する模様。

37.8

(a)

1,1, 2, 3, 7, 16, 65, 321, 4546, 107587,...

(b)

1, 2, 1, 3, 5, 16, 83, 1333, 110655,...

パターンは・・う～む。