シルヴァーマン 「はじめての数論」第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により解はない。