合同式(1)

整数$${a}$$を自然数$${n}$$で割った余りと、整数$${b}$$を自然数$${n}$$で割った余りが等しいことを
$${a \equiv b \mod n}$$
と表します。

厳密な定義は$${a - b}$$を$${n}$$で割った余りが$${0}$$であることを上式で表すと説明されることが多いですが、意味は同じ事です。

合同式は等式と同じように、両辺に同じ数を足したり、引いたり、掛けたり、割ったりしても式が壊れないという重要な性質があります。

ただし、割る場合だけ注意が必要です。

この証明を今回の記事で行います。

$${a \equiv b \mod n}$$の両辺に対して、定整数$${k}$$を使ってある操作をします。

まず、$${a + k\equiv b + k \mod n}$$が成り立ちます。

この証明は、合同式の厳密な定義を採用するとやりやすいです。

前提が$${a \equiv b \mod n}$$なので何らかの整数を$${m}$$として
$${a - b = nm}$$が成り立ちます。

これは、$${a - b}$$を$${n}$$で割った余りが$${0}$$であるということは$${a - b}$$は$${n}$$の倍数であるという事実を使っています。

そして、$${a - b = nm}$$に$${k}$$をうまくねじ込みます。
$${(a + k) - (b + k) = nm}$$

$${(a + k) - (b + k) = nm}$$ということは、合同式の定義から$${a + k\equiv b + k \mod n}$$です。

証明完了です。

足し算が成り立つということは、引き算も成り立ちます。

$${a \equiv b \mod n}$$から$${a - b = nm}$$であり、$${k}$$をうまくねじ込むと$${(a - k) - (b - k) = nm}$$なので$${a - k\equiv b - k \mod n}$$です。

次に、掛け算について触れます。

同じように、$${a \equiv b \mod n}$$より$${a - b = nm}$$です。

掛け算の場合は、$${k}$$をうまくねじ込むのではなく、等式の性質を利用して、両辺を$${k}$$倍してみます。
$${k(a - b) = k(nm)}$$

つまり、$${ka - kb = n(km)}$$です。

$${k}$$と$${m}$$は整数ですので、$${km}$$も整数です。
ということは、$${ka - kb}$$を$${n}$$で割った余りは$${0}$$であることが導かれます。

合同式の定義から、$${ka \equiv kb \mod n}$$です。

最後に、注意が必要な割り算です。

今までの順番で行けば、$${k}$$が$${0}$$でない整数のとき$${a \equiv b \mod n}$$において$${\frac ak \equiv \frac bk \mod n}$$が成り立つ、となりますが、式の見栄えが悪いことと今回は商が整数以外のときは考慮しないため、少し工夫して話をスマートにします。

$${k \neq 0}$$のとき、$${ak \equiv bk \mod n}$$において$${a \equiv b \mod n}$$が成り立つか、を考えます。

どちらにせよ、合同式の両辺を定整数$${k}$$で割るとどうなるか、を主題にしています。

$${ak \equiv bk \mod n}$$より$${m}$$を整数として$${ak - bk = nm}$$です。

等式の左辺を$${k}$$でくくると$${k(a-b) = nm}$$です。

ここで、$${k}$$と$${n}$$が互いに素であれば、$${a-b}$$が$${n}$$の倍数であることが確定します。

$${k}$$と$${n}$$が互いに素でなければ、$${k}$$と$${n}$$は$${2}$$以上の共通因数を持つため、$${a-b}$$が$${n}$$の倍数であることが確定しません。

したがって、$${k}$$と$${n}$$が互いに素であれば、$${a-b}$$を$${n}$$で割った余りが$${0}$$であるため、合同式の定義から$${a \equiv b \mod n}$$です。

つまり言いたいことは、$${\mod n}$$において$${n}$$と割る数$${k}$$が互いに素であれば合同式の両辺を$${k}$$で割ることができます。

しかし、ミスを誘発するため、実際には合同式での割り算は極力避けられます。

このように、合同式は等式と似た性質を持ちます。

この性質を駆使して、余りに関する様々な帰結を導いていきます。