合同式とモジュロ演算：余りの計算と割り算ができる条件

$17$ を $5$ で割った余りは $2$ です。$27$ も $37$ も、$5$ で割れば余りは $2$。余りだけを見る立場では、この 3 つを区別しません。

同じ余りになる 2 数を $17\equiv 2(\mathrm{mod}5)$ と書きます。定義は、差の $17-2=15$ が $5$ の倍数だということ。

$5$ で割った余りは $0$ から $4$ の 5 通りしかありません。整数をこの 5 か所に振り分けたものが、$5$ を法とする世界です。

足し算とかけ算は先に余りにしてよい

$a\equiv b$ かつ $c\equiv d$ なら、$a+c\equiv b+d$ と $ac\equiv bd$ が成り立つ。大きな数のまま計算せず、先に余りへ落としてよい。

$123\times 456$ を $7$ で割った余りを求めます。$123=7\times 17+4$、$456=7\times 65+1$ です。

$$123\times 456\equiv 4\times 1=4(\mathrm{mod}7)$$

$56088=7\times 8012+4$ で、確かに余りは $4$。かけ算を先にすると 5 桁になるところが、$4\times 1$ で済みました。

引き算も通る。$2-4=-2$ で、$-2+5=3$ だから $2-4\equiv 3(\mathrm{mod}5)$ です。

かけ算の表を並べる

$0$ から $4$ までの積を $5$ で割った余りと、$0$ から $3$ までの積を $4$ で割った余りを並べます。

$5$ の表では、$0$ の行を除いてどの行にも $1$ が 1 度ずつ現れる。$4$ の表はそうなりません。

割り算ができる相手、できない相手

$2\times 3=6\equiv 1(\mathrm{mod}5)$ です。$2$ をかけて $1$ に戻す数が $3$ だから、$5$ を法とする世界で $2$ で割ることは、$3$ をかけることと同じになる。

$4$ を法とすると事情が変わる。$2$ の行は $0$、$2$、$0$、$2$ の 4 つだけで、$1$ がどこにも現れません。

$2x\equiv 1(\mathrm{mod}4)$ を満たす $x$ がないため、$2$ で割るという操作そのものが置けない。

$0$ でない 2 つをかけて $0$ になる

$4$ を法とすると $2\times 2=4\equiv 0$ です。$2$ は $0$ ではないのに、2 つかけると $0$ に落ちる。

$6$ を法とすれば $2\times 3=6\equiv 0$。実数では、$ab=0$ ならば $a$ か $b$ のどちらかが $0$ でした。余りの世界では違います。

こうなるのは法が素数でないときに限られます^[1]。法が合成数なら $n=ab$ と分けられ、その $a$ と $b$ をかけた時点で $0$ に落ちる。

割り算ができる条件

$a$ で割れるかどうかは、$ax\equiv 1(\mathrm{mod}n)$ を満たす $x$ があるかどうかで決まる。

$ax\equiv 1(\mathrm{mod}n)$ とは、$ax-1$ が $n$ の倍数だということ。$ax-1=-ny$ と置けば、次の形に直せます。

$$ax+ny=1$$

この式に整数解があるのは、$a$ と $n$ が互いに素なときに限ります^[2]。

両方の向きを確かめます。$ax+ny=1$ が成り立つなら、$a$ と $n$ の公約数は左辺を割るため $1$ も割る。だから公約数は $1$ だけ。

逆に $a$ と $n$ が互いに素なら、互除法を逆にたどれば $ax+ny=1$ の形に届きます。

例：互除法で $8$ の相手を見つける

$8x\equiv 1(\mathrm{mod}11)$ を解きます。まず $11$ と $8$ に互除法をあてる。

$$\begin{array}{rl}11& =8\times 1+3\\ 8& =3\times 2+2\\ 3& =2\times 1+1\end{array}$$

余りが $1$ になったため、$11$ と $8$ は互いに素です。ここから逆にたどる。

$$\begin{array}{rl}1& =3-2\\ & =3-(8-3\times 2)\\ & =3\times 3-8\\ & =3\times (11-8)-8\\ & =3\times 11-4\times 8\end{array}$$

$3\times 11$ は $11$ の倍数だから $0$ に落ち、$-4\times 8\equiv 1(\mathrm{mod}11)$ が残る。$-4+11=7$ だから $x\equiv 7$ です。

$8\times 7=56=11\times 5+1$ で、確かに $1$ に戻りました。

法が素数なら $0$ 以外はすべて割れる

$p$ を素数とし、$1\le a<p$ とします。$a$ と $p$ の最大公約数は $p$ の約数だから、$1$ か $p$ のどちらか。

$a$ は $p$ より小さいため $p$ では割れません。残るのは $1$ だけで、$a$ と $p$ は互いに素になる^[2]。

$7$ を法とすると、かけて $1$ になる数はこう並びます。

$1$ から $6$ まで、どれにも相手がいる。法が素数なら、$0$ 以外のどれでも割り算ができる。

例：$3x\equiv 5(\mathrm{mod}7)$ を解く

$3$ とかけて $1$ になるのは $5$ です。両辺に $5$ をかける。

$$\begin{array}{rl}15x& \equiv 25(\mathrm{mod}7)\\ x& \equiv 4(\mathrm{mod}7)\end{array}$$

$15\equiv 1$、$25\equiv 4$ を使いました。$3\times 4=12=7+5$ なので、確かに $5$ に戻ります。

解が $0$ 個にも 3 個にもなる

$8x\equiv 1(\mathrm{mod}10)$ には解がありません。$8x+10y=1$ と直すと、左辺は偶数で右辺は奇数だから。

原因は、$8$ と $10$ の最大公約数が $2$ で、$1$ を割れないところです。

$6x\equiv 3(\mathrm{mod}15)$ のほうは解が 3 つある。$x=3$、$8$、$13$ のどれでも成り立つ。

$$\begin{array}{rl}6\times 3& =18=15+3\\ 6\times 8& =48=45+3\\ 6\times 13& =78=75+3\end{array}$$

$6$ と $15$ の最大公約数は $3$ で、右辺の $3$ を割る。両辺と法を $3$ で割った $2x\equiv 1(\mathrm{mod}5)$ からは $x\equiv 3$ に決まり、これを $15$ の中で数え直すと 3 つに分かれる。

1 次方程式の感覚では、解は 1 つに決まるものでした。余りの世界では $0$ 個にも複数にもなります。

$5$ と $12$ は互いに素なので、$5$ ずつ進むと $12$ か所すべてを通る。途中に $1$ が現れるため、$5$ で割ることもできる。

$8$ と $12$ の最大公約数は $4$ です。$8$ ずつ進むと $0$、$8$、$4$ の 3 か所で閉じてしまい、$1$ を踏みません。

記号の由来

$\equiv$ を持ちこんだのはガウスで、1801 年の Disquisitiones Arithmeticae の第 1 節にあたります^[3]。

その第 2 条で記号を導入し、$-16\equiv 9(\mathrm{mod}5)$ と $-7\equiv 15(\mathrm{mod}11)$ を例に挙げている。負の数でも同じように使えることを、最初の例で見せています。

同じ場所の注に、選んだ理由も書いてある。等式と合同のあいだにある類似が大きいから、この記号にしたということ。

ルジャンドルは等号そのものを合同の意味で使っていました。ガウスは、等号のままではあいまいになるとして $\equiv$ に替えたと述べています。

足し算と引き算とかけ算は、法がいくつでも通る。割り算だけが相手を選び、その相手を決めているのは法との最大公約数です。

参考