第 $1$ 章 初 等 整 数 論
$\S\ 7.$ 合同式解法の概論
$\boldsymbol{1.}$ $f\left(x\right)=a_0x^n+a_1x^{n-1}+\cdots\cdots+a_n$ が整係数の多項式であるとき，合同式\[f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ m\right)\]を解くには，各係数 $a_\nu$ をそれと合同な数で置き換えてさしつかえない，特に法 $m$ で割り切れる係数を有する項は消してもよい．このような消去を行なった後に $a_0\not\equiv0\hphantom{m}\left(\text{mod}.\ m\right)$ ならば，上記の合同式を $n$ 次という．法が素数なる合同式に関して次の定理が成り立つ．
〔定理 $\boldsymbol{1.\ 15}$〕 法 $p$ が素数なるとき，$n$ 次の合同式\[\boldsymbol{f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)}\tag{$\ 1\ $}\]は $n$ よりも多くの解を有することを得ない．
解の数はもちろん $p$ を法として，互いに不合同なものを数えていう．
〔証〕 合同式 $\left(\ 1\ \right)$ が解を有するとき，$x\equiv a\hphantom{m}\left(\text{mod}.\ p\right)$ を一つの解とする．すなわち $f\left(a\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$．
さて代数的恒等式\[f\left(x\right)=\left(x-a\right)f_1\left(x\right)+f\left(a\right)\]において $f_1\left(x\right)$ は $a_0x^{n-1}$ を最高次の項とする整係数の多項式である．よって合同式 $\left(\ 1\ \right)$ は\[\left(x-a\right)f_1\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)\]と同一の解を有する．$p$ は素数であるから，この合同式は $x-a$ または，$f_1\left(x\right)$ が $p$ で割り切れるときに限って成り立つ．
故に $x\equiv a\hphantom{m}\left(\text{mod}.\ p\right)$ 以外の $\left(\ 1\ \right)$ の解は $n-1$ 次の合同式\[f_1\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)\]の解でなければならない．故に，定理が $n-1$ 次の多項式に関して正しいならば，$n$ 次の多項式に関しても正しい．
しかるに一次の合同式\[a_0x+a_1\equiv0\hphantom{m}\left(\text{mod}.\ p\right),\hphantom{m}\left(a_0,\ p\right)=1\]は $p$ を法としてただ一つの解を有する（定理 $1.\ 13$）．故に定理は数学的帰納法によって証明されたのである．
〔注意〕 上記の定理において，法 $p$ が素数であることが緊要である．例えば $x^2\equiv1\hphantom{m}\left(\text{mod}.\ 12\right)$ は $x=1$，$5$，$7$，$11\hphantom{m}\left(\text{mod}.\ 12\right)$ なる四つの解を有する．
合同式には解のないことがある．例えば $x^2\equiv2\hphantom{m}\left(\text{mod}.\ 3\right)$．
$\boldsymbol{2.}$ 法 $m$ が合成数なるとき，合同式\[f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ m\right)\tag{$\ 2\ $}\]の解法は法が素数なる場合に帰する．
まず素数 $p$ を法とするとき，\[f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)\tag{$\ 3\ $}\]の解が求められたとして，それから $p$ の任意の巾を法とするときの解を求める方法を述べる．\[f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p^2\right)\tag{$\ 4\ $}\]の解はもちろん $\left(\ 1\ \right)$ を満足させるから，$x_0$を $\left(\ 3\ \right)$ の解とするとき，$\left(\ 4\ \right)$ の解は\[x=x_0+py\tag{$\ 5\ $}\]のような数の中から求められねばならない，これを $\left(\ 4\ \right)$ に代入すれば，\begin{alignat*}{1}f\left(x\right)&=f\left(x_0+py\right)\\&=f\left(x_0\right)+pyf^\prime\left(x_0\right)+p^2y^2\frac{f^{\prime\prime}\left(x_0\right)}{2}+\cdots\cdots\equiv0\hphantom{m}\left(\text{mod}.\ p^2\right).\end{alignat*}さて $f^\prime\left(x\right)$，$\dfrac{f^{\prime\prime}\left(x\right)}{2}$，$\dfrac{f^{\prime\prime\prime}\left(x\right)}{3!}$，$\cdots\cdots$ は整係数の多項式であるから，$f^\prime\left(x_0\right)$，$\dfrac{f^{\prime\prime}\left(x_0\right)}{2}$，$\cdots\cdots$ は整数である．よって上記の展開式の第三項以下は $p^2$ で割り切れるから，$\left(\ 5\ \right)$ の数で $\left(\ 4\ \right)$ を満足させるものを求めることは\[f\left(x_0\right)+pyf^\prime\left(x_0\right)\equiv0\hphantom{m}\left(\text{mod}.\ p^2\right)\]から $y$ を求めることに帰する．
または仮定によって $f\left(x_0\right)$ は $p$ で割り切れるから，\[\frac{f\left(x_0\right)}{p}+yf^\prime\left(x_0\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right).\tag{$\ 6\ $}\] さて，ここで二つの場合を区別する．
$\ \ \!\text{i}\ )$ $f^\prime\left(x_0\right)\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ なるときには，$\left(\ 6\ \right)$ はただ一つの解を有する．それを\[y\equiv y_0\hphantom{m}\left(\text{mod}.\ p\right)\]として $\left(\ 5\ \right)$ に代入すれば，$py\equiv py_0\hphantom{m}\left(\text{mod}.\ p^2\right)$ だから，\[x\equiv x_0+py_0\hphantom{m}\left(\text{mod}.\ p^2\right)\tag{$\ 7\ $}\]を得る．すなわち $\left(\ 3\ \right)$ の一つの解 $x\equiv x_0\hphantom{m}\left(\text{mod}.\ p\right)$ から，$\left(\ 4\ \right)$ の一つの解 $\left(\ 7\ \right)$ を得るのである．
$\text{ii}$ $)$ $f^\prime\left(x_0\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ なるときには，$\left(\ 6\ \right)$ は $f\left(x_0\right)/p$ が $p$ で割り切れないならば，不可能である．もしも $f\left(x_0\right)/p$ が $p$ で割り切れるならば，任意の $y$ によって満足させられる．よって $\left(\ 5\ \right)$ に返って考えるならば，\[x\equiv x_0,\ \ x_0+p,\ \ x_0+2p,\ \cdots\cdots,\ x_0+\left(p-1\right)p\hphantom{m}\left(\text{mod}.\ p^2\right)\]が $\left(\ 4\ \right)$ を満足させる．すなわち $\left(\ 5\ \right)$ の形の数 $x$ は一つも $\left(\ 4\ \right)$ の解を与えないか，あるいはまた $p^2$ を法として，$p$ 個の解を与えるかである．
同様に，$\left(\ 3\ \right)$ のかわりに\[f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p^n\right)\tag{$\ 8\ $}\]を考察すれば，$\left(\ 8\ \right)$ の一つの解を $x_0$ とするとき，\[x=x_0+p^ny\tag{$\ 9\ $}\]の形の数で，\[f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p^{n+1}\right)\tag{$10$}\]を満足させるものは，
$\ \ \!\text{i}\ )$ $f^\prime\left(x_0\right)\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ の場合には，$p^{n+1}$ を法としてただ一つあり，
$\ \text{ii}\ \!)$ $f^\prime\left(x_0\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ の場合には，$p^{n+1}$ を法としては一つもないか，
または $p$ 個ある．$p$ 個の解があるのは $f\left(x_0\right)\equiv0\hphantom{m}\left(\text{mod}.\ p^{n+1}\right)$ で，$\left(\ 9\ \right)$ において $y$ を任意にとっても，それが $\left(10\right)$ を満足させるときである．
以上要約して次の定理を得る．
〔定理 $\boldsymbol{1.\ 16}$〕 合同式 $f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p^n\right)$ の解は $f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ の解から導かれる．
合同式 $f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ の一つの解を $x_0$ とするとき，
$\ \ \!\text{i}\ )$ $f^\prime\left(x_0\right)\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ ならば，$f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p^n\right)$の解の中に，$x\equiv x_0\hphantom{m}\left(\text{mod}.\ p\right)$ なるものが，$\text{mod}.\ p^n$ に関してただ一つある．
$\ \text{ii}\ \!)$ $f^\prime\left(x_0\right)\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$ の場合には，$f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p^n\right)$が $x\equiv x_0\hphantom{m}\left(\text{mod}.\ p^n\right)$ なる解を有するときに，その解から $f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p^{n+1}\right)$ の $p$ 個の解が派生することもあり，あるいは，また $f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p^{n+1}\right)$ は $x\equiv x_0\hphantom{m}\left(\text{mod}.\ p^n\right)$ なる解を有しないこともある．
〔例〕 $p\neq2$ が素数で，$a$ は $p$ で割り切れないとする．そのとき\[x^2\equiv a\hphantom{m}\left(\text{mod}.\ p\right)\]が解を有するならば，解は二つある．それを $\pm x_0$ とする．\[x_0\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right),\ \ x_0\not\equiv-x_0\hphantom{m}\left(\text{mod}.\ p\right).\] この場合には $f\left(x\right)=x^2-a$，$f^\prime\left(x\right)=2x$ ．故に $f^\prime\left(\pm x_0\right)=\pm2x_0\not\equiv0\hphantom{m}\left(\text{mod}.\ p\right)$．これは定理 $1.\ 16$ の$\ \ \!\text{i}\ )$ の場合である．故に\[x^2\equiv a\hphantom{m}\left(\text{mod}.\ p^n\right)\]は二つの解を有する．
例えば $x^2\equiv2\hphantom{m}\left(\text{mod}.\ 7\right)$ の解は $x_0\equiv\pm3\hphantom{m}\left(\text{mod}.\ 7\right)$．いま\[x^2\equiv2\hphantom{m}\left(\text{mod}.\ 49\right)\]の解を求めるために $x=3+7y$ と置けば\[\left(3+7y\right){}^2\equiv2\hphantom{m}\left(\text{mod}.\ 49\right)\]から\[9+42y\equiv2\hphantom{m}\left(\text{mod}.\ 49\right),\]すなわち\[6y\equiv-1\hphantom{m}\left(\text{mod}.\ 7\right).\]故に\[y\equiv1\hphantom{m}\left(\text{mod}.\ 7\right),\]したがって\[x\equiv10\hphantom{m}\left(\text{mod}.\ 49\right)\]いま一つの解は\[x\equiv-10\equiv39\hphantom{m}\left(\text{mod}.\ 49\right).\] 定理 $1.\ 16$ の $\ \text{ii}\ \!)$ の部分はあまりに粗雑であるが，ここでその細論に入るのは時機尚早である．次に最も簡単な一例を問題として掲出する．これは初等整数論においても重要である．$2$ が別格の素数で，有理整数論における特異点（singular point）ともいうべきものであるところに，目を止めねばならない．
| 〔問題 $\boldsymbol{1}$〕 | $a\equiv1\hphantom{m}\left(\text{mod}.\ 8\right)$ |
〔解〕 $x=1+2y$ を奇数とすれば，$x^2=1+4y\left(y+1\right)$ で，$y$ または $y+1$ は偶数であるから $x^2\equiv1\hphantom{m}\left(\text{mod}.\ 8\right)$．
故に $a\equiv1\hphantom{m}\left(\text{mod}.\ 8\right)$ は $a$ が奇数であるときに問題の合同式が解を有するために必要な条件である．
$n=3$ ならば，この条件のもとにおいて，解は $x\equiv1$，$3$，$5$，$7\hphantom{m}\left(\text{mod}.\ 8\right)$ である．あるいは $x\equiv\pm1$，$\pm1+4\hphantom{m}\left(\text{mod}.\ 8\right)$．
よって数学的帰納法を用いて証明をする．
指数 $n$ に関して定理はすでに証明されたとすれば，指数 $n+1$ のとき解は\[\pm x_0+2^ny または \left(\pm x_0+2^{n-1}\right)+2^ny\hphantom{m}\left(\text{mod}.\ 2^{n+1}\right)\]でなければならない．その $y$（$y=0$ または $1$）は\[\left(\pm x_0+2^ny\right){}^2\equiv a\hphantom{m}\left(\text{mod}.\ 2^{n+1}\right),\tag{$11$}\]あるいは\[\left\{\left(\pm x_0+2^{n-1}\right)+2^ny\right\}{}^2\equiv a\hphantom{m}\left(\text{mod}.\ 2^{n+1}\right)\tag{$12$}\]から求められる．
仮定によって ${x_0}^2-a=2^nt$．故に $\left(11\right)$ から\[2^nt\equiv0\hphantom{m}\left(\text{mod}.\ 2^{n+1}\right).\] $t$ が奇数ならば，これは不可能である．また $t$ が偶数ならば，$y$ は任意であるから，$\text{mod}.\ 2^{n+1}$ に関しては，$y=0$，$1$ として $\pm x_0$ および $\pm x_0+2^n$ が解である．すなわち $\text{mod}.\ 2^n$ に関する解 $\pm x_0$ から，$\text{mod}.\ 2^{n+1}$ に関する解が得られないか，あるいは四つの解が得られる．
次に\begin{alignat*}{1}\left(\pm x_0+2^{n-1}\right){}^2&\equiv{x_0}^2\pm2^nx_0+2^{2n-2}\\&\equiv{x_0}^2+2^n\hphantom{m}\left(\text{mod}.\ 2^{n+1}\right)\end{alignat*}（$x_0$ は奇数，また $2n-2\geqq n+1$ だから）．
よって $\left(12\right)$ から\[2^nt+2^n\equiv0\hphantom{m}\left(\text{mod}.\ 2^{n+1}\right).\]今度は $t$ が偶数ならば，これは不可能であるが，$t$ が奇数ならば，$y$ は任意である．故に $\text{mod}.\ 2^{n+1}$ に関して\[\pm\left(x_0+2^{n-1}\right) および \pm\left(x_0+2^{n-1}\right)+2^n\]の四つの解が得られる．
よって定理は証明された．
この問題では $f\left(x\right)=x^2-a$，$f^\prime\left(x\right)=2x$ で，すなわち定理 $1.\ 16$ の $\ \text{ii}\ \!)$ の場合であるが，$\text{mod}.\ 2^n$ に関する解\[\pm x_0 または \pm x_0+2^{n-1}\]の中の一方からは $\text{mod}.\ 2^{n+1}$ に関する解が得られないで，他の一方からは二つずつの解が派生して，解の数がいつも四つになるのである．
$\boldsymbol{3.}$ 一般の法に関する合同式の解は法が素数巾なる場合に帰する．
〔定理 $\boldsymbol{1.\ 17}$〕 法 $m$ を素数巾に分解して\[m=p^a\hspace{0.7mm}\cdotp q^b\cdots\cdots\tag{$13$}\]とするとき，\begin{alignat*}{1}&f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ p^a\right),\tag{$14$}\\&f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ q^b\right),\tag{$15$}\\&{\small\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots}\end{alignat*}がそれぞれ $\nu$，$\nu^\prime$，$\cdots\cdots$ 個の解を有するとすれば，\[f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ m\right)\tag{$16$}\]は $\nu\nu^\prime\cdots\cdots$ 個の解を有する．それらは\[\left.\begin{alignat*}{1}x&\equiv\alpha\hphantom{m}\left(\text{mod}.\ p^a\right),\\x&\equiv\beta\hphantom{m}\left(\text{mod}.\ q^b\right),\\&{\small\cdots\cdots\cdots\cdots\cdots\cdots\cdots}\end{alignat*}\ \ \right\}\tag{$17$}\]から求められる，ここで $\alpha$，$\beta$，$\cdots\cdots$ はそれぞれ $p^a$，$q^b$，$\cdots\cdots$ を法としての $f\left(x\right)\equiv0$ の解の任意の一組である．
〔証〕 $x$ が $\left(16\right)$ の解ならば，もちろん $\left(14\right)$，$\left(15\right)$ ，$\cdots\cdots$ の解であるから，$\left(17\right)$ を満足させる．逆に $\left(17\right)$ を満足させる $x$ は $\left(14\right)$，$\left(15\right)$ ，$\cdots\cdots$ を満足させるから，$\left(16\right)$ を満足させる．
〔例〕 $x^2\equiv1\hphantom{m}\left(\text{mod}.\ 3\right)$ は二つの解 $\alpha\equiv\pm1\hphantom{m}\left(\text{mod}.\ 3\right)$ を有する．また $x^2\equiv1\hphantom{m}\left(\text{mod}.\ 4\right)$ は二つの解 $\beta\equiv\pm1\hphantom{m}\left(\text{mod}.\ 4\right)$ を有する．故に\[x^2\equiv1\hphantom{m}\left(\text{mod}.\ 12\right)\]は四つの解を有する．それらは\[\left.\begin{array}{r}x\equiv1\\\equiv1\end{array}\right\}\hspace{1em}\left.\begin{array}{r}x\equiv\hphantom{-}1\\\equiv-1\end{array}\right\}\hspace{1em}\left.\begin{array}{r}x\equiv-1\\\equiv\hphantom{-}1\end{array}\right\}\hspace{1em}\left.\begin{array}{r}x\equiv-1\\\equiv-1\end{array}\right\}\hspace{1em}\begin{array}{r}\left(\text{mod}.\ 3\right)\\\left(\text{mod}.\ 4\right)\end{array}\]から求められる，すなわち\[x\equiv1,\ \ x\equiv7,\ \ x\equiv5,\ \ x\equiv11\hphantom{m}\left(\text{mod}.\ 12\right)\]である．