第 $1$ 章 附 記
$\S\ 15.$ 多 項 式 の 合 同
$\boldsymbol{1.}$ 整係数の多項式を或る整数を法として考察する必要がしばしば生じる．変数の巾に従って整理された多項式\begin{alignat*}{3}f\left(x\right)&=a_0x^n&&+a_1x^{n-1}&&+\cdots\cdots+a_n,\\[2mm]g\left(x\right)&=b_0x^n&&+b_1x^{n-1}&&+\cdots\cdots+b_n\end{alignat*}において\[a_0\equiv b_0,\ \ a_1\equiv b_1,\ \cdots\cdots,\ a_n\equiv b_n\hphantom{m}\left(\text{mod}.\ m\right)\]なるとき，これらの多項式を互いに合同（恒等的に合同）といい，それを\[f\left(x\right)\equiv g\left(x\right)\hphantom{m}\left(\text{mod}.\ m\right)\]と記るす．特に\[f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ m\right)\]は $f\left(x\right)$ の各係数が $m$ で割り切れることを意味する．二つ以上の変数の多項式に関しても同様である．
この定義に従えば\[\begin{alignat*}{1}f_1\left(x\right)&\equiv g_1\left(x\right),\\[2mm]f_2\left(x\right)&\equiv g_2\left(x\right)\end{alignat*}\hphantom{m}\left(\text{mod}.\ m\right)\]であるときは\begin{alignat*}{3}&f_1\left(x\right)\pm f_2\left(x\right)&&\equiv g_1\left(x\right)\pm g_2\left(x\right)&\hphantom{m}&\left(\text{mod}.\ m\right),\\[2mm]&f_1\left(x\right)\cdotp f_2\left(x\right)&&\equiv g_1\left(x\right)\cdotp g_2\left(x\right)&\hphantom{m}&\left(\text{mod}.\ m\right)\end{alignat*}であること明らかである．
念のために第二の関係式についていえば，仮定によって\begin{alignat*}{2}g_1\left(x\right)&=f_1\left(x\right)&&+mh_1\left(x\right),\\[2mm]g_2\left(x\right)&=f_2\left(x\right)&&+mh_2\left(x\right).\end{alignat*}もちろん $h_1\left(x\right)$，$h_2\left(x\right)$ は整係数の多項式である．したがって\[g_1\left(x\right)g_2\left(x\right)=f_1\left(x\right)f_2\left(x\right)+m\left\{f_1\left(x\right)h_2\left(x\right)+f_2\left(x\right)h_1\left(x\right)+mh_1\left(x\right)h_2\left(x\right)\right\}\]から\[f_1\left(x\right)f_2\left(x\right)\equiv g_1\left(x\right)g_2\left(x\right)\hphantom{m}\left(\text{mod}.\ m\right).\]
$\boldsymbol{2.}$ 多項式の合同は法が素数であるときだけが簡単で，多くの点において代数的の恒等に類似する．以下一定の素数 $p$ を法とする場合のみを論ずるから，時には $\text{mod}.\ p$ を略すこともある．
多項式\[f\left(x\right)=a_0x^n+a_1x^{n-1}+\cdots\cdots+a_n\]において $a_0\not\equiv0$ であるとき，$f\left(x\right)$ を $\text{mod}.\ p$ に関して $n$ 次という．しからば\[f\left(x\right)=a_0x^n+\cdots\cdots,\ \ g\left(x\right)=b_0x^m+\cdots\cdots\]が，$\text{mod}.\ p$ に関してそれぞれ $n$ 次，$m$ 次ならば，積\[f\left(x\right)g\left(x\right)=a_0b_0x^{n+m}+\cdots\cdots\]は $m+n$ 次である．
仮定によって $a_0\not\equiv0$，$b_0\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ したがって $a_0b_0\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ だからである（法が素数でないときには，すでにこの定理が成り立たない）．
よって
〔定理 $\boldsymbol{1.\ 39}$〕 $f\left(x\right)\cdotp g\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ ならば，$f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$．または $g\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$．因数が二つより多くても同様である．
多項式の除法に対応して次の基本定理が $\text{mod}.\ p$ に関しても成り立つ．
〔定理 $\boldsymbol{1.\ 40}$〕 $f\left(x\right)$，$g\left(x\right)$ が与えられた多項式で，$g\left(x\right)$ は $n$ 次ならば\[f\left(x\right)\equiv g\left(x\right)\cdotp q\left(x\right)+h\left(x\right)\hphantom{m}\left(\text{mod}.\ p\right)\]で，$h\left(x\right)$ は $n-1$ 次以下であるような多項式 $q\left(x\right)$，$h\left(x\right)$ がただ一組に限って必ずある．一組というのは $\text{mod}.\ p$ に関していう．次数も同様である．
〔証〕 $g\left(x\right)=ax^n+bx^{n-1}+\cdots\cdots$，$a\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ とする．\[aa^\prime\equiv1\hphantom{m}\left(\text{mod}.\ p\right)\]なる $a^\prime$ を $g\left(x\right)$ に掛けて，$x^n$ の係数 $aa^\prime$ を $1$ で置き換えて，\[g_0\left(x\right)=x^n+a^\prime bx^{n-1}+\cdots\cdots\equiv a^\prime g\left(x\right)\]とおく．$f\left(x\right)$ を $g_0\left(x\right)$ で代数的に割れば，$g_0\left(x\right)$ の最高次の項の係数が，$1$ であるから商 $q_0\left(x\right)$ も剰余 $h\left(x\right)$ も整係数を有する．すなわち\[f\left(x\right)=g_0\left(x\right)q_0\left(x\right)+h\left(x\right)\]これは代数的恒等式である．さて $aa^\prime\equiv1\hphantom{m}\left(\text{mod}.\ p\right)$ であるから，\[f\left(x\right)\equiv ag_0\left(x\right)\cdotp a^\prime q_0\left(x\right)+h\left(x\right)\hphantom{m}\left(\text{mod}.\ p\right).\]$ag_0\left(x\right)\equiv aa^\prime g\left(x\right)\equiv g\left(x\right)$ であるから，$a^\prime q_0\left(x\right)=q\left(x\right)$ とすれば\[f\left(x\right)\equiv g\left(x\right)\cdotp q\left(x\right)+h\left(x\right)\hphantom{m}\left(\text{mod}.\ p\right).\] また，もしも同時に\[f\left(x\right)\equiv g\left(x\right)\cdotp q_1\left(x\right)+h_1\left(x\right)\hphantom{m}\left(\text{mod}.\ p\right).\]で，$h_1\left(x\right)$ も $n-1$ 次以下とすれば\[g\left(x\right)\left\{q\left(x\right)-q_1\left(x\right)\right\}\equiv h_1\left(x\right)-h\left(x\right)\hphantom{m}\left(\text{mod}.\ p\right).\]$h_1\left(x\right)-h\left(x\right)$ は $n-1$ 次以下であるから，\[q\left(x\right)-q_1\left(x\right)\equiv0,\]したがって\[h_1\left(x\right)-h\left(x\right)\equiv0.\]すなわち\[q\left(x\right)\equiv q_1\left(x\right),\hphantom{m}h\left(x\right)\equiv h_1\left(x\right).\]よって $\text{mod}.\ p$ に関して商も剰余も一定である．
特に剰余 $h\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$，すなわち\[f\left(x\right)\equiv g\left(x\right)q\left(x\right)\hphantom{m}\left(\text{mod}.\ p\right)\]である場合には，$f\left(x\right)$ は $\text{mod}.\ p$ に関して因数 $g\left(x\right)$，$q\left(x\right)$ に分解されるともいい，また $f\left(x\right)$ は $g\left(x\right)$ で割り切れるともいう．
このような用語は，代数的の整除との形式的の類似を暗示するために過ぎない．実質的には代数的の整除とは全く別の物である．例えば\[x^2+1\equiv\left(x-2\right)\left(x+2\right)\hphantom{m}\left(\text{mod}.\ 5\right)\]であるが，$\text{mod}.\ 7$ に関しては $x^2+1$ は分解不可能である．
$\text{mod}.\ 13$ に関しては\[x^2+1\equiv\left(x-5\right)\left(x+5\right)\hphantom{m}\left(\text{mod}.\ 13\right).\] 定理 $1.\ 40$ に基づいて，$\text{mod}.\ p$に関して $f\left(x\right)$，$g\left(x\right)$ に Euclid の互除法を行なうことができる．その最後の剰余を $l\left(x\right)$ とすれば，$l\left(x\right)$ は $\text{mod}.\ p$ に関する $f\left(x\right)$，$g\left(x\right)$ の最大公約数である．というのは，\[f\left(x\right)\equiv l\left(x\right)\cdotp u\left(x\right),\ \ \ g\left(x\right)\equiv l\left(x\right)\cdotp v\left(x\right)\hphantom{m}\left(\text{mod}.\ p\right)\]で，しかも $l\left(x\right)$ はこのような $f\left(x\right)$，$g\left(x\right)$ の公因子 $\left(\text{mod}.\ p\right)$ の中で最高次 $\left(\text{mod}.\ p\right)$ のもので，それはすべての公因子 $\left(\text{mod}.\ p\right)$ で割り切れる $\left(\text{mod}.\ p\right)$ のである．特に $l\left(x\right)\equiv c\not\equiv0$ が常数であるときに $f\left(x\right)$，$g\left(x\right)$ は $\text{mod}.\ p$ に関して互いに素であるという．その場合には\[f\left(x\right)\cdotp P\left(x\right)+g\left(x\right)\cdotp Q\left(x\right)\equiv1\hphantom{m}\left(\text{mod}.\ p\right)\]になるような多項式 $P\left(x\right)$，$Q\left(x\right)$ が求められる．
〔定理 $\boldsymbol{1.\ 41}$〕 多項式を $\text{mod}.\ p$ に関して既約因子の積に分解することができる．分解の結果は常数因子だけの違いを考えないならば，ただ一つである．
既約もただ一つも $\text{mod}.\ p$ に関していう．すなわち既約なる多項式とは，$\text{mod}.\ p$ に関して低次なる因数に分解されないものをいうのである．例えば $\text{mod}.\ 7$ に関して $x^2+1$ は既約であるが，$\text{mod}.\ 5$ に関しては既約でない．$x^2+1\equiv\left(x-2\right)\left(x+2\right)\hphantom{m}\left(\text{mod}.\ 5\right)$．
これから Eisenstein の定理を導くことができる．\begin{alignat*}{1}f\left(x\right)&=a_0x^n+a_1x^{n-1}+\cdots\cdots+a_n\ において\\[2mm]&\hphantom{-}a_0\not\equiv0,\ \ a_1\equiv a_2\equiv\cdots\cdots\equiv a_n\equiv0\hphantom{m}\left(\text{mod}.\ p\right)\end{alignat*}ならば $f\left(x\right)\equiv a_0x^n\hphantom{m}\left(\text{mod}.\ p\right)$．故にもしも\[f\left(x\right)=\varphi\left(x\right)\psi\left(x\right),\ \varphi\left(x\right)=b_0x^\mu+\cdots\cdots,\ \psi\left(x\right)=c_0x^\nu+\cdots\cdots,\ a_0=b_0c_0\]ならば\[a_0x^n\equiv\varphi\left(x\right)\cdotp\psi\left(x\right)\hphantom{m}\left(\text{mod}.\ p\right)\]から，定理 $1.\ 41$ によって\[\varphi\left(x\right)\equiv b_0x^\mu.\ \psi\left(x\right)\equiv c_0x^\nu\hphantom{m}\left(\text{mod}.\ p\right).\]これから Eisenstein の定理を得る（代．$130$ 頁）．
〔注意〕 $f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ が $x$ のすべての整数値に対して成り立つとき，恒等合同の意味で $f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ ということはできない．多項式 $x^p-x$ がその例である．
この点は代数的の恒等とは趣が違う．
上記の場合に $f\left(x\right)$ は $x^p-x$ で割り切れる，すなわち $f\left(x\right)\equiv\left(x^p-x\right)g\left(x\right)\hphantom{m}\left(\text{mod}.\ p\right)$．もしも $f\left(x\right)$ が $p-1$ 次以下ならば恒等的に $f\left(x\right)\equiv0$．
上記の説明ははなはだ概括的であるけれども，その趣意が了解されたならば，代．第 $4$ 章を参照して等号 $=$ を合同記号 $\equiv\ \left(\text{mod}.\ p\right)$ で置き換えて，いちいち当たって見れば，なんらの困難なく，すべてが了解されるであろう．
要点は四則の基本的法則が，恒等においても合同 $\left(\text{mod}.\ p\right)$ においても同様であることに着眼して，基本的法則から生じる結論をできうる限り追跡するところにある．法が素数でないときには，$a\not\equiv0$，$b\not\equiv0$ でも $ab\equiv0$ になり得るから（「零因数」があるから）このような類似は直ぐに壊れてしまう．故に法を素数に限ったのである．
$\boldsymbol{3.}$ 上記の理論を合同式の解法に応用することができる．合同式 $f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ が解 $x\equiv x_1$ を有するならば，$f\left(x\right)$ は $x-x_1$ なる因数 $\left(\text{mod}.\ p\right)$ を有する．故に $x_1$，$x_2$，$\cdots\cdots$，$x_m$ を相異なる解とすれば\[f\left(x\right)\equiv\left(x-x_1\right)^{e_1}\left(x-x_2\right)^{e_2}\cdots\cdots\left(x-x_m\right)^{e_m}g\left(x\right).\] しかるに Fermat の定理によって\[x^p-x\equiv x\left(x-1\right)\left(x-2\right)\cdots\cdots\left(x-\left(p-1\right)\ \!\right).\] 故に $f\left(x\right)$ と $x^p-x$ との最大公約数を $h\left(x\right)$ とすれば，定理 $1.\ 41$ によって\[h\left(x\right)\equiv\left(x-x_1\right)\left(x-x_2\right)\cdots\cdots\left(x-x_m\right)\]である．$f\left(x\right)\equiv0$ の解はすべて $h\left(x\right)\equiv0$ から得られる．
$h\left(x\right)$ は互除法によって求められる．$h\left(x\right)$ は次数だけの解を有し，一般的には $f\left(x\right)$ よりも低次であるから，試行によって解を求めるにしても，$f\left(x\right)$ に $h\left(x\right)$ を代用するのがよい．もしも $h\left(x\right)$ が常数ならば $f\left(x\right)\equiv0$ は解を有しない．
$f\left(x\right)$ が $x\equiv0$ なる解を有するときには，$f\left(x\right)$ の常数項は $\equiv0$ である．そのときには $f\left(x\right)$ から因数 $x$ を除いて，$x^{p-1}-1$ との最大公約数を求めるならば，それから $x\equiv0$ 以外の解が得られる．
もしも $f\left(x\right)$ が $p$ 次以上ならば，それを $x^{p-1}-1$ で割った剰余を $f\left(x\right)$ に代用してよい．剰余は $f\left(x\right)$ において $x^{p-1}$，$x^p$，$x^{p+1}$，$\cdots\cdots$ にそれぞれ $1$，$x$，$x^2$，$\cdots\cdots$ を代入して求めることができる．
〔例〕 $f\left(x\right)=x^5+x^4-x^3+3x^2-6x-5\equiv0\hphantom{m}\left(\text{mod}.\ 7\right)$．
$f\left(x\right)$ と $x^6-1$ との最大公約数 $\left(\text{mod}.\ 7\right)$ を計算すれば $h\left(x\right)\equiv x^3+x^2+4x+1$ を得る．故に解は三つある．
この場合には $h\left(1\right)=7\equiv0$ が一見して明らかであるから，$x-1$ で割って\[x^3+x^2+4x+1\equiv\left(x-1\right)\left(x^2+2x-1\right)\hphantom{m}\left(\text{mod}.\ 7\right).\] さて\begin{alignat*}{1}x^2+2x-1&=\left(x+1\right)^2-2\\&\equiv\left(x+1\right)^2-9\hphantom{m}\left(\text{mod}.\ 7\right).\end{alignat*}よって他の二つの解は $-1\pm3$，すなわち $2$．または $-4$．故に解は\[1,\ \ 2,\ \ 3\hphantom{m}\left(\text{mod}.\ 7\right).\] $f\left(x\right)$ と $x^{p-1}-1$ との最大公約数を求める代わりに $f\left(x\right)$ と $x^{\displaystyle\small\raise{0.5em}\frac{p-1}{2}}-1$ と，および $x^{\displaystyle\small\raise{0.5em}\frac{p-1}{2}}+1$ との最大公約数を求めるならば，計算が簡単になる．
上記の例では計算は次の通り．
まず $f\left(x\right)$ を $x^3-1$ で割った剰余を求めるには，$x^3$，$x^4$，$x^5$ に $1$，$x$，$x^2$ を代入すればよい
| $\begin{alignat*}{1}&x^5+x^4-x^3\!\!\\&\ \vphantom{x^2}\end{alignat*}$ | $\begin{alignat*}{1}\!&+\ \!3x^2-6x-5\\\!&+\ \!\hphantom{3}x^2+\hphantom{6}x-1\end{alignat*}$ |
| $\begin{alignat*}{1}\!&+\ \!4x^2-5x-6\end{alignat*}$ |
| $\dfrac{1}{4}\equiv2$ を掛けて： |
| |||||||||||||||||||||||||
| これで $x^3-1$ を割れば， | ||||||||||||||||||||||||||
| 割り切れる． | ||||||||||||||||||||||||||
次に $f\left(x\right)$ と $x^3+1$ との最大公約数は $x-3$．それから解 $x\equiv3$ を得る．
| $\begin{alignat*}{1}&1+1-\!\\&\ \end{alignat*}$ | $\begin{alignat*}{1}1&+3-6-5\\&-1-1+1\end{alignat*}$ | ||||||
| $\cssId{eq4}{\biggl(}\dfrac{1}{2}\equiv4$ をかける$\cssId{eq5}{\biggr)}$ | $\begin{alignat*}{1}&2+0-4\\&1+0-2\\&\ \end{alignat*}$ | $\begin{alignat*}{1}&\ \\&\hspace{-1mm}\!\cssId{eq2}{\Huge)}\!\!\!\end{alignat*}$ | $\begin{alignat*}{1}&\ \\&1+0+0+1\\&1+0-2\end{alignat*}$ | ||||
| $\begin{alignat*}{1}&2+1\\&1-3\\&\ \end{alignat*}$ | $\begin{alignat*}{1}&\ \\&\hspace{-1mm}\!\cssId{eq3}{\Huge)}\!\!\!\end{alignat*}$ | $\begin{alignat*}{1}&\ \\&1+\!\\&1-\!\end{alignat*}$ | $\begin{alignat*}{1}&\ \\&0-2\hphantom{1}\\&3\end{alignat*}$ | ||||
| $\begin{alignat*}{1}&3-2\hphantom{1}\\&3-9\hphantom{1}\end{alignat*}$ | |||||||
| $\begin{alignat*}{1}&0\hphantom{1}\end{alignat*}$ | |||||||
〔問題 $\boldsymbol{1}$〕 $g\left(x\right)=c_1x^{p-2}+c_2x^{p-3}+\cdots\cdots+c_{p-1}$ なるとき，
| $\hphantom{m}c_1\hphantom{m}$ | $\hphantom{m}c_2\hphantom{m}$ | $\hphantom{m}c_3\hphantom{m}$ | $\hphantom{1}\cdots\cdots c_{p-1}$ | |
| $c_2$ | $c_3$ | $c_4$ | $\hphantom{1}\cdots\cdots c_1$ | |
| $C_{p-1}=$ | $c_3$ | $c_4$ | $c_5$ | $\hphantom{1}\cdots\cdots c_2$ |
| $\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp$ | $\ \!\lower{0.05em}{\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp\cdotp}$ | |||
| $\hphantom{m}c_{p-1}\hphantom{m}$ | $c_1$ | $c_2$ | $\cdots\cdots\ c_{p-2}\hphantom{_1}$ | |
それらは
| $\varphi\left(x\right)=\ \!\!$ | $\hphantom{c}c_1\hphantom{c}$ | $\hphantom{c}c_2\cdots c_{k-1}\hphantom{c}$ | $c_kx^{p-k-1}\hphantom{m}+\hphantom{m}c_{k+1}x^{p-k-2}+\cdots\ $ | $\ \!\!\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ |
| $\hphantom{c}c_2\hphantom{c}$ | $\hphantom{c}c_3\cdots c_k\hphantom{c}$ | $c_{k+1}x^{p-k-1}\hphantom{m}+\hphantom{m}c_{k+2}x^{p-k-2}+\cdots\ $ | ||
| $\hphantom{c}{\small\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots}\ $ | ||||
| $\hphantom{c}c_k\hphantom{c}$ | $\hphantom{c}c_{k+1}\cdots c_{2k-2}\hphantom{c}$ | $\hphantom{c}c_{2k-1}x^{p-k-1}\hphantom{m}+\hphantom{m_+}c_{2k}x^{p-k-2}+\cdots\ $ | ||
〔解〕 詳しくは述べないが，$x^{p-1}-1$ と $g\left(x\right)$ との最大公約数 $\left(\text{mod}.\ p\right)$ を求めるのに代．$\S\S\ 72$，$73$ の方法を応用するのである．この場合\[\frac{g\left(x\right)}{x^{p-1}-1}=\frac{c_1}{x}+\frac{c_2}{x^2}+\cdots\cdots+\frac{c_{p-1}}{x^{p-1}}+\frac{c_1}{x^p}+\frac{c_2}{x^{p+1}}+\cdots\cdots\] 上記の例では $k=3$，$p-1-k=3$\begin{eqnarray*}\begin{vmatrix}\hphantom{-}1&\hphantom{-}1&-x^3+3x^2+\hphantom{1}x+2\\\hphantom{-}1&-1&\ 3x^3+\hphantom{3}x^2+2x+1\\-1&\hphantom{-}3&\hphantom{-}x^3+2x^2+\hphantom{1}x+1\end{vmatrix}&&\equiv5x^3+5x^2+6x+5\\\equiv&&5\left(x^3+x^2+4x+1\right)\hphantom{m}\left(\text{mod}.\ 7\right).\end{eqnarray*}