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

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

9.1
(a)
$9^{794}=(9^{72})^{11}\cdot9^2\equiv9^2\pmod{73}=81\equiv8\pmod{73}$

(b)
$x^{86}=(x^3)^{28}\cdot x^2\equiv x^22 \pmod{29}\equiv6\pmod{29}$から、$x\equiv8,21\pmod{29}$


(c)
$x^{39}=(x^3)^{12} x^3\equiv x^3\pmod{13}\equiv3\pmod{13}$で、$x$=0〜12の中に、3乗して3と合同になる数はないので解なし。

9.2 (Wilsonの定理)
(a)
$p=2$のとき$1!\equiv1\pmod{2}$
$p=3$のとき$2!\equiv2\pmod{3}$
$p=5$のとき$4!\equiv4\pmod{5}$
$p=7$のとき$6!\equiv6\pmod{7}$
$p=11$のとき$10!\equiv10\pmod{11}$
$p=13$のとき$12!\equiv12\pmod{13}$
$p$が素数なら$(p-1)!\equiv -1 \pmod{p}$が予想される。 

(b)
まず次の2つの補題を証明する。

補題1：$p$を素数とする。$x^2\equiv1\pmod{p}$と、$x\equiv1\mbox{または}-1\pmod{p}$は同値。
(証明) $x^2-1=(x-1)(x+1)\equiv0\pmod{p}$なので$p|(x-1)(x+1)$。したがって補題7.1より$x-1\equiv0\pmod{p}$または$x+1\equiv0\pmod{p}$。よって$x\equiv1\mbox{または}-1\pmod{p}$。逆は明らか。

補題2：$p$が素数、$\gcd(a,p)=1$なら、$ax\equiv1\pmod{p}$の解となる$x=a^{-1}$ (つまり既約剰余系での乗法の逆元)が合同を除きただ一つ定まる。
（証明）定理6.1で$b=p$, $g=1$とすれば、$ax\equiv1\pmod{p}$の解$a^{-1}$が存在することがわかる。別の解$x=a'$もあったとすると、$a(a-1-a')\equiv0\pmod{p}$だが、$a\not\equiv0\pmod{p}$より$a-1-a'\equiv0\pmod{p}$。よって$a'\equiv a-1\pmod{p}$。特に補題1により、$a\equiv1\mbox{または}-1\pmod{p}$のときかつその時に限り、$a^{-1}\equiv a\pmod{p}$となり自分自身が逆元となる。

(a)の予想(Wilsonの定理)の証明：
$p=2$の時は明らか。
$p\geq3$の時、補題2により、$\{2,3,4....(p-2)\}$の各元に、互いに乗法の逆元となる元がただ一つ存在するから、これら$(p-3)$個(偶数個)の元は、$ab\equiv1\pmod{p}$となる2元$a$と$b$を組にして、$(p-3)/2$組に分けることが出来る。したがって、$2\cdot3\cdot4\cdot\cdots(p-2)\equiv1^{(p-3)/2}=1 \pmod{p}$だから、$(p-1)!=1\cdot2\cdot3\cdot4\cdot\cdots(p-2)(p-1)\equiv1\cdot1\cdot(p-1)=p-1\equiv-1 \pmod{p}$。

9.3
(a) 計算機で$m=100$まで計算してみると、$m$が素数のとき$(m-1)!\equiv-1\pmod{m}$ (これはFermatの小定理)、$m=4$のとき$3!\equiv2\pmod{4}$、$m$が4でない合成数のとき$(m-1)!\equiv0\pmod{m}$の模様。

(b) 多分できるが計算量的に非現実的だろう。

9.4
Fermatの小定理およびその対偶「$a^{m-1}\not\equiv1 \pmod{m}$となる整数$a\not\equiv0\pmod{m}$が存在すれば$m$は合成数」は成り立つが、Fermatの小定理の逆は一般に成り立たない(練習問題10.3と第19章を参照)。
(a) 結論付けられる。
(b) 結論付けられる。
(c) 結論付けられない。