初 等 整 数 論 講 義 第 $2$ 版

$\blacktriangleleft$ $\S\ 9.$ $1$ の $n$ 乗根  $\S\ 11.$ 原始根,指数 $\blacktriangleright$

『初等整数論講義 第 $2$ 版』目次へ



第 $1$ 章 初 等 整 数 論


 $\S\ 10.$ Fermat の定理

 $\boldsymbol{1.}$ $\left(a,\ m\right)=1$ であるとき,$x$ に $m$ を法としての一つの剰余系の値を与えるならば,$ax$ からも一つの剰余系が生ずる(定理 $1.\ 13$,証参照).特に $x$ が既約剰余系の値をとるとき $ax$ からも一つの既約剰余系が生ずる($ax$ が $m$ と素だから).
 よって $x_1$,$x_2$,$\cdots\cdots$,$x_{\varphi\left(m\right)}$ を既約剰余系とすれば,\[ax_1,\ ax_2,\ \cdots\cdots,\ ax_{\varphi\left(m\right)}\]は全体において一つずつ $x_1$,$x_2$,$\cdots\cdots$,$x_{\varphi\left(m\right)}$ と合同になるから,\[a^{\varphi\left(m\right)}x_1x_2\cdots\cdots x_{\varphi\left(m\right)}\equiv x_1x_2\cdots\cdots x_{\varphi\left(m\right)}\hphantom{m}\left(\text{mod}.\ m\right).\]$\left(x_1x_2\cdots\cdots x_{\varphi\left(m\right)},\ m\right)=1$ であるから,\[a^{\varphi\left(m\right)}\equiv1\hphantom{m}\left(\text{mod}.\ m\right).\tag{$\ 1\ $}\] 特に,法を素数 $p$ とするとき,$a$ が $p$ で割り切れないならば,$\left(a,\ p\right)=1$,$\varphi\left(p\right)=p-1$.故に次の定理を得る.
  〔定理 $\boldsymbol{1.\ 25}$〕 (Fermat の定理$p$ が素数で,$a$ は $p$ で割り切れないならば,\[a^{p-1}\equiv1\hphantom{m}\left(\text{mod}.\ p\right)\] あるいは両辺に $a$ を掛けて\[a^p\equiv a\hphantom{m}\left(\text{mod}.\ p\right)\]とすれば,$a$ が $p$ で割り切れるときにも成り立つ.
 この定理は整数論において基本的で,たえず応用されるものである.$\left(\ 1\ \right)$ はこの定理の拡張で,Euler の定理と称される.
 〔例〕 $\begin{alignat*}{2}10^6&\equiv1\hphantom{m}\left(\text{mod}.\ 7\right),&\hspace{2em}10^6-1&=999999=7\times142857.\\2^{12}&\equiv1\hphantom{m}\left(\text{mod}.\ 13\right),&\hspace{2em}2^{12}-1&=4095=13\times315.\\5^8&\equiv1\hphantom{m}\left(\text{mod}.\ 16\right),&\hspace{2em}5^8-1&=\left(5^4-1\right)\left(5^4+1\right)=624\times626\\&&&\hphantom{===}=16\times39\times626.\end{alignat*}$

  定理 $1.\ 25$ は $a$ の $p-1$ 乗が $\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ であることをいうのであるが,個々の数 $a$ に関しては,$p-1$ 乗よりも低い巾がすでに $\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ となることはあり得る.例えば $3^3\equiv1\hphantom{m}\left(\text{mod}.\ 13\right)$.
 いま $a$ の巾の中で,$a^e\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ となる最小指数を $e$ とすれば,$a^n\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ は $n$ が $e$ の倍数のときにだけ成り立つのである.なぜならば,もしも $n=qe+r$,$0\lt r\lt e$ ならば,$a^n=\left(a^e\right){}^q\hspace{0.7mm}\cdotp a^r$,したがって $a^n\equiv1$,$a^e\equiv1$から,$a^r\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ が得られるから,これは矛盾である.特に $a^{p-1}\equiv1$ であるから,$e$ は $p-1$ の約数である.このような最小正指数 $e$ を $a$ に対応する指数という.
 合同式 $\left(\ 1\ \right)$ に関しても同様である.すなわち:
 〔定理 $\boldsymbol{1.\ 26}$〕 $a$ が法 $m$ に関して指数 $e$ に対応するならば,$e$ の倍数 $k$ を指数とするときに限って $a^k\equiv1\hphantom{m}\left(\text{mod}.\ m\right)$.特に $\varphi\left(m\right)$ は $e$ の倍数である.
 また,$a^h\equiv a^k\hphantom{m}\left(\text{mod}.\ m\right)$ は $h\equiv k\hphantom{m}\left(\text{mod}.\ e\right)$ のときに限る.
 〔注意〕 $\S\ 6$($34$ 頁)に述べた分数記号と同様の意味で $a$ の負数巾を用いることも,しばしば便利である.すなわち $a^{-k}$ は $\text{mod}.\ m$ に関して $1/a^k$ を表わす.規約によって,それは $a^kx\equiv1\hphantom{m}\left(\text{mod}.\ m\right)$ の解である.いま $ne\geqq k$ とすれば $x\equiv a^{ne-k}\hphantom{m}\left(\text{mod}.\ m\right)$ であるから,\[a^{-k}\equiv a^{ne-k}\hphantom{m}\left(\text{mod}.\ m\right).\]換言すれば,$k^\prime\equiv-k\hphantom{m}\left(\text{mod}.\ e\right)$ で $k^\prime\geqq0$ ならば $a^{-k}\equiv a^{k^\prime}\hphantom{m}\left(\text{mod}.\ m\right)$.
 よって一般に $h$,$k$ が正でも負でも,$h\equiv k\hphantom{m}\left(\text{mod}.\ e\right)$ であるときは,\[a^h\equiv a^k\hphantom{m}\left(\text{mod}.\ m\right).\]また,一般に $a^ha^k\equiv a^{h+k}$,$\left(a^h\right){}^k\equiv a^{hk}\hphantom{m}\left(\text{mod}.\ m\right)$.もちろん $\left(a,\ m\right)=1$ であることを要する.
 〔問題 $\boldsymbol{1}$〕 $\text{mod}.\ m$ に関して $a$ が指数 $e$ に対応するとき $a^k$(またはそれと同類の数)は,$\left(k,\ e\right)=1$ であるときは,指数 $e$ に対応する.一般には指数 $e^\prime=e/\left(k,\ e\right)$ に対応する.
  〔解〕 $\left(k,\ e\right)=d$ と置いて,$k=k^\prime d$,$e=e^\prime d$ とする.しからば\[\left(a^k\right){}^{e^\prime}=\left(a^e\right){}^{k^\prime}\equiv1\hphantom{m}\left(\text{mod}.\ m\right).\] 逆に $\left(a^k\right){}^x\equiv1\hphantom{m}\left(\text{mod}.\ m\right)$ とすれば,$kx$ は $e$ の倍数である(定理 $1.\ 26$),すなわち $k^\prime x$ は $e^\prime$ で割り切れるが,$\left(k^\prime,\ e^\prime\right)=1$ だから,$x$ は $e^\prime$ の倍数でなくてはならない.故に $a^k$ は指数 $e^\prime$ に対応する.

 $\boldsymbol{2.}$ Fermat の定理を応用して $4n+1$ の形の素数が無限に存在することを証明することができる.
 まず $x^2+1$ の形の数の素因数は $2$ または $4n+1$ の形の素数である.
 例えば $1^2+1=2$,$2^2+1=5$,$3^2+1=2\hspace{0.7mm}\cdotp5$,$4^2+1=17$,$5^2+1=2\hspace{0.7mm}\cdotp13$,$\cdots$
 その証は次の通り.
 $x^2+1$ が素数 $p$($p\neq2$)で割り切れるとすれば,\[x^2+1\equiv0\hphantom{m}\left(\text{mod}.\ p\right),\]すなわち\[x^2\equiv-1\hphantom{m}\left(\text{mod}.\ p\right),\]故に\[x^4\equiv1\hphantom{m}\left(\text{mod}.\ p\right).\]のみならず,$x$ は指数 $4$ に対応する.さもなければ $x\equiv1$ または $x^2\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$,したがって $-1\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ で,$p\neq2$ だから,これは不可能である.
 $x$ が指数 $4$ に対応するから,$p-1$ は $4$ の倍数である.
 よって $p-1=4n$ とすれば,$p=4n+1$.
 この定理を応用して,$4n+1$ の形の素数が無限に存在することを証明するために,$p$ を $4n+1$ の形の一つの素数とし,$p$ 以下の $4n+1$ の形の素数のすべてと $2$ との累乗積の平方に $1$ を加えて\[a=\left(2\hspace{0.7mm}\cdotp5\hspace{0.7mm}\cdotp13\hspace{0.7mm}\cdotp\cdots\cdots\hspace{0.7mm}\cdotp p\right){}^2+1\]と置けば,$a$ が素数ならば,それはもちろん $4n+1$ の形で,$p$ よりも大きい素数である.また $a$ が合成数ならば,その素因数 $q$ は奇数であるから,上記の通り $q$ は $4n+1$ の形の素数でなくてはならない.しかるに $a$ は $5$,$13$,$\cdots\cdots$,$p$ では割り切れないから,$q\gt p$.いずれにしても,$p$ よりも大きくて $4n+1$ の形の素数が存在するから,これらの素数は無限に存在する.

 $\boldsymbol{3.}$ 上記 $x^2+1=\left(x-i\right)\left(x+i\right)$ はすなわち定理 $1.\ 24$ における $F_4\left(x\right)$ である.それを拡張して次の著しい定理を得る($22$ 頁参照).
 $F_m\left(x\right)$ を定理 $1.\ 24$ に掲げた多項式,$a$ を任意の整数とすれば,$F_m\left(a\right)$ の素因数は $m$ の約数または $mt+1$ の形のものである(もちろん,$m\gt1$,また $F_m\left(a\right)\neq\pm1$ と仮定する).
 $mt+1$ の形の素数は無限に存在する.
 〔証〕 定理 $1.\ 24$ によって次の恒等式が成り立つ,\[x^m-1=F_m\left(x\right)G\left(x\right).\]ここで $G\left(x\right)$ は整係数の多項式である.よって\[a^m-1=F_m\left(a\right)G\left(a\right)\]において $F_m\left(a\right)$,$G\left(a\right)$ は整数であるから,いま素数 $p$ を $F_m\left(a\right)$ の約数とすれば,$a^m-1$ は $p$ の倍数,すなわち\[a^m\equiv1\hphantom{m}\left(\text{mod}.\ p\right).\]さて,$a$ に対応する指数を $e$ とすれば(定理 $1.\ 26$),\[m=ef.\] 故に $m\gt e$ とすれば,$x^e-1$ と $F_m\left(x\right)$ とは共通の因数を有しないから,\[x^m-1=\left(x^e-1\right)F_m\left(x\right)H\left(x\right),\] $H\left(x\right)$ はもちろん整係数の多項式である.あるいは $x^e-1$ で割って\[x^{e\left(f-1\right)}+x^{e\left(f-2\right)}+\cdots\cdots+x^e+1=F_m\left(x\right)H\left(x\right).\] $x$ に $a$ を代入して,$a^e\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ を用いるならば,\begin{alignat*}{2}f&\equiv F_m\left(a\right)H\left(a\right)&&\\[2mm]&\equiv0&&\left(\text{mod}.\ p\right).\end{alignat*} 故に $p$ は $f$ の約数,したがって $m=ef$ の約数である.
 次に $m=e$ とすれば,$m$ がすなわち $a$ に対応する最小指数であるから,$m$ は $p-1$ の約数である.よって $p-1=mt$.すなわち $p=mt+1$.
 特に $a$ を $m$ の倍数(または $m$ に含まれるすべての相異なる素数の倍数)とすれば,$a^m\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ によって $\left(a,\ p\right)=1$ であるから,$p$ は $m$ の約数であり得ない.故に必ず $mt+1$ の形である.
 例えば $F_{12}\left(x\right)=x^4-x^2+1$ において,$a=6$ とすれば,\[F_{12}\left(6\right)=6^4-6^2+1=1261=13\times97\]で $13\equiv1$,$97\equiv1\hphantom{m}\left(\text{mod}.\ 12\right)$.
 上文では $F_m\left(a\right)\neq\pm1$ と仮定した.$F_m\left(a\right)=\pm1$ になるような $a$ があっても,それは有限個に限る(方程式 $F_m\left(x\right)=\pm1$ の根)から,その他の $a$ をとればよい.
 これによって $m$ を任意の整数とするとき,$mt+1$ の形の素数が実際存在することが証明された.
 さて $p=mt+1$ とするとき,$mp$ を $m$ に代用すれば,$p^\prime=mpt^\prime+1$ の形の素数 $p^\prime$ が存在する.$p^\prime$ はやはり $mt+1$ の形で,かつ $p$ よりも大きい.すなわち $mt+1$ の形の素数に最大のものがないのだから,かような素数は無限に存在する.

 附記 循 環 小 数
 既約な真分数 $m/n$ において,分母 $n$ が $2$ および $5$ で割り切れないとき,すなわち $\left(10,\ n\right)=1$ であるとき,$n$ を法として,$10$ が指数 $e$ に対応するとする.しからば\[10^e\equiv1\hphantom{m}\left(\text{mod}.\ n\right).\] いま\[10^e-1=na\]と置けば,\[\frac{m}{n}=\frac{ma}{na}=\frac{ma}{10^e-1}=\frac{ma}{10^e}+\frac{ma}{10^{2e}}+\frac{ma}{10^{3e}}+\cdots\cdots\]仮定によって $0\lt m\lt n$,したがって $ma\lt na\lt 10^e$.故に $m/n$ は $e$ 桁の周期を有する循環小数に展開される.逆に $m/n$ が $e$ 桁の周期をもって循環する小数に等しいならば,\[\frac{m}{n}=\frac{c}{10^e}+\frac{c}{10^{2e}}+\cdots\cdots=\frac{c}{10^e-1},\]したがって $10^e-1=na$,($c=ma$)である.故に
 〔定理〕 $m/n$ は循環小数に展開され,循環の一節の数字を $e$ 桁とすれば,$e$ は $10^e\equiv1\hphantom{m}\left(\text{mod}.\ n\right)$ なる最小正指数である.$e$ は $\varphi\left(n\right)$ の約数で,それは分母 $n$ のみによって定まる.
 $n=p^\alpha q^\beta\cdots\cdots$ を $n$ の素数巾への分解とし,$p^\alpha$,$q^\beta$,$\cdots\cdots$ を法として $10$ に対応する指数を $e_1$,$e_2$,$\cdots\cdots$ とすれば,$n$ を法としての指数 $e$ は $e_1$,$e_2$,$\cdots\cdots$ の最小公倍数に等しい.

 次に $\left(10,\ n\right)\neq1$ のとき,$n=2^u5^vn^\prime$,$\operatorname{Max}\!\!\ \left(u,\ v\right)=k$ とし,$10^km/n$ を既約分数に化して $m^\prime/n^\prime$ を得るとする.しからば $\left(10,\ n^\prime\right)=1$,したがって $n^\prime$ を法として $10$ に対応する指数を $e$ とすれば,$m^\prime/n^\prime$ は $e$ 桁の周期を有する循環小数に等しい.$m/n$ も同様であるが,循環が小数第 $k+1$ 位から始まる.
 $n^\prime=1$ ならば $m/n$ は有限小数に等しい.
 〔例 $1$〕 $n=7$ とすれば,$10$ は指数 $6$ に対応する(すなわち $10$ は素数 $7$ の原始根である.$\S\ 11$).故に $7$ を分母とする既約分数は分子がなんであっても,$6$ 位の周期を有する循環小数に展開される.

$\hphantom{1}\!$$1\!$$4\!$$2\!$$8\!$$5\!$$7\!$$\hphantom{1}\!$
$7$$\raise{2mu}{)}$$1\!$$0\!$$0\!$$0\!$$0\!$$0\!$$0\!$
$7$
$3$
$2\!$$8$
$2$
$1\!$$4$
$6$
$5\!$$6$
$4\!$
$3\!$$5$
$5$
$4\!$$9$
$1$
   \begin{alignat*}{2}\frac{1}{7}&=0.\dot{1}4285\dot{7},&\hspace{1cm}\frac{6}{7}&=0.\dot{8}5714\dot{2},\\[1em]\frac{3}{7}&=0.\dot{4}2857\dot{1},&\hspace{1cm}\frac{4}{7}&=0.\dot{5}7142\dot{8},\\[1em]\frac{2}{7}&=0.\dot{2}8571\dot{4},&\hspace{1cm}\frac{5}{7}&=0.\dot{7}1428\dot{5}.\end{alignat*}

 上記の循環節は $142857$ の $1$,$3$,$2$,$6$,$4$,$5$ 倍であるが,それらは $142857$ なる六つの数字の循環置換によって得られるものである.
 循環節を折半して加え合わせると $999$ になる.$142+857=999$ 等.
 ここでは $e=6$ だから,$10^3\equiv-1\hphantom{m}\left(\text{mod}.\ 7\right)$.故に上記の割り算で第三段の剰余が $6\equiv-1\hphantom{m}\left(\text{mod}.\ 7\right)$ である.$1/7$ と $6/7$ との和が $1$ であるから上記のような現象が生ずる.
 多くの読者はこのような数字の遊戯に興味を感ずるであろうと信ずる.

 〔例 $2$〕 分母を $13$ とする.
割り算から $10^6\equiv1\hphantom{m}\left(\text{mod}.\ 13\right)$,$e=6$.
故に分母 $13$ なる既約分数は $6$ 位の循
環節を有する小数に展開される.
 割り算から見えるように
   
$\hphantom{1}\!$$0\!$$7\!$$6\!$$9\!$$2\!$$3\!$$\hphantom{1}\!$
$13$$\raise{2mu}{)}\!$$1\!$$0\!$$0\!$$0\!$$0\!$$0\!$$0\!$
$9\!$$1\!$
$9$
$7\!$$8\!$
$1\!$$2$
$1\!$$1\!$$7\!$
$3$
$2\!$$6\!$
$4$
$3\!$$9\!$
$1$
\[10\equiv10,\ \ 10^2\equiv9,\ \ 10^3\equiv12,\ \ 10^4\equiv3,\ \ 10^5\equiv4,\ \ 10^6\equiv1\hphantom{m}\left(\text{mod}.\ 13\right).\\\begin{alignat*}{3}\frac{1}{13}&=0.\dot{0}7692\dot{3},&\hspace{1cm}\frac{10}{13}&=0.\dot{7}6923\dot{0},&\hspace{1cm}\frac{9}{13}&=0.\dot{6}9230\dot{7},\\[1em]\frac{12}{13}&=0.\dot{9}2307\dot{6},&\hspace{1cm}\frac{3}{13}&=0.\dot{2}3076\dot{9},&\hspace{1cm}\frac{4}{13}&=0.\dot{3}0769\dot{2}.\end{alignat*}\] この場合にも第三段で剰余 $12$($\equiv-1$,$\text{mod}.\ 13$)が出たところで割り算を止めてもよかったのである.あとの三つの剰余は $-10\equiv3$,$-9\equiv4$,$-12\equiv1\hphantom{m}\left(\text{mod}.\ 13\right)$ で,商の数字は $999-76=923$ である.
 この中にない分子,例えば $2$ をとれば\begin{alignat*}{1}&2\hspace{0.7mm}\cdotp10\equiv7,\ \ 2\hspace{0.7mm}\cdotp10^2\equiv18\equiv5,\ \ 2\hspace{0.7mm}\cdotp10^3\equiv24\equiv11,\ \ 2\hspace{0.7mm}\cdotp10^4\equiv6,\\&2\hspace{0.7mm}\cdotp10^5\equiv8\hphantom{m}\left(\text{mod}.\ 13\right).\end{alignat*} よって\begin{alignat*}{3}\frac{2}{13}&=0.\dot{1}5384\dot{6},&\hspace{1cm}\frac{7}{13}&=0.\dot{5}3846\dot{1},&\hspace{1cm}\frac{5}{13}&=0.\dot{3}8461\dot{5},\\[1em]\frac{11}{13}&=0.\dot{8}4615\dot{3},&\hspace{1cm}\frac{6}{13}&=0.\dot{4}6153\dot{8},&\hspace{1cm}\frac{8}{13}&=0.\dot{6}1538\dot{4}.\end{alignat*} $2/13$ の循環節 $153846$ は $76923\times2$,その他は循環置換によって得られる.
 〔例 $3$〕 例 $1$,例 $2$ によれば $91=7\hspace{0.7mm}\cdotp13$ を法としても $10$ は指数 $6$ に対応する.故に $91$ を分母とする既約分数は,$6$ 位の循環節を有する小数に展開される.
 $\begin{alignat*}{1}\frac{1}{91}&=0.\dot{0}1098\dot{9},\\[1em]\frac{10}{91}&=0.\dot{1}0989\dot{0},\\[1em]\frac{9}{91}&=0.\dot{0}9890\dot{1},\\[1em]\frac{90}{91}&=0.\dot{9}8901\dot{0},\\[1em]\frac{81}{91}&=0.\dot{8}9010\dot{9},\\[1em]\frac{82}{91}&=0.\dot{9}0109\dot{8},\end{alignat*}$
$\hphantom{1}\!$$0\!$$1\!$$0\!$$9\!$$8\!$$9\!$$\hphantom{1}\!$
  $91$$\raise{2mu}{)}\!$$1\!$$0\!$$0\!$$0\!$$0\!$$0\!$$0\!$
$9\!$$1$
$9\!$$0\!$$0\!$
$8\!$$1\!$$9$
$8\!$$1\!$$0\!$
$7\!$$2\!$$8$
$8\!$$2\!$$0\!$
$8\!$$1\!$$9\!$
$1$
分  子
$1)\ $$1$,$10$,$9$,$90$,$81$,$82$
$2)\ $$2$,$20$,$18$,$89$,$71$,$73$
$3)\ $$3$,$30$,$27$,$88$,$61$,$64$
$4)\ $$4$,$40$,$36$,$87$,$51$,$55$
$5)\ $$5$,$50$,$45$,$86$,$41$,$46$
$6)\ $$6$,$60$,$54$,$85$,$31$,$37$
$7)\ $$8$,$80$,$72$,$83$,$11$,$19$
$8)\ $$12$,$29$,$17$,$79$,$62$,$74$
$9)\ $$15$,$59$,$44$,$76$,$32$,$47$
$10)\ $$16$,$69$,$53$,$75$,$22$,$38$
$11)\ $$23$,$48$,$25$,$68$,$43$,$66$
$12)\ $$24$,$58$,$34$,$67$,$33$,$57$
循環節
$010989$
$021978$
$032967$
$043956$
$054945$
$065934$
$087912$
$131868$
$164835$
$175824$
$252747$
$263736$
$91$ を分母とする既約真分数 $\varphi\left(91\right)=\varphi\left(7\right)\varphi\left(13\right)=72$ 個が六つずつ $12$ 群に分かれ,各群に属する六つの既約真分数の小数への展開における循環の一節は同一の六つの数字の循環置換である.
 表の説明 $1)$ の意味は明白であろう.$2)$ に掲げた分子は $1)$ の数の $2$ 倍を $91$ で割った剰余で,循環節の欄に掲げた $021978$ は $1)$ のところの $010989$ に $2)$ の左端の $2$ を掛けたものである.その他の行も同様である.例えば $11)$ は $1)$ の各数の $23$ 倍を $91$ で割った剰余 $10\times23\equiv48$,$9\times23\equiv25$.等等で,循環節は $252747=10989\times23$.この数字を一桁ずつ循環的にずらして\[\frac{48}{91}=0.\dot{5}2747\dot{2},\ \ \frac{25}{91}=0.\dot{2}7472\dot{5},\ \cdots\cdots\] どの行でも初めの三つの分子を $91$ から引いた残りが後の三つの分子である($e$ が偶数のとき,いつでも同様).






$\blacktriangleleft$ $\S\ 9.$ $1$ の $n$ 乗根  $\S\ 11.$ 原始根,指数 $\blacktriangleright$

『初等整数論講義 第 $2$ 版』目次へ


 ページトップへ inserted by FC2 system