第 $1$ 章 初 等 整 数 論
$\S\ 11.$ 原 始 根，指 数
$\boldsymbol{1.}$ Fermat の定理によれば，$p$ が素数で，$a$ が $p$ で割り切れないとき，\[a^{p-1}\equiv1\hphantom{m}\left(\text{mod}.\ p\right)\]である．特に，$a$ が $p-1$ よりも小さい正指数では，このような合同式に適合しないとき（$a$ が指数 $p-1$ に対応するとき），$a$ を $p$ を法としての原始根という．または $p$ の原始根と略称する．この定義の意味を理解するには，合同式 $x^{p-1}\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ を方程式 $x^{p-1}=1$ と比較して考察するとよい．しからば，$p$ を法としての原始根は，あたかも $1$ の原始 $p-1$ 乗根に類するものである．$a^e\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ で，かつ $e$ よりも小さい正指数では，このような合同式が成り立たないならば，$e$ は $p-1$ の約数であることはすでに述べた（定理 $1.\ 26$）．これは $1$ の原始 $e$ 乗根に相当するものである．故にこのような $a$ を，$p$ を法としての原始 $e$ 乗根と名づけるのが適当である．指数が $p-1$ である場合に，特にそれを略して単に原始根というのである．本節で述べることは，合同式 $x^{p-1}\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ の解と方程式 $x^{p-1}=1$ の解とが平行であることを主眼とするのである．
まず原始根が必ず存在することを証明しなくてはならない．いま $a$ を $p$ で割り切れない任意の整数として，$a$ の巾は $m$ 乗巾に至って初めて $a^m\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ となるとする．すなわち $m$ を $a$ に対応する指数とする．しからば $\left(a^k\right){}^m=\left(a^m\right){}^k\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ であるから，\[a^0\left(=1\right),\ \ a,\ a^2,\ \cdots\cdots,\ a^{m-1}\tag{$\ 1\ $}\]は合同式\[x^m\equiv1\hphantom{m}\left(\text{mod}.\ p\right)\tag{$\ 2\ $}\]の解であるが，これらは互いに不合同である．
$a^h\equiv a^k\hphantom{m}\left(\text{mod}.\ p\right)$，$h\gt k$ とすれば，$a^{h-k}\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$，したがって $h-k$ は $m$ の倍数であることを要するから，$h$，$k$ が $0$ から $m-1$ までの中の指数では不可能である．
故に $\left(\ 1\ \right)$ の $m$ 個の数がすなわち合同式 $\left(\ 2\ \right)$ のすべての解である（定理 $1.\ 15$）．
さて $m=p-1$ ならば，$a$ がすでに原始根である．もしも $m\lt p-1$ ならば，$m$ よりも大きい指数に対応する数が必ず求められることを示そう．そうすれば，ついには原始根に到達することになるから，われわれの目的は達せられるのである．
$m\lt p-1$ ならば $\left(\ 1\ \right)$ の各数と合同でない整数（$p$ で割り切れない整数）が存在する．その一つを $b$ とし，$b$ は指数 $n$ に対応するものとする（$n\gt1$）．
$\text{i}$ $)$ $\left(m,\ n\right)=1$ ならば，$ab$ は指数 $mn$ に対応する．まず $\left(ab\right){}^{mn}=\left(a^m\right){}^n\hspace{0.7mm}\cdotp\left(b^n\right){}^m\equiv1^n\hspace{0.7mm}\cdotp1^m\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$．また逆に $\left(ab\right){}^x\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ とすれば，$\left(ab\right){}^{xm}\equiv1$．仮定によって $a^m\equiv1$，故に $b^{xm}\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$，したがって $xm$ は $n$ の倍数，したがって $\left(m,\ n\right)=1$ によって，$x$ は $n$ の倍数である．同様に $\left(ab\right){}^{xn}\equiv1$ から $x$ は $m$ の倍数，すなわち $x$ は $m$，$n$ の公倍数，したがってその最小公倍数 $mn$ の倍数でなければならない．故に $ab$ は指数 $mn$ に対応する，すなわち $ab$ は $m$ よりも大きい指数に対応する．
$\text{ii}$ $)$ $\left(m,\ n\right)=d\gt1$ ならば $m$，$n$ の最小公倍数を $l$ とするとき，$l=mn/d=m_0n_0$ と置いて，$m_0$ は $m$ の約数，$n_0$ は $n$ の約数でかつ $\left(m_0,\ n_0\right)=1$ にすることができる（$\S\ 4$，問題 $11$）．
さて $a^{m/m_0}$ は指数 $m_0$ に対応し，$b^{n/n_0}$ は指数 $n_0$ に対応するから，$\text{i}$ $)$ によってその積 $a^{m/m_0}\hspace{0.7mm}\cdotp b^{n/n_0}$ は指数 $m_0n_0$，すなわち $l$ に対応する．さて $n$ は $m$ の約数ではない．
$n$ が $m$ の約数ならば，$b^m\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$，したがって $b$ は合同式 $\left(\ 2\ \right)$ の解となり，$b$ に関する仮定に矛盾する．
故に $l\gt m$．故にこの場合にも，$m$ より大きい指数に対応する数が得られたのである．
これによって原始根の存在が確定し，同時に実際原始根を求める方法が示されたのである（補遺 $6$ 参照）．
〔例〕 $p=41$．
$a=2$ とすれば，\begin{alignat*}{2}&2^2=4,\ 2^3=8,\ 2^4=16,\ 2^5&&=32\equiv-9,\ 2^6\equiv-18,\ 2^7\equiv-36\equiv5,\ 2^8\equiv10,\\[1mm]&2^9\equiv20,\ 2^{10}\equiv40\equiv-1.&&\ \therefore\hphantom{\therefore}2^{20}\equiv1.\end{alignat*}（$2^{11}$ から $2^{20}$ までは上記 $2$ から $2^{10}$ までの剰余の符号を変えたものと合同である．）
故に $2$ は指数 $20$ に対応するから，原始根でない．
上記 $2$ の巾の中にない（$2$ の巾と合同でない）数の中で最も小さい $3$ をとって見る．\[3^2=9,\ \ 3^3=27,\ \ 3^4=81\equiv-1.\hspace{1cm}3^8\equiv1.\] 故に $3$ は指数 $8$ 対応する．
さて $2^{\displaystyle\small\raise{0.5em}\frac{20}{5}}=2^4$ は指数 $5$ に対応する．故に $2^4\hspace{0.7mm}\cdotp3=48\equiv7$ は指数 $5\hspace{0.7mm}\cdotp8=40$ に対応する．すなわち $7$ は原始根である．
上記を要約して次の定理を得る．
〔定理 $\boldsymbol{1.\ 27}$〕 素数 $\boldsymbol{p}$ を法として原始根が存在する．$\boldsymbol{r}$ をその一つとすれば\[\boldsymbol{1,\ r,\ r,\ \cdots\cdots r^{p-2}}\]は既約代表の一組である．
〔証〕 原始根の存在することはすでに証明された．$r$ を一つの原始根とすれば，上記 $p-1$ 個の数は $\text{mod}.\ p$ に関して互いに不合同であることも既知である（$62$ 頁）．故にそれらが既約代表の一組である．すなわち $a\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ ならば $r^k\equiv a\hphantom{m}\left(\text{mod}.\ p\right)$，$0\leqq k\lt p-1$ なる指数 $k$ がただ一つある．
〔注意〕 $\left(k,\ p-1\right)=1$ ならば $r^k$ は原始根である．故に原始根は $\varphi\left(p-1\right)$ だけある（$\text{mod}.\ p$に関していう）．一般に $\left(k,\ p-1\right)=d$ ならば，$p-1=ed$ とするとき，$r^k$ は指数 $e$ に対応する（$\S\ 10$，問題 $1$）．
$\boldsymbol{2.}$ 定理 $1.\ 27$ に述べたように，$r$ を $p$ の原始根とすれば，$a\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ なる任意の整数に対して\[r^\alpha\equiv a\hphantom{m}\left(\text{mod}.\ p\right)\]なる指数 $\alpha$ が $0\leqq\alpha\lt p-1$ の範囲に必ず，しかもただ一つ存在する．この $\alpha$ を $r$ を底としての $a$ の指数（index）といい，それを次のように記す：\[\operatorname{Ind}_r\ \!\left(a\right)=\alpha.\]しかし指数を $0$ ないし $p-1$ の範囲に限る必要はない．一般に\[r^s\equiv a\hphantom{m}\left(\text{mod}.\ p\right)\tag{$\ 3\ $}\]とすれば\[s\equiv\alpha\hphantom{m}\left(\text{mod}.\ p-1\right).\]よって $\left(\ 3\ \right)$ を満足させる $s$ をも $a$ の指数という．しからば $a$ の指数は $p-1$ を法として一定である．すなわち\[\operatorname{Ind}_r\ \!\left(a\right)\equiv s\hphantom{m}\left(\text{mod}.\ p-1\right).\tag{$\ 4\ $}\] $\S\ 10$ の注意（$54$ 頁）に述べたように，$s$ は負数でもよい．
$\left(\ 3\ \right)$ において $a$ は $p$ を法として，また $s$ は $p-1$ を法として考えるべきである．すなわち
$a\equiv b\hphantom{m}\left(\text{mod}.\ p\right)$ ならば，$\operatorname{Ind}.\ \!a\equiv\operatorname{Ind}.\ \!b\hphantom{m}\left(\text{mod}.\ p-1\right).$
$\operatorname{Ind}.\ \!a\equiv\operatorname{Ind}.\ \!b\hphantom{m}\left(\text{mod}.\ p-1\right)$ ならば，$a\equiv b\hphantom{m}\left(\text{mod}.\ p\right).$
もちろん底 $r$ は不動としていう．
〔例〕 $p=13$．
$2$ は原始根である．\[\begin{alignat*}{1}&2^0=1,\ 2^1=2,\ 2^2=4,\ 2^3=8,\ 2^4\equiv3,\ 2^5\equiv6,\\[2mm]&2^6\equiv12,\ 2^7\equiv11,\ 2^8\equiv9,\ 2^9\equiv5,\ 2^{10}\equiv10,\ 2^{11}\equiv7.\end{alignat*}\hphantom{m}\left(\text{mod}.\ 13\right)\]よって各既約類の指数表は次の通り．$N\equiv2^I\hphantom{m}\left(\text{mod}.\ 13\right)$
| $N$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $\hphantom{1}7$ | $8$ | $9$ | $10$ | $11$ | $12$ |
| $\hspace{0.5mm}I$ | $0$ | $1$ | $4$ | $2$ | $9$ | $5$ | $11$ | $3$ | $8$ | $10$ | $\hphantom{1}7$ | $\hphantom{1}6$ |
用法． $1$ $)$ $\operatorname{Ind}.\ \!100$ を求めること．
$100\equiv9\hphantom{m}\left(\text{mod}.\ 13\right).$ $\therefore\hphantom{\therefore}\operatorname{Ind}.\ \!100=\operatorname{Ind}.\ \!9=8.$
$2$ $)$ $\operatorname{Ind}.\ \!\left(-1\right)$ を求めること．
$-1\equiv12\hphantom{m}\left(\text{mod}.\ 13\right).$ $\therefore\hphantom{\therefore}\operatorname{Ind}.\ \!\left(-1\right)=\operatorname{Ind}.\ \!12=6.$
$3$ $)$ $\operatorname{Ind}.\ \!x=9$ から $x$ を求めること．
$I$ の欄で $9$ を求め，それに対する $N$ の欄の数 $5$ をとる．
$x\equiv5\hphantom{m}\left(\text{mod}.\ 13\right).$
$4$ $)$ $\operatorname{Ind}.\ \!x=-1$ から $x$ を求めること．
$-1\equiv11\hphantom{m}\left(\text{mod}.\ 12\right)$，$I=11$ に対する $N=7$．
$\therefore$ $x\equiv7\hphantom{m}\left(\text{mod}.\ 13\right).$
〔定理 $\boldsymbol{1.\ 28}$〕 素数 $p$ を法として，原始根 $r$ を底とするとき，\[\begin{alignat*}{2}&\operatorname{Ind}.\ \!ab&&\equiv\operatorname{Ind}.\ \!a+\operatorname{Ind}.\ \!b,\\[2mm]&\operatorname{Ind}.\ \!a^n&&\equiv n\operatorname{Ind}.\ \!a.\end{alignat*}\hspace{2cm}\left(\text{mod}.\ p-1\right)\] 〔証〕 $\operatorname{Ind}.\ \!a=\alpha$，$\operatorname{Ind}.\ \!b=\beta$ とすれば，\[a\equiv r^\alpha,\ \ b\equiv r^\beta\hphantom{m}\left(\text{mod}.\ p\right).\]故に\[ab\equiv r^{\alpha+\beta}\hphantom{m}\left(\text{mod}.\ p\right).\]故に\[\operatorname{Ind}.\ \!ab\equiv\alpha+\beta\equiv\operatorname{Ind}.\ \!a+\operatorname{Ind}.\ \!b\hphantom{m}\left(\text{mod}.\ p-1\right).\]因数が二つより多くても同様である．特に同一の因数 $n$ 個のとき\[\operatorname{Ind}.\ \!a^n\equiv n\hspace{0.7mm}\cdotp\operatorname{Ind}.\ \!a\hphantom{m}\left(\text{mod}.\ p-1\right).\]
このように $\operatorname{Ind}$ は $\log$ に類似する性質を有するから，$\operatorname{Ind}$ の表を $\text{mod}.\ p$ に関する計算に使用することができる．
Jacobi の Canon arithmeticus（$1839$）に $1000$ 以下の素数を法とする指数の表が計算されてある．
（Cunningham の調査した正誤表が Messenger of mathematics $46$ 巻（$1916$）に載っている．）
本書の終りに $100$ 以下の素数を法とする指数表を掲げる．
次に上掲 $13$ を法とする指数表によって二，三計算の例を示そう．
〔例 $1$〕 $11x\equiv5\hphantom{m}\left(\text{mod}.\ 13\right)$ を解くこと．
| 〔解〕 | $\operatorname{Ind}.\ \!11+\operatorname{Ind}.\ \!x\equiv5\hphantom{m}\left(\text{mod}.\ 12\right).$ |
| 〔解〕 | $3\hspace{0.7mm}\cdotp\operatorname{Ind}.\ \!x\equiv\operatorname{Ind}.\ \!5\hphantom{m}\left(\text{mod}.\ 12\right).$ |
| $x\equiv8,\ 11,\ 7\hphantom{m}\left(\text{mod}.\ 13\right).$ | ||
| 〔検算〕 | $7^3-5\equiv338=13\times26.$ | |
| $8^3-5\equiv507=13\times39.$ | ||
| $11^3-5\equiv1326=13\times102.$ |
〔解〕 表から $5\hspace{0.7mm}\cdotp8\equiv1\hphantom{m}\left(\text{mod}.\ 13\right)$ を得る．よって $8$ を掛けて\[40x^2+24x-80\equiv0\hphantom{m}\left(\text{mod}.\ 13\right).\] あるいは\[x^2-2x-2\equiv3\hphantom{m}\left(\text{mod}.\ 13\right),\] すなわち\begin{alignat*}{1}&\hphantom{\therefore\therefore\therefore\therefore}\left(x-1\right)^2\equiv3\hphantom{m}\left(\text{mod}.\ 13\right).\\&\therefore\hphantom{\therefore}2\hspace{0.7mm}\cdotp\operatorname{Ind}.\ \!\left(x-1\right)\equiv4\hphantom{m}\left(\text{mod}.\ 12\right),\\&\therefore\hphantom{\therefore}\operatorname{Ind}.\ \!\left(x-1\right)\equiv2\ または\ 8\hphantom{m}\left(\text{mod}.\ 12\right).\end{alignat*} 表から
| $x-1\equiv4$ または $9\hphantom{m}\left(\text{mod}.\ 13\right).$ |
| $x\equiv5$ または $10\hphantom{m}\left(\text{mod}.\ 13\right).$ |
〔解〕 $r^{p-1}-1=\left(\lower{0.1em}{r^{\displaystyle\small\raise{0.5em}\frac{p-1}{2}}-1}\right)\left(\lower{0.1em}{r^{\displaystyle\small\raise{0.5em}\frac{p-1}{2}}+1}\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$．
$r$ は原始根だから $r^{\displaystyle\small\raise{0.5em}\frac{p-1}{2}}\not\equiv1$，故に $r^{\displaystyle\small\raise{0.5em}\frac{p-1}{2}}\equiv-1\hphantom{m}\left(\text{mod}.\ p\right)$．
〔問題 $\boldsymbol{2}$〕 $a+b=p$ ならば $\operatorname{Ind}.\ \!a\ –\!\!\ \operatorname{Ind}.\ \!b\equiv\dfrac{p-1}{2}\hphantom{m}\left(\text{mod}.\ p\right)$．ただし $p\neq2$．
〔解〕 $a\equiv-b\hphantom{m}\left(\text{mod}.\ p\right)$．故に $\operatorname{Ind}.\ \!a\equiv\operatorname{Ind}.\ \!\left(-1\right)+\operatorname{Ind}.\ \!b\equiv\dfrac{p-1}{2}+\operatorname{Ind}.\ \!b\hphantom{m}\left(\text{mod}.\ p-1\right)$．
〔問題 $\boldsymbol{3}$〕 底の変換も $\log$ と同様である
| $\operatorname{Ind}_{r^{\ \!\prime}}\ \!a\equiv\rho\operatorname{Ind}_r\ \!a,\hphantom{m}\left(\text{mod}.\ p-1\right)$．ただし $\rho=\operatorname{Ind}_{r^{\ \!\prime}}\ \!r$． |
〔問題 $\boldsymbol{4}$〕 $k$ が $p-1$ で割り切れないときは（$p$ 素数）\[1^k+2^k+3^k+\cdots\cdots+\left(p-1\right)^k\equiv0\hphantom{m}\left(\text{mod}.\ p\right).\] 〔解〕 $r$ を法 $p$ の原始根とすれば，この和は\begin{alignat*}{1}&\equiv1+r^k+r^{2k}+\cdots\cdots+r^{\left(p-2\right)k}\\&=\frac{\left(r^{p-1}\right)^{}k-1}{r^k-1}\equiv0\hphantom{m}\left(\text{mod}.\ p\right).\end{alignat*}（分子は $\left(r^{p-1}\right){}^k-1\equiv1^k-1\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$，分母は $r^k-1\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ であるから．）
〔注意〕 $k$ が $p-1$ で割り切れるならば，和の各項が $\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ ，故に和は $\equiv p-1\equiv-1\hphantom{m}\left(\text{mod}.\ p\right)$．
〔問題 $\boldsymbol{5}$〕 $p$ が素数ならば，$\left(p-1\right)^{\ }\!!\equiv-1\hphantom{m}\left(\text{mod}.\ p\right)$（Wilson の定理）．
〔解〕 $\left(p-1\right)^{\ }\!!\equiv r^{1+2+\cdots\cdots+\left(p-2\right)}=\left(\lower{0.1em}{r^{\displaystyle\small\raise{0.5em}\frac{p-1}{2}}}\right){}^{p-2}\equiv\left(-1\right){}^{p-2}\equiv-1\hphantom{m}\left(\text{mod}.\ p\right)$．
$\boldsymbol{3.}$ 指数の理論によって容易に次の著しい定理を得る．
〔定理 $\boldsymbol{1.\ 29}$〕 法 $p$ は素数，$a$ は $p$ で割り切れないとき，二項合同式\[x^n\equiv a\hphantom{m}\left(\text{mod}.\ p\right)\]が解を有するために必要かつ十分な条件は\[a^f\equiv1\hphantom{m}\left(\text{mod}.\ p\right)\]である．ただし $f=\dfrac{p-1}{\left(n,\ p-1\right)}$．
〔証〕 $x^n\equiv a\hphantom{m}\left(\text{mod}.\ p\right)$ を解くには\[n\hspace{0.7mm}\cdotp\operatorname{Ind}.\ \!x\equiv\operatorname{Ind}.\ \!a\hphantom{m}\left(\text{mod}.\ p-1\right)\]を解けばよい．
いま $\left(n,\ p-1\right)=e$ とすれば，この合同式が解を有するために必要かつ十分な条件は $\operatorname{Ind}.\ \!a$ が $e$ で割り切れることである（定理 $1.\ 13$）．
さて底を $r$，$\operatorname{Ind}.\ \!a=\alpha$ とすれば，$\alpha$ が $e$ で割り切れるとき，$\alpha=eq$ と置けば\[a\equiv r^{eq}\hphantom{m}\left(\text{mod}.\ p\right).\]故に\[a^f\equiv r^{efq}=r^{\left(p-1\right)q}\equiv1\hphantom{m}\left(\text{mod}.\ p\right).\] また逆に $a^f\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ ならば $r^{f\alpha}\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$．故に $f\alpha$ は $p-1=ef$ で割り切れる，したがって $\alpha$ は $e$ で割り切れる．故に $\operatorname{Ind}.\ \!a$ が $e$ で割り切れるというのは $a^f\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ と同一に帰する．すなわち定理は証明されたのである．
〔注意〕 解があるとき，解の数は $e=\left(n,\ p-1\right)$．
合同式 $x^n\equiv a\hphantom{m}\left(\text{mod}.\ p\right)$ が解を有するか，または有しないかにしたがって $a$ を $p$ の $\boldsymbol{n}$ 巾剰余または非剰余という．
$a$ が $n$ 巾剰余ならば，$a^\prime\equiv a\hphantom{m}\left(\text{mod}.\ p\right)$ なる $a^\prime$ はもちろん $n$ 巾剰余である．$n$ 巾剰余であるとか，非剰余であるとかいうことは，$p$ を法として数の類に関する性質である．故に巾剰余，非剰余の問題に関しては，数を $p$ を法としての類を代表するものと見てよい．
$0$ はもちろん $n$ 巾剰余である．
$a\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ なる $a$ のみについていえば，定理 $1.\ 29$ によって，
$\left(n,\ p-1\right)=1$ であるときは，任意の $a$ が $n$ 巾剰余である．これらは興味の少ない場合である．
$\left(n,\ p-1\right)=e\gt1$ であるときは，$\operatorname{Ind}.\ \!a$ が $e$ の倍数なる $a$ だけが $n$ 巾剰余である．
すなわち $p-1=ef$ と置けば，$\operatorname{Ind}.\ \!a=0$，$e$，$2e$，$\cdots\cdots$，$\left(f-1\right)e$．
故に $n$ 巾剰余は $p$ を法としての $p-1$ 個の既約類の中の $e$ 分の一（$f$ 個）だけである．