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

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

11.1
(a)
97は素数だから$\varphi(97)=97-1=96$。

(b)
$8800=2^5\cdot5^2\cdot11$。各素数冪は互いに素だから、$\varphi(8800)=\varphi(2^5)\varphi(5^2)\varphi(11)=(2^5-2^4)(5^2-5^1)(11^1-11^0)=3200$。


11.2
(a)
練習問題10.1で示した。

(b)
$p_i$ ($i\in\mathbb{N}$)を奇素数として、一般に$m=2^{k_0}p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}$ ($n\geq0$, $k_0\geq0$, $k_1,\cdots k_n\geq1$)と素因数分解される。$\varphi(m)=\varphi(2^{k_0})\varphi(p_1^{k_1})\cdots\varphi(p_n^{k_n})$なので、$k_0\geq2$なら$\varphi(2^{k_0})$が偶数であることと(a)とから、$k_0\geq2$かつ$n=1$、または、$n\geq2$ならば$4\mid\varphi(m)$。
残る可能性として、(i) $k_0\leq1$, $n=1$, (ii) $n=0$の2つがありうる。(1)のときは$p$を奇素数、$k\geq1$として$m=p^k$または$m=2p^k$だが、$\varphi(2)=1$なのでいずれにせよ$\varphi(m)=p^{k-1}(p-1)$。常に$4\nmid p^{k-1}$なので、$p-1\equiv2 \pmod{4}$すなわち$p\equiv3\pmod{4}$なら$4\nmid \varphi(m)$で、$p\equiv1\pmod{4}$なら$4\mid\varphi(m)$。(ii)のときは$k_0=0$なら$\varphi(m)=\varphi(2)=1$、$k_0=1$なら$\varphi(m)=\varphi(4)=2$、$k_0\geq3$なら$\varphi(2^{k_0})=2^{k_0-1}$より$4\mid\varphi(m)$。
以上により、$4\nmid\varphi(m)$となる$m$は2,4と、$p$を$p\equiv3\pmod{4}$となる素数として$p^k$, $2p^k$ ($k\geq1$)。

11.3
$m$の素因数分解を$m=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}$とすると、各素数冪は互いに素だから、$\varphi(m)=\varphi(p_1^{k_1})\varphi(p_2^{k_2})\cdots\varphi(p_r^{k_r})$
$=(p_1^{k_1}-p_1^{k_1-1})(p_2^{k_2}-p_2^{k_2-1})\cdots(p_r^{k_r}-p_r^{k_r-1})$
$=p_1^{k_1}p_2^{k_2}\cdots p_r^{k_r}(1-1/p_1)(1-1/p_2)\cdots(1-1/p_r)$
$10000000=2^7\cdot5^7$より$\varphi(10000000)=10000000\cdot(1/2)\cdot(4/5)=4000000$。

11.5
(a)
$x=59+63n$ ($n\in\mathbb{N}$)。$0\leq x<63$の範囲では$x=59$。

(b)
$x=125803+3219n$ ($n\in\mathbb{N}$)。$0\leq x<3219$の範囲では$x=262$。

(c)　
最初の2式を解いて$x\equiv26\pmod{84}$。$x=26+84z\equiv8\pmod{13}$を解いて、 $z\equiv10\pmod{13}$により、$x=26+84\cdot10\equiv866\pmod{1092}$。


11.6
$x\equiv2 \pmod{3}$, $x\equiv3 \pmod{5}$, $x\equiv2 \pmod{7}$を解く。最初の2式を解いて $x\equiv8 \pmod{15}$。$x=8+15z\equiv2 \pmod{7}$を解いて、 $z\equiv1 \pmod{7}$により、$x=8+15\cdot1\equiv23 \pmod{105}$。

11.7
$x\equiv1 \pmod{2}$, $x\equiv1 \pmod{3}$, $x\equiv1 \pmod{4}$, $x\equiv1 \pmod{5}$, $x\equiv1 \pmod{6}$, $x\equiv0 \pmod{7}$を解く。互いに素な底2,3,5,7をとって、まず$x\equiv1 \pmod{2}$, $x\equiv1 \pmod{3}$, $x\equiv1 \pmod{5}$, $x\equiv0 \pmod{7}$を解くと、$x\equiv91 \pmod{210}$。$91\equiv1 \pmod{6}$だが、$91\not\equiv1 \pmod{4}$。$x\equiv91 \pmod{210}$, $x\equiv1 \pmod{4}$を解く。$n,m\in\mathbb{Z}$として、$x=91+210n=1+4m$より、$105n=2m-45$。すなわち$105n=-45\equiv1 \pmod{2}$なので$n=1$。したがって$x=301 \pmod{420}$だから、最小個数は310個。


11.9
任意の2つ、例えば$x\equiv a_1 \pmod{m_1}$と$x\equiv a_2 \pmod{m_2}$を解き、その解と第3式を連立させればよい。すなわちまず、$x=m_1x_1+a_1\equiv a_2 \pmod{m_2}$から、$m_1x_1\equiv a_2-a_1\pmod{m_2}$を解き、解$x_1$ ($0\leq x_1<m_2$)を得る。これより、$x\equiv m_1x_1+a_1 \pmod{m_1m_2}$。この式と$x\equiv a_3 \pmod{m_3}$を連立して、$x=m_1m_2x_2+m_1x_1+a_1\equiv a_3 \pmod{m_3}$から、$m_1m_2x_2\equiv a_3-(m_1x_1+a_1)\pmod{m_3}$を解き、解$x_2$ ($0\leq x_2<m_3$)を得る。以上により、$x=m_1m_2x_2+m_1x_1+a_1 \pmod{m_1m_2m_3}$。
より多くの合同式でも以上を繰り返せば良い。$m_1,m_2,\cdots,m_r$の、どの2つも互いに素でなければならない。

11.10
(1) $\varphi(n)$が素数の時：
練習問題11.2(a)により$\varphi(n)$は$n\geq3$では偶数だから、$\varphi(n)$が素数なら$\varphi(n)=2=1\cdot2$しかない。$n=lm$として、$\varphi(l)=1$のとき$l=1$ or $2$。$\varphi(m)=2$のとき$m=p^k$ ($k\geq1$)として$\varphi(m)=p^k-p^{k-1}=p^{k-1}(p-1)=2$だから、$p^{k-1}=2$かつ$p-1=1$、または、$p^{k-1}=1$かつ$p-1=2$。したがって、$(p,k)=(2,2)$または$(3,1)$なので、$m=3$ or $4$。$\varphi(n)=\varphi(l)\varphi(m)$となるには$\gcd(l,m)=1$でなければならないから、可能な組み合わせは、$n=3,4,6$。

(2) $\varphi(n)$が素数の2乗の時：
$\varphi(n)$が素数なら$\varphi(n)=4=1\cdot2\cdot2=1\cdot4$しかない。まず$\varphi(n)=4=1\cdot2\cdot2$と考えると、$n=jlm$として、$\varphi(j)=1$に対し$j=1$ or $2$。
$\varphi(l)=\varphi(m)=2$に対し(1)と同様に$l,m=3, 4$, or $6$。$\gcd(j,l,m)=1$でなければならないから、可能な組み合わせは$n=12$。次に、$\varphi(n)=4=1\cdot4$と考えると、$n=lm$として、$\varphi(l)=1$に対し$l=1$ or $2$。$\varphi(m)=4$に対し$m=p^k$ $(k\geq1$)として$\varphi(m)=p^k-p^{k-1}=p^{k-1}(p-1)=4$だから、$p^{k-1}=1$かつ$p-1=4$、または、$p^{k-1}=4$かつ$p-1=1$、または、$p^{k-1}=2$かつ$p-1=2$。最後の場合は解がない。したがって、$(p,k)=(5,1)$または$(2,3)$なので、$m=5$ or $8$。$\gcd(l,m)=1$でなければならないから、可能な組み合わせは$n=lm=5, 8$, or $10$。
以上をまとめて、$n=5, 8, 10$ or $12$。

11.11
$160=2^5\cdot5$である。
$160=2^4\cdot10=\varphi(2^5)\varphi(11)=\varphi(352)$、$2^4\cdot10=\varphi(17)\varphi(11)=\varphi(187)$。
$160=1\cdot2^4\cdot10=\varphi(2)\varphi(17)\varphi(11)=\varphi(374)$。
$160=2^2\cdot2^2\cdot10=\varphi(2^3)\varphi(5)\varphi(11)=\varphi(440)$、$2^2\cdot2^2\cdot10=\varphi(12)\varphi(5)\varphi(11)=\varphi(660)$。
$160=2\cdot2^3\cdot10=\varphi(3)\varphi(2^4)\varphi(11)=\varphi(528)$
$160=2^3\cdot20=\varphi(2^4)\varphi(52)=\varphi(400)$。
$160=2\cdot2^2\cdot20=\varphi(3)\varphi(2^3)\varphi(5^2)=\varphi(600)$。
$160=2^2\cdot40=\varphi(5)\varphi(41)=\varphi(205)$、$2^2\cdot40=\varphi(2^3)\varphi(41)=\varphi(328)$、$2^2\cdot40=\varphi(10)\varphi(41)=\varphi(410)$、$2^2\cdot40=\varphi(12)\varphi(41)=\varphi(492)$。
まとめると、187, 205, 328, 352, 374, 400, 410, 440, 492, 528, 600, 660の12個で全て。

(a)
$1000=2^3\cdot5^3$。この因数の中で、Euler関数の値域になるのは偶数なので、さらに絞り込むと、$1=\varphi(2)$, $2=\varphi(2^2)=\varphi(3)=\varphi(2\cdot3)$,$2^2=\varphi(5)=\varphi(2^3)=\varphi(2\cdot5)$, $2^3=\varphi(2^4)$, $2\cdot5=\varphi(11)$, $2^2\cdot5=\varphi(5^3)$, $2^3\cdot5=\varphi(41)$,  $2^2\cdot5^2=\varphi(101)$,  $2\cdot5^3=\varphi(251)$,  $2^2\cdot5^3=\varphi(54)$なので、$n$を割る候補の素数は2, 3, 5, 11, 41, 101, 251。

(b)
$1000=1\cdot2\cdot500=\varphi(2^2)\varphi(5^4)=\varphi(2500)$
$1000=1\cdot2\cdot500=\varphi(3)\varphi(5^4)=\varphi(1875)$
$1000=1\cdot2\cdot500=\varphi(2)\varphi(3)\varphi(5^4)=\varphi(3750)$
$1000=1\cdot4\cdot500=\varphi(2^3)\varphi(251)=\varphi(2008)$
$1000=1\cdot4\cdot500=\varphi(5)\varphi(251)=\varphi(1255)$
$1000=1\cdot4\cdot500=\varphi(2)\varphi(5)\varphi(251)=\varphi(2510)$
$1000=1\cdot10\cdot100=\varphi(11)\varphi(5^3)=\varphi(1375)$
$1000=1\cdot10\cdot100=\varphi(11)\varphi(101)=\varphi(1111)$
$1000=1\cdot10\cdot100=\varphi(2)\varphi(11)\varphi(5^3)=\varphi(2750)$
$1000=1\cdot10\cdot100=\varphi(2)\varphi(11)\varphi(101)=\varphi(2222)$
$1000=1\cdot2\cdot2\cdot250=\varphi(2^2)\varphi(3)\varphi(251)=\varphi(3012)$

となり、$n=1111, 1255, 1375, 1875, 2008, 2222, 2500, 2510, 2750, 3012, 3750$。

11.12
(a) $n=2^m$ ($m\in\mathbb{N}$)
(b) $n=2^{m_1}\cdot3^{m_2}$ ($m_1,m_2\in\mathbb{N}$)
(c) 存在しない。


11.13
(a) 
$2^{1000}\equiv9376 \pmod{10000}$
$3^{1000}\equiv1 \pmod{10000}$ 
$4^{1000}\equiv9376 \pmod{10000}$
$5^{1000}\equiv625 \pmod{10000}$
$6^{1000}\equiv9376 \pmod{10000}$
$7^{1000}\equiv1 \pmod{10000}$
$8^{1000}\equiv9376 \pmod{10000}$
$9^{1000}\equiv1 \pmod{10000}$
$10^{1000}\equiv0 \pmod{10000}$


(b)
(1) $a\equiv0 \pmod{10}$のとき$a^{1000}\equiv0 \pmod{10000}$。
(2) $a\equiv5 \pmod{10}$のとき$a^{1000}\equiv625 \pmod{10000}$。
(3) $a\equiv1,3,7,9\pmod{10}$のとき$a^{1000}\equiv1 \pmod{10000}$。
(4) $a\equiv2,4,6,8\pmod{10}$とき$a^{1000}\equiv9376 \pmod{10000}$。

(c)
二項定理(第36章)を使えば単純：
$a\equiv l\pmod{10}$ ($0\leq l\leq9$)とすると、$a=l+10k$ ($k\in\mathbb{Z}$)。$a^{1000}=(l+10k)^{1000}=l^{1000}+10000kl^{999}+49950000k^2l^{998}+166167000000k^3l^{997}+((10k)^4=10000k^4\mbox{以上の冪の項})\equiv l^{1000}\pmod{10000}$
(a)と、自明な$0^{1000}\equiv0 \pmod{10000}$, $1^{1000}\equiv1 \pmod{10000}$とから、(b)が従う。

第11章までの知識でなんとかしようと思うと...：
(1) $a\equiv0 \pmod{10}$のときは$a=10k$ ($k\in\mathbb{Z}$)なので$a^{1000}=10000\cdot10^{996}k^{1000}\equiv0\pmod{10000}$。

(2) $a\equiv5 \pmod{10}$のとき$a^{4m}\equiv625\pmod{4m}$ ($m\in\mathbb{N}$)であることを数学的帰納法で示す。$a=5+10k$ ($k\in\mathbb{Z}$)として、$m=1$のとき$a^4=625+4\cdot10k\cdot5^3+6\cdot(10k)^2\cdot25+4\cdot(10k)^3\cdot5+(10k)^4=625+5000k(k+1)(2k^2+2k+1)$
で、$k$と$k+1$のいずれかは偶数だから$5000k(k+1)\equiv0\pmod{10000}$となり$a^4\equiv625\pmod{10000}$。
$m$では$a^{4m}=a^4a^{4(m-1)}\equiv625\cdot625\equiv625\pmod{10000}$。

(3) $a\equiv1,3,7,9 \pmod{10}$のとき
(4) $a\equiv2,4,6,8 \pmod{10}$のとき
...