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

40.6

(a)

連分数の周期数列[(b₁, ..., b_m)]の周期自体を求めるのではなく、

√D=a+1/α₀, b_n=⌊α_n-1⌋, α_n-1=b_n+1/α_nによって決まる実数列{α_n}(n≥1)について、

α₀=α_nとなる最小のnを求めた方が、精度よく計算でき、

しかも比較がα₀との比較だけで済むのでやりやすい。

α₀=(a+√D)/(D-a²)である。α_n=(r_n+s_n√D)/t_nとおくと、

r₀=a, s₀=1, t₀= D-a²。また、b_n+1=⌊α_n⌋を用いてα_n=b_n+1+1/α_n+1を解いて

r_n+1=t_n(b_n+1t_n-r_n), s_n+1=s_nt_n, t_n+1=s_n²D-(b_n+1t_n-r_n)²。

この漸化式をプログラムに組んで、以下の表を得る。

√2=[1, (2)]

√3=[1, (1, 2)]

√5=[2, (4)]

√6=[2, (2, 4)]

√7=[2, (1, 1, 1, 4)]

√8=[2, (1, 4)]

√10=[3, (6)]

√11=[3, (3, 6)]

√12=[3, (2, 6)]

√13=[3, (1, 1, 1, 1, 6)]

√14=[3, (1, 2, 1, 6)]

√15=[3, (1, 6)]

√17=[4, (8)]

√18=[4, (4, 8)]

√19=[4, (2, 1, 3, 1, 2, 8)]

√20=[4, (2, 8)]

√21=[4, (1, 1, 2, 1, 1, 8)]

√22=[4, (1, 2, 4, 2, 1, 8)]

√23=[4, (1, 3, 1, 8)]

√24=[4, (1, 8)]

√26=[5, (10)]

√27=[5, (5, 10)]

√28=[5, (3, 2, 3, 10)]

√29=[5, (2, 1, 1, 2, 10)]

√30=[5, (2, 10)]

√31=[5, (1, 1, 3, 5, 3, 1, 1, 10)]

√32=[5, (1, 1, 1, 10)]

√33=[5, (1, 2, 1, 10)]

√34=[5, (1, 4, 1, 10)]

√35=[5, (1, 10)]

√37=[6, (12)]

√38=[6, (6, 12)]

√39=[6, (4, 12)]

√40=[6, (3, 12)]

√41=[6, (2, 2, 12)]

√42=[6, (2, 12)]

√43=[6, (1, 1, 3, 1, 5, 1, 3, 1, 1, 12)]

√44=[6, (1, 1, 1, 2, 1, 1, 1, 12)]

√45=[6, (1, 2, 2, 2, 1, 12)]

√46=[6, (1, 3, 1, 1, 2, 6, 2, 1, 1, 3, 1, 12)]

√47=[6, (1, 5, 1, 12)]

√48=[6, (1, 12)]

√50=[7, (14)]

(b)

(3+2√2)/5=[1, 6, (28, 7)]

(3+2√3)/5=[(1, 3, 2, 2, 2, 3, 1, 10)]

(3+2√5)/5=[(1, 2, 44, 2, 1, 3, 2, 1, 1, 10, 1, 1, 2, 3)]

(3+2√6)/5=[(1, 1, 1, 2)]

(3+2√7)/5=[(1, 1, 1, 1, 12, 1, 1, 1, 1, 2, 5, 2, 52, 2, 5, 2)]

(3+2√8)/5=[(1, 1, 2, 1, 2, 1, 1, 1, 1, 7, 2, 7, 1, 1)]

(3+2√10)/5=[(1, 1, 6, 2, 2, 15, 2, 2, 6, 1, 1, 1, 1, 1, 62, 1, 1, 1)]

(3+2√11)/5=[(1, 1, 12, 1, 1, 1, 2, 1)]

(3+2√12)/5=[(1, 1, 68, 1, 1, 1, 3, 1)]

(3+2√13)/5=[(2, 23, 1, 2, 5, 1)]

(3+2√14)/5=[(2, 10, 2, 1, 8, 1)]

(3+2√15)/5=[(2, 6, 1, 2, 2, 1, 2, 1, 76, 1, 2, 1, 2, 2, 1, 6, 2, 1, 18, 1)]

(3+2√17)/5=[2, (4, 82, 4, 3, 20, 3)]

(3+2√18)/5=[2, (3, 2, 1, 2, 1, 2, 3, 3, 10, 3)]

(3+2√19)/5=[2, (2, 1, 10, 5, 28, 1, 6, 3)]

(3+2√20)/5=[2, (2, 1, 1, 2, 1, 88, 1, 2, 1, 1, 2, 3, 5, 3)]

(3+2√21)/5=[2, (2, 3, 4, 3)]

(3+2√22)/5=[2, (2, 9, 1, 92, 1, 9, 2, 3, 3, 1, 1, 1, 1, 1, 3, 3)]

(3+2√23)/5=[2, (1, 1, 13, 7, 3, 3)]

(3+2√24)/5=[2, (1, 1, 3, 1, 2, 3)]

(3+2√26)/5=[2, (1, 1, 1, 3, 2, 3)]

(3+2√27)/5=[2, (1, 2, 9, 11, 2, 3)]

(3+2√28)/5=[2, (1, 2, 1, 1, 8, 4, 8, 1, 1, 2, 1, 3, 1, 1, 14, 1, 1, 3)]

(3+2√29)/5=[2, (1, 3, 15, 8, 4, 1, 1, 3)]

(3+2√30)/5=[2, (1, 3, 1, 3, 1, 1, 2, 3, 1, 108, 1, 3, 2, 1, 1, 3)]

(3+2√31)/5=[2, (1, 4, 1, 3, 1, 1, 1, 2, 7, 22, 7, 2, 1, 1, 1, 3)]

(3+2√32)/5=[2, (1, 6, 3, 1, 1, 112, 1, 1, 3, 6, 1, 3, 1, 1, 1, 27, 1, 1, 1, 3)]

(3+2√33)/5=[2, (1, 8, 1, 3, 1, 2, 3, 4, 3, 2, 1, 3)]

(3+2√34)/5=[2, (1, 13, 1, 3, 1, 2, 1, 2, 1, 3)]

(3+2√35)/5=[2, (1, 28, 1, 3, 1, 3, 3, 1, 1, 4, 6, 118, 6, 4, 1, 1, 3, 3, 1, 3)]

(3+2√37)/5=[3, (30, 4, 1, 4, 1, 120, 1, 4, 1, 4)]

(3+2√38)/5=[3, (15, 4, 1, 6, 2, 4, 2, 6, 1, 4)]

(3+2√39)/5=[3, (10, 4, 1, 8, 1, 4)]

(3+2√40)/5=[3, (7, 1, 2, 2, 1, 2, 1, 4, 3, 31, 3, 4, 1, 2, 1, 2, 2, 1, 7, 4, 1, 13, 4, 126, 4, 13, 1, 4)]

(3+2√41)/5=[3, (6, 4, 1, 24, 1, 4)]

(3+2√42)/5=[3, (5, 4, 1, 128, 1, 4)]

(3+2√43)/5=[3, (4, 2, 15, 1, 17, 1, 3, 1, 10, 7, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 7, 10, 1, 3, 1, 17, 1, 15, 2, 4, 5, 43, 1, 1, 9, 1, 1, 2, 1, 1, 9, 1, 1, 43, 5)]

(3+2√44)/5=[3, (3, 1, 18, 5)]

(3+2√45)/5=[3, (3, 1, 1, 7, 1, 4, 2, 14, 2, 4, 1, 7, 1, 1, 3, 5, 12, 134, 12, 5)]

(3+2√46)/5=[3, (3, 5, 8, 1, 5, 1, 8, 5)]

(3+2√47)/5=[3, (2, 1, 11, 1, 3, 1, 1, 136, 1, 1, 3, 1, 11, 1, 2, 5, 7, 34, 7, 5)]

(3+2√48)/5=[3, (2, 1, 2, 3, 1, 4, 1, 3, 2, 1, 2, 5, 5, 1, 5, 5)]

(3+2√50)/5=[3, (2, 2, 1, 140, 1, 2, 2, 5, 4, 2, 1, 1, 1, 5, 35, 5, 1, 1, 1, 2, 4, 5)]