第 $1$ 章 初 等 整 数 論
$\S\ 5.$ 合 同 式
$\boldsymbol{1.}$ 整数 $a$，$b$ の差が $m$ の倍数であるとき，$a$ と $b$ とは $m$ を法（modulus）として互いに合同であるといい，それを次のように記す．\[a\equiv b\hphantom{m}\left(\text{mod}.\ m\right).\]これは Gauss の記法である．合同とは congruent の訳語であって，それは幾何学でいう合同と同語である．$a\equiv b\hphantom{m}\left(\text{mod}.\ m\right)$ とは $m$ の倍数なる差を無視すれば，$a$ も $b$ も同じであるというように考えるのである．あたかも二つの合同な図形が，位置の差を無視すれば，全く合致するのと同様である．
合同ということは整数論において基本的である．しかし日常生活においても，普通に応用されているともいえよう．朝は五時に起き，夜は十時に寝るのは $24$ 時間を $\text{mod}.$ として生活を律するのである．暦は一年を $\text{mod}.$ として季節を定める．また干支，七曜などは $10$，$12$，$7$ などを $\text{mod}.$ とする合同に基づく．
合同は相等，相似，対等などと同じ範ちゅう（範疇）に属する関係であって，それらに共通な三つの規律に従うものである．すなわち
反射的 $a\equiv a\ \left(\text{mod}.\ m\right)$．
対称的 $a\equiv b$ ならば，$b\equiv a\ \left(\text{mod}.\ m\right)$．
推移的 $a\equiv b$，$b\equiv c$ ならば，$a\equiv c\ \left(\text{mod}.\ m\right)$．
要するに，合同な数は互いに合同で，同じ数と合同な数は互いに合同である．
この原則のために，合同な数を同類とし，不合同な数を異類として，すべての整数を確定的に分類することが可能である．
すなわち $m$ を法としての整数の一つの類とは，$m$ を法として互いに合同なすべての整数の集合である．
例えば，$2$ を法とするならば，すべての整数は偶数と奇数との二類に分かれる．
整数を大きさの順序に並べて，定理 $1.\ 2$によって，$m$ を法（除数）としての最小剰余を求めるならば，剰余 $0$，$1$，$2$，$\cdots\cdots$，$m-1$ が周期的に出てくる．その際，相等しい剰余を出す数がすなわち $m$ を法として互いに合同な整数で，それらが整数の一類を組成するのである．故に $m$ を法とすれば整数は $m$ 類に分かれる．
〔例〕 $\text{mod}.\ 7$ に関して次の各縦列の数がそれぞれ一つの類を組み立てる．
| ・ | ・ | ・ | ・ | ・ | ・ | ・ |
| $-14$ | $-13$ | $-12$ | $-11$ | $-10$ | $-9$ | $-8$ |
| $-7$ | $-6$ | $-5$ | $-4$ | $-3$ | $-2$ | $-1$ |
| $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ |
| $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | $13$ |
| $14$ | $15$ | $16$ | $17$ | $18$ | $19$ | $20$ |
| ・ | ・ | ・ | ・ | ・ | ・ | ・ |
故に $m$ 個の整数が，$m$ を法としての完全な代表の一組を形成するために必要かつ十分な条件は，それらの $m$ 個の整数のうち，どの二つもが，$m$ を法として不合同であることである．
例えば上記の表の各縦列から一つずつの数をとれば，$\text{mod}.\ 7$ に関する代表の一組が得られる．すなわち
| $0$， | $1$， | $2$， | $3$， | $4$， | $5$， | $6$； | |
| $0$， | $1$， | $2$， | $3$， | $-3$， | $-2$， | $-1$； | |
| $7$， | $-6$， | $9$， | $-4$， | $-10$， | $-9$， | $13$； | 等， 等． |
代表の一組（Repräsentantensystem）は読んで字の如しであるが，それをあるいは，剰余系（Restsystem，system of residues）ともいう．system は組であるが，それを系統または略して系というのである．剰余系は語の短いところがよい．ただし，剰余（residue，Rest）は拡張された意味でいう，すなわち $a\equiv b\hphantom{m}\left(\text{mod}.\ m\right)$ であるとき，$b$ を $a$ の剰余といって，それが法 $m$ よりも小さいことを要求しないのである．法よりも小なる剰余にこだわれば，類の代表の趣意に反する．自由に代表を選ぶ所が最も大切である．
$\boldsymbol{2.}$ 同一の法を有す合同式は加法，減法，乗法に関する限り，等式と同様に取り扱うことができるものである．
〔定理 $\boldsymbol{1.\ 11}$〕 $a\equiv a^\prime\hphantom{m}\left(\text{mod}.\ m\right)$，$b\equiv b^\prime\hphantom{m}\left(\text{mod}.\ m\right)$ ならば，\begin{alignat*}{1}a\pm b&\equiv a^\prime\pm b^\prime&\hphantom{m}&\left(\text{mod}.\ m\right),\\[2mm]ab&\equiv a^\prime b^\prime&\hphantom{m}&\left(\text{mod}.\ m\right).\end{alignat*} 一般に $a\equiv a^\prime$，$b\equiv b^\prime$，$c\equiv c^\prime$，$\cdots\cdots\left(\text{mod}.\ m\right)$ で，また $f\left(x,\ y,\ z,\ \cdots\cdots\right)$ が $x$，$y$，$z$，$\cdots\cdots$ に関する整係数の多項式ならば，\[f\left(a,\ b,\ c,\ \cdots\cdots\right)\equiv f\left(a^\prime,\ b^\prime,\ c^\prime,\ \cdots\cdots\right)\hphantom{m}\left(\text{mod}.\ m\right).\] 〔証〕 仮定によって
| $a\equiv a^\prime$ | $\hphantom{m}\left(\text{mod}.\ m\right)$，したがって， | $a-a^\prime$ | は $m$ の倍数． |
| $b\equiv b^\prime$ | $\hphantom{m}\left(\text{mod}.\ m\right)$，したがって， | $b-b^\prime$ | は $m$ の倍数． |
| 故に | $\left(a+b\right)-\left(a^\prime+b^\prime\right)=\left(a-a^\prime\right)+\left(b-b^\prime\right)$ は $m$ の倍数， |
| すなわち | $a+b\equiv a^\prime+b^\prime\hphantom{m}\left(\text{mod}.\ m\right)$． |
| 同様に | $a-b\equiv a^\prime-b^\prime\hphantom{m}\left(\text{mod}.\ m\right)$． |
| また | $ab-a^\prime b^\prime=\left(a-a^\prime\right)b+a^\prime\left(b-b^\prime\right)$ も $m$ の倍数． |
| すなわち | $ab\equiv a^\prime b^\prime\hphantom{m}\left(\text{mod}.\ m\right)$． |
| 特に | $a\equiv a^\prime\hphantom{m}\left(\text{mod}.\ m\right)$ ならば， |
| $Na\equiv Na^\prime\hphantom{m}\left(\text{mod}.\ m\right)$． |
| すなわち | $f\left(a,\ b,\ c,\ \cdots\cdots\right)\equiv f\left(a^\prime,\ b^\prime,\ c^\prime,\ \cdots\cdots\right)\hphantom{m}\left(\text{mod}.\ m\right)$． |
| 〔定理 $\boldsymbol{1.\ 12}$〕 | $ac\equiv bc\hphantom{m}\left(\text{mod}.\ m\right)$ | |
| のとき，$\left(c,\ m\right)=1$ なる条件のもとにおいて | ||
| $a\equiv b\hphantom{m}\left(\text{mod}.\ m\right)$. | ||
| 一般に $\left(c,\ m\right)=d$ ならば，$m=dm^\prime$ と置くとき， | ||
| $a\equiv b\hphantom{m}\left(\text{mod}.\ m^\prime\right)$. | ||
〔証〕 仮定によって\[ac\equiv bc\hphantom{m}\left(\text{mod}.\ m\right).\]すなわち $ac-bc=\left(a-b\right)c$ は $m$ の倍数．故に $\left(c,\ m\right)=1$ ならば，$a-b$ は $m$ の倍数（定理 $1.\ 6$），すなわち\[a\equiv b\hphantom{m}\left(\text{mod}.\ m\right).\] 一般に $\left(c,\ m\right)=d$ ならば，$m=dm^\prime$，$c=dc^\prime$ と置くとき， $\left(c^\prime,\ m^\prime\right)=1$ ；かつ $\left(a-b\right)c^\prime$ は $m^\prime$ の倍数，故に
| $a-b$ は $m^\prime$ の倍数， |
〔問題 $\boldsymbol{1}$〕 $a$ を十進法で表わして\[a=a_n10^n+\cdots\cdots+a_110+a_0\]とすれば，\begin{eqnarray*}a&\equiv&a_0+a_1+\cdots\cdots+a_n\hphantom{m}\left(\text{mod}.\ 9\right),\\[2mm]a&\equiv&a_0-a_1+\cdots\cdots+\left(-1\right){}^na_n\hphantom{m}\left(\text{mod}.\ 11\right).\end{eqnarray*} 〔解〕 $10\equiv1\hphantom{m}\left(\text{mod}.\ 9\right)$， $\therefore$ $10^k\equiv1\hphantom{m}\left(\text{mod}.\ 9\right)$．よって第一の合同式を得る．
また $10\equiv-1\hphantom{m}\left(\text{mod}.\ 11\right)$． $\therefore$ $10^k\equiv\left(-1\right){}^k\hphantom{m}\left(\text{mod}.\ 11\right)$．よって第二の合同式を得る．
| 〔例〕 | $\begin{array}{l}26384\equiv2+6+3+8+4=23\equiv2+3\equiv5\hphantom{m}\left(\text{mod}.\ 9\right).\\[1mm]26384\equiv4-8+3-6+2=-5\hphantom{m}\left(\text{mod}.\ 11\right).\end{array}$ |
これを用いて，例えば\[25683941\equiv941-683+25=283\equiv3\hphantom{m}\left(\text{mod}.\ 7\right).\] 同様に\[25683941\equiv283\equiv10\hphantom{m}\left(\text{mod}.\ 13\right).\] このような数字の遊戯からでも，整数論に興味が生ずるならば，幸いである．