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

※MathJaxの数式表示に少し時間がかかります。

5.1
(a) 15
(b) 3

5.3
$r_n$ ($n\ge0$)は自然数を$r_{n-1}$で割った剰余なので$r_{n-1}>r_n$である。$a<b$であることがありうるので互除法の最初の1ステップのみ$q_1\ge0$だが、以降のステップでは$r_{m-1}<r_{m-2}$ ($m\ge2$)より$q_m\ge1$。これらの不等式を用いて$i\ge0$について $$r_i=q_{i+2}r_{i+1}+r_{i+2}\ge r_{i+1}+r_{i+2}>2r_{i+2}$$ だから、 $$r_{i+2}<\frac{1}{2}r_i$$

5.4
(a)(b)
(i) $m=8$, $n=12$に対し$\mathrm{LCM}(m,n)=24$, $\gcd(m,n)=4$
(ii) $m=20$, $n=30$に対し$\mathrm{LCM}(m,n)=60$, $\gcd(m,n)=10$
(iii) $m=51$, $n=68$に対し$\mathrm{LCM}(m,n)=204$, $\gcd(m,n)=17$
(iv) $m=23$, $n=18$に対し$\mathrm{LCM}(m,n)=414$, $\gcd(m,n)=1$

$mn=\mathrm{LCM}(m,n)\gcd(m,n)$と予想される。

(c)
$\gcd(m,n)=d$とすると、$m=dm', n=dn'$ ($\gcd(m',n')=1$)と書ける。このとき$\mathrm{LCM}(m,n)=dm'n'$である：$m|dm'n'$, $n|dm'n'$は明らかだから、$dm'n'$は$m,n$の公倍数。$m,n$の公倍数$L$について、$m|L$より$L=dm'p$とかける。$n|L$でもあるから、$n'|m'p$だが、$m'$と$n'$は互いに素だから$n'|p$でなければならないので$p=n'p'$。これより$L=dm'n'p'$だから$dm'n'|L$。よって$dm'n'$は$m,n$のすべての公倍数の約数なので、すべての公倍数の中で最小のものだから、$\mathrm{LCM}(m,n)=dm'n'$。
以上により$mn=dm'dn'=dm'n'\cdot d=\mathrm{LCM}(m,n)\gcd(m,n)$。

(d)
$\gcd(301337,307829)=541$より、$\mathrm{LCM}(301337,307829)=301337\cdot307829/541=171460753$。

(e)
$m=18m'$,$n=18n'$とすれば(c)より$18m'n'=720$だから$m'n'=40$かつ$\gcd(m',n')=1$。これを満たす40の約数の組は(1,40)と(5,8)の2つなので、$(m,n)$として(18,720)または(90,144)。

5.5
数論の未解決問題''Collatz問題''。常に停止するかどうかは未解決だが、停止しない例は見つかっていない。
(a)
(i) 値1, 長さ8
(ii) 値1, 長さ10
(iii) 値1, 長さ107

(b)
$n=10000$まで調べた範囲では、常に停止し、繰り返しは1,4,2,1,4,2,1,4,2,1...である。

(c)
$n=8k+4$から始めても$n+1=8k+5$から始めても、アルゴリズムの3回めの動作で$6k+4$となるので、$L(n)=3+L(6k+4)=L(n+1)$。

(d)
$n=128k+28=8(16k+3)+4$だから、(c)により$L(n)=L(n+1)$。$n$から始めると、アルゴリズムの7回目の動作で$216k+52=8(27k+6)+4$となり、$n+2$から始めると7回目の動作で$216k+53=8(27k+6)+5$となるから、(c)により$L(n)=7+L(216k+52)=7+L(216k+53)=L(n+1)$。以上により$L(n)=L(n+1)=L(n+2)$。

(e)
(i)
$n=16k+2$から始めるとアルゴリズムの2回めの動作で$24k+4=8\cdot3k+4$となり、$n+1$から始めると2回めの動作で$24k+5=8\cdot3k+5$となるので、(c)により$L(n)=2+L(24k+4)=2+L(24k+5)=L(n+1)$

(ii)
$n=32k+22$から始めるとアルゴリズムの2回めの動作で$48k+34=16(3k+2)+2$となり、$n+1$から始めると2回めの動作で$48k+35=16(3k+2)+3$となるので、(e)(i)により$L(n)=2+L(48k+34)=2+L(48k+35)=L(n+1)$

(iii)
$n=64k+14$から始めるとアルゴリズムの2回めの動作で$96k+22=32\cdot3k+22$となり、$n+1$から始めると2回めの動作で$96k+23=32\cdot3k+23$となるので、(e)(ii)により$L(n)=2+L(96k+22)=2+L(96k+23)=L(n+1)$

(iv)
$n=128k+94$から始めるとアルゴリズムの2回めの動作で$192k+142=64(3k+2)+14$となり、$n+1$から始めると2回めの動作で$192k+143=64(3k+2)+15$となるので、(e)(iii)により$L(n)=2+L(192k+142)=2+L(192k+143)=L(n+1)$

(c)と(i)〜(iv)のパターンは以下にまとめられる：
ある$i\ge3$, $0<a_i<2^{i-1}$ (ただし$j\ge0$として$a_i=3j+l_i$, $l_i=$ 1 ($i$が偶数のとき) or 2 ($i$が奇数のとき))と、任意の$k\ge1$について $$n^{(i)}_k=2^ik+2a_i$$ が$L(n^{(i)}_k)=L(n^{(i)}_k+1)$を満たすなら、 $$n^{(i+1)}_k=2^{i+1}k+2a_{i+1}$$ も任意の$k\ge1$について$L(n^{(i+1)}_k)=L(n^{(i+1)}_k+1)$を満たす。ただし、 $$a_{i+1}=\frac{1}{3}(2^im_{i+1}+2a_i-1)$$ $$m_i=\left\{\begin{array}{cc} 0& \mbox{($i$が偶数のとき)}\\2& \mbox{($i$が奇数のとき)}\end{array}\right.$$

(証明)
まず、$\lambda\ge0$として $$2^i=\left\{\begin{array}{cc} 3\lambda+1& \mbox{($i$が偶数のとき)}\\3\lambda+2& \mbox{($i$が奇数のとき)}\end{array}\right.$$ であることを示す。実際、$i=0$について$2^i=1=3\cdot0+1$で、$2^i=3\lambda+1$なら$2^{i+1}=2\cdot2^i=3\cdot(2\lambda)+2$、また$2^i=3\lambda+2$なら$2^{i+1}=3(2\lambda+1)+1$となる。
これを用いて、$a_{i+1}=(2^im_{i+1}+2a_i-1)/3$が奇数であることを示す。$i$が偶数なら$2^im_{i+1}+2a_i-1=2(3\lambda+1)+2(3j+1)-1=3[2(\lambda+j)+1]$なので$a_{i+1}=2(\lambda+j)+1$は奇数。$i$が奇数なら$2^im_{i+1}+2a_i-1=2(3j+2)-1=3(2j+1)$なので$a_{i+1}=2j+1$は奇数。
さて、 $$n^{(i+1)}_k=2^{i+1}k+2a_{i+1}$$ は偶数なので、$(3n+1)$アルゴリズムを1回行って
$$2^ik+a_{i+1}$$ $a_{i+1}$は奇数なのでこれも奇数だから、さらにもう1回行って整理すれば、 $$3(2^ik+a_{i+1})+1=2^i(3k+m_{i+1})+2a_i=n^{(i)}_{3k+m_{i+1}}$$ となるので、$L(n^{(i+1)}_k)=2+L(n^{(i)}_{3k+m_{i+1}})$。
また $$n^{(i+1)}_k+1=2^{i+1}k+2a_{i+1}+1$$ は奇数なので、$(3n+1)$アルゴリズムを1回行って $$2^{i+1}\cdot3k+6a_{i+1}+4$$ これは偶数だからさらにもう1回行って整理すれば、 $$2^i\cdot3k+3a_{i+1}+2=2^i(3k+m_{i+1})+2a_i+1=n^{(i)}_{3k+m_{i+1}}+1$$ となるので、$L(n^{(i+1)}_k+1)=2+L(n^{(i)}_{3k+m_{i+1}}+1)$。
仮定により$L(n^{(i)}_{3k+m_{i+1}})=L(n^{(i)}_{3k+m_{i+1}}+1)$だから、$L(n^{(i+1)}_k)=L(n^{(i+1)}_k+1)$となる。(証明終)

(c)の$8k+4$が$i=3, a_3=2=3\cdot0+2$で上の条件を満たすので、$L(n)=L(n+1)$となる一つの系列として、$n=8k+4$, $16k+2$, $32k+22$, $64k+14$, $128k+94$, $256k+62$, $512k+382$, ...が得られる。
(d)の$128k+28$についてもいろいろ言えると思うが、面倒なのでパス。