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

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

8.1
$k,l\in\mathbb{Z}$とすると、定義により $$a_1-b_1=mk\tag{1}$$ $$a_2-b_2=ml\tag{2}$$
(a)
(1)(2)を辺々足して$(a_1+a_2)-(b_1+b_2)=m(k+l)$だから$a_1+a_2\equiv b_1+b_2 \pmod{m}$。

(b)
(1)(2)より$a_1=mk+b_1$, $a_2=ml+b_2$。これらの積より$a_1a_2=m(mkl+kb_2+lb_1)+b_1b_2$なので$a_1a_2-b_1b_2=m(mkl+kb_2+lb_1)$だから$a_1a_2\equiv b_1b_2 \pmod{m}$。

8.2
$k\in\mathbb{Z}$として、定義により$ac-bc=c(a-b)=mk$だから$m|c(a-b)$。$\gcd(c,m)=1$だから練習問題7.1により$m|(a-b)$となるので$a\equiv b \pmod{m}$。

8.3
(a) $x\equiv9\pmod{15}$
(b) 解なし。
(c) $x\equiv1,3,5,7\pmod{8}$
(d) $x\equiv3,4\pmod{7}$
(e) 解なし。

8.4
(a)
$a$の末尾2桁を$a_2$とする。すなわち$a=100k+a_2$ ($k\geq0$, $0\leq a_2<100$ )。$a-a_2=100k=4\cdot25k$だから、$a\equiv a_2\pmod{4}$である。
したがって$4|a$すなわち$a\equiv0\pmod{4}$と$4|a_2$すなわち$a_2\equiv0\pmod{4}$は同値。

(b)
$a$の末尾3桁を$a_3$とする。すなわち$a=1000k+a_3$ ($k\geq0$, $0\leq a_3<1000$ )。$a-a_3=1000k=8\cdot125k$だから、$a\equiv a_3\pmod{8}$である。
したがって$8|a$すなわち$a\equiv0\pmod{8}$と$8|a_3$すなわち$a_3\equiv0\pmod{8}$は同値。

(c)(d)
$n+1$桁の数$a$が、$1\leq a_n\leq9$, $0\leq a_i\leq9$ ($0\leq i\leq n-1$)となる$a_0,\cdots,a_n$を用いて$a=10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0$と表されているとする。$10\equiv1\pmod{9}$なので練習問題8.1(b)により$10^j\equiv1\pmod{9}$ ($1\leq j\leq n$)だから、$10^j=9k_j+1$ ($k_j\in\mathbb{N}$)と書けるので、$a$の各桁の和$s=a_n+a_{n-1}+\cdots+a_1+a_0$として $$a=9(a_nk_n+a_{n-1}k_{n-1}+\cdots+a_1k_1)+s\tag{3}$$ これより$a\equiv s \pmod{9}$だから、$9|a$すなわち$a\equiv0\pmod{9}$と$9|s$すなわち$s\equiv0\pmod{9}$は同値。
(3)において3を法としても同様なので、$3|a$と$3|s$は同値。

(e)
(c)(d)と同様に$a=10^na_n+10^{n-1}a_{n-1}+\cdots+10a_1+a_0$とする。$10\equiv-1\pmod{11}$なので練習問題8.1(b)により $$10^j\equiv\left\{\begin{array}{cc} 1\pmod{11}& \mbox{($j$が偶数のとき)}\\-1\pmod{11}& \mbox{($j$が奇数のとき)}\end{array}\right.$$
これより$a$の各桁の交代和を$A$として$a\equiv A\pmod{11}$だから、$11|a$すなわち$a\equiv0\pmod{11}$と$11|A$すなわち$A\equiv0\pmod{11}$は同値。

8.5
(a) $x\equiv6,13\pmod{14}$
(b) 解なし。
(c) $x\equiv5,18,31,44,57,70,83\pmod{91}$

8.6
(a) $\gcd(72,200)=8$より$\gcd(72,200)\nmid47$だから、定理8.1により解はない。
(b) $\gcd(4183,15087)=47$で、$\gcd(4183,15087)\mid5781$だから、定理8.1により解は47個。
(c) $\gcd(1537,6731)=53$より$\gcd(1537,6731)\nmid2863$だから、定理8.1により解はない。

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

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

7.1
定理7.3により$a=p_1p_2\cdots p_n$と素因数分解される。$\gcd(a,b)=1$だから、$p_1$は$b$の因数でないので、定理7.2により$p_1|c$。そこで$a_1=a/p_1=p_2p_3\cdots p_n$, $c_1=c/p_1$とすると、$a_1|bc_1$だから、上と同様に$p_2|c_1$となるので$p_1p_2|c$。同様に繰り返して$p_1p_2\cdots p_n|c$だから$a|c$。

7.2
$a=p_1p_2\cdots p_m$, $b=q_1q_2\cdots q_n$と素因数分解されたとすると、$\gcd(a,b)=1$より$\{p_1,p_2,\cdots, p_m\}\cap\{q_1q_2\cdots q_n\}=\emptyset$。$a|(c\cdot1)$なので練習問題7.1により$p_1p_2\cdots p_m|c$だから、$c=c'p_1p_2\cdots p_m$とかける。$q_1\nmid p_1p_2\cdots p_m$だから定理7.2により$q_1|c'$。以降$q_2,\cdots, q_n$について練習問題7.1と同様に繰り返して$q_1q_2\cdots q_n|c'$。故に$c'=c''q_1q_2\cdots q_n$となるから、$c=c''p_1p_2\cdots p_mq_1q_2\cdots q_n=c''ab$なので$ab|c$。

7.3
(a)
$n=1$のとき$n(n+1)/2=1$だから成立。$n>1$に対して$1+2+\cdots+(n-1)+n=(n-1)n/2+n=n(n+1)/2$。

(b)
$n=1$のとき$n(n+1)(2n+1)/6=1=1^2$だから成立。$n>1$に対して$1^2+2^2+\cdots+(n-1)^2+n^2=(n-1)n[2(n-1)+1]/6+n^2=n(n+1)(2n+1)/6$。

(c)
$n=0$のとき$(1-a^{n+1})/(1-a)=1$だから成立。$n>0$に対して$1+a+a^2+\cdots+a^n=(1-a^n)/(1-a)+a^n=(1-a^{n+1})/(1-a)$。

(d)
$n=2$のとき$(n-1)/n=1/2$だから成立。$n>2$に対して$1/(1\cdot2)+\cdots+1/[(n-2)(n-1)]+1/[(n-1)n]=(n-2)/(n-1)+1/[(n-1)n]=(n-1)/n$。

7.4
まー大体の話でいいと思うので、$\mathbb{E}$を公理的に構成するとか、$\mathbb{N}$によらずに証明するとかってのは、ここでは要求されてないよね多分。

(a)(b)
$\mathbb{E}$は$n\in\mathbb{N}$として$4n$か$4n+2$の形の数から構成される。$4n$の形の数は$2\cdot2n$というように$2,2n\in\mathbb{E}$の積に分解できるので$\mathbb{E}$素数でない。$4n+2$の形の数は$\mathbb{N}$において$p_1,\cdots,p_m$を奇素数として$2p_1\cdots p_m$と一意に分解され、偶数$\times$偶数の形になりえないからすべて$\mathbb{E}$素数。

(c)
2通りの分解を与える最小の数：$36=2\cdot18=6\cdot6$
3通りの分解を与える最小の数：$180=2\cdot90=6\cdot30=10\cdot18$
4通りの分解を与える最小の数：$360=2\cdot2\cdot90=2\cdot6\cdot30=2\cdot10\cdot18=6\cdot6\cdot10$

(d)
$e$を1つの$\mathbb{E}$素数として$2^ne$ ($n\geq0$)の形の数。

7.5
(a)
5,9,13,17,21,29

(b)
$441=9\cdot49=21\cdot21$

7.6
(b)
$1000000=2^{6}\cdot 5^{6}$
$1000001=101\cdot 9901$
$1000002=2\cdot 3\cdot 166667$
$1000003=1000003$
$1000004=2^{2}\cdot 53^{2}\cdot 89$
$1000005=3\cdot 5\cdot 163\cdot 409$
$1000006=2\cdot 7\cdot 71429$
$1000007=29\cdot 34483$
$1000008=2^{3}\cdot 3^{2}\cdot 17\cdot 19\cdot 43$
$1000009=293\cdot 3413$
$1000010=2\cdot 5\cdot 11\cdot 9091$
$1000011=3\cdot 333337$
$1000012=2^{2}\cdot 13\cdot 19231$
$1000013=7\cdot 373\cdot 383$
$1000014=2\cdot 3\cdot 166669$
$1000015=5\cdot 200003$
$1000016=2^{4}\cdot 62501$
$1000017=3^{2}\cdot 23\cdot 4831$
$1000018=2\cdot 500009$
$1000019=47\cdot 21277$
$1000020=2^{2}\cdot 3\cdot 5\cdot 7\cdot 2381$
$1000021=11\cdot 90911$
$1000022=2\cdot 107\cdot 4673$
$1000023=3\cdot 333341$
$1000024=2^{3}\cdot 125003$
$1000025=5^{2}\cdot 13\cdot 17\cdot 181$
$1000026=2\cdot 3^{4}\cdot 6173$
$1000027=7\cdot 19\cdot 73\cdot 103$
$1000028=2^{2}\cdot 250007$
$1000029=3\cdot 31\cdot 10753$
$1000030=2\cdot 5\cdot 100003$

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

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

6.1
(a) $x=11$, $y=-2$
(b) $x=1645$, $y=9048$

6.2
$k\in\mathbb{Z}$とする。
(a) $x=-53+121k$, $y=46-105k$
(b) $x=11+4526k$, $y=-2-823k$
(c) $x=-1645+3292k$, $y=9048-18107k$

6.3
(c)
(i) $g=7$, $x=1303$, $y=-1095$
(ii) $g=1$, $x=-381$, $y=1448$
(iii) $g=237$,$x=-8980$,$y=10063$

(e)
(c)(ii)(iii)を$x>0$になるよう解き直すと
(ii) $g=1$, $x=8006$,$y=-30427-381$
(iii) $g=237$,$x=19839059$,$y=-22231676$

6.4
(a) $x=7$, $y=-14$, $z=-1$
(b)
$a,b,c$が互いに素であること、すなわち$\gcd(\gcd(a,b),c)=1$であること。
$ax'+by'=\gcd(a,b)$の解$x',y'$と$\gcd(a,b)w+cz=1$の解$w,z$を用いて、$(x,y,z)=(wx',wy',z)$とすればよい。

(c)
$x=2124$, $y=-944$, $z=-19$

6.5
定理6.1によって$au+bv=1$は解$(u,v)=(u_1,v_1)$を常に持つから、$(x,y)=(cu_1,cv_1)$は$ax+by=a(cu_1)+b(cv_1)=c(au_1+bv_1)=c$を満たす。したがって、$ax+by=1$は常に解を持つ。なお$ax+by=c$のすべての解が$x=cu_1+bk$, $y=cv_1-ak$ ($k\in\mathbb{Z}$)で表されることは、本文と同様に示される。
$37u+47v=1$の解をなるべく小さくすると$(u,v)=(14,-11)$が得られるので、$(x,y)=(1442,-1133)$。

6.6
(a)
$x=0$または$y=0$に対して解はなく、$x\ge1$, $y\ge1$については$3x+5y\ge8$だからやはり解はない。

(b)
リストに現れないのは1,2,4,7のみの模様。証明は4について行った(a)と同様。

(c)
(i) 11
(ii) 23
(iii) 29

(d)
$ax+by$にならない最大の数は$ab-(a+b)$と思われる。
(a)と、(c)の3つについては$ab-(a+b)$で合っている。

(e)
$ax+by=ab-(a+b)$に$x\ge0$, $y\ge0$となる解が存在したとすると、$a(x-b+1)=-b(y+1)$だから、$x<b-1$、また$\gcd(a,b)=1$より$a|(y+1)$。これより$y+1=av\ge1$となる$v>0$が存在する。このとき$a(x-b+1)=-abv$より$x=b-1-bv\ge0$だから$b(1-v)\ge1$となるので$1-v\ge1$、故に$v\le0$となり$v>0$と矛盾。したがって$ax+by=ab-(a+b)$に$x\ge0$, $y\ge0$となる解は存在しない。

$c=ab-(a+b)$が$ax+by=c$となる$x\ge0$, $y\ge0$を持ち得ない最大の$c$であることを証明するには、$c=ab-(a+b)+\gamma$ ($\gamma\ge1$)に対し$ax+by=c$となる$x\ge0$, $y\ge0$が常に存在することを示せばよい。まず少し準備。

(i) 方程式$ax+by=ab-(a+b)+\gamma$において、$a,b$のいずれかが1、例えば$b=1$なら$x=0$, $y=\gamma-1\ge0$が常に解となり自明。$a=1$の時も同様。以後$a>1$, $b>1$とする。
(ii) $aX+bY=1$ ($\gcd(a,b)=1$)は定理6.1より常に$X,Y\in\mathbb{Z}$となる解を持つが、$X=bk$ ($k\in\mathbb{Z}$)となる解があったとすると、$b(ak+Y)=1$より$b|1$だから$b=1$となり$b>1$と矛盾する。したがって$X=bk+t$ ($1\le t<b$)。
(iii) $aX+bY=\gamma$ ($\gcd(a,b)=1$, $\gamma\in\mathbb{Z}$)は練習問題6.5により常に$X,Y\in\mathbb{Z}$となる解を持ち、(ii)と同様に$X=bk+t$ ($k\in\mathbb{Z}$, $1\le t<b$)であることを示せる。

方程式$ax+by=ab-(a+b)+1$を考えると、$a(x-b+1)+b(y+1)=1$。いま$aX+bY=1$の解のうち、$X<0$となる一つの解$X_1,Y_1$をとる。$Y_1>0$すなわち$Y_1\ge1$である。また(ii)により$X_1=bk+t$ ($k<0$, $1\le t<b$)と書ける。とくに$k=-1$となるように$X_1<0, Y_1\ge1$をとれる。この$X_1,Y_1$を用いれば、$-(b-1)\le X_1<0$。そこで$x-b+1=X_1$, $y+1=Y_1$とすれば、$x=X_1+b-1\ge0$かつ$y\ge0$となるから、$ax+by=ab-(a+b)+1$には$x\ge0$, $y\ge0$となる解が常に存在する。
方程式$ax+by=ab-(a+b)+\gamma$ ($\gamma>1$)についても、(iii)を用いて上の$\gamma=1$の場合と同様にすれば、$x\ge0$, $y\ge0$となる解が常に存在する。
以上により、$c=ab-(a+b)+\gamma$に対し$ax+by=c$となる$x\ge0$, $y\ge0$が常に存在する。

(f)
...

シルヴァーマン 「はじめての数論」第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$についてもいろいろ言えると思うが、面倒なのでパス。