§A4.5合同式の計算

1 同値関係であること

$\equiv$は同値関係です。反射律は$m \mid 0$から、対称律は$m\mid(a-b)$なら$m\mid(b-a)$から、推移律は$m\mid(a-b)$と$m\mid(b-c)$の和が$m\mid(a-c)$になることから、それぞれ一瞬で確かめられます。だから整数全体は法$m$ごとに$m$個の類（$0,1,\dots,m-1$の余りのグループ）へきれいに分割されます。

2 和・差・積は代表の取り方によらない

問題は、この分割の上で四則演算を「代表を選んで計算する」形で定義してよいか、です。$a \equiv a'$,$b \equiv b' \pmod m$のとき、

$$ab - a'b' = a(b - b') + b'(a - a')$$

と分解すると、右辺の2項はどちらも$m$の倍数（仮定より$m \mid (b-b')$,$m\mid(a-a')$）なので、左辺も$m$の倍数、つまり$ab \equiv a'b' \pmod m$。和・差も同様の分解で示せます。「別の代表を選んでも答えが変わらない」という、well-defined 性の確認そのものです（基礎解析の well-definedness の記事と全く同じ構造の議論です）。だから「$a \pmod m$の値だけ見て計算してよい」という、合同式の四則演算が正当化されます。

3 割り算はできるとは限らない

ところが割り算は同じようにいきません。たとえば

$$2 \times 3 \equiv 2 \times 8 \pmod{10}$$

（$6$と$16$はどちらも$10$で割ると余り$6$）は成り立ちますが、両辺を$2$で割った$3 \equiv 8 \pmod{10}$は成り立ちません（$3 \not\equiv 8$）。

$ca \equiv cb \pmod m$から$a \equiv b \pmod m$を結論してよいのは、$\gcd(c, m) = 1$のときに限られます。理由は、$m \mid c(a-b)$のとき、$c$と$m$が互いに素なら$m$の素因数はすべて$(a-b)$の側に落ちるしかなく、$m \mid (a-b)$が出るからです（先の例では$\gcd(2,10)=2 \ne 1$なので割り算が壊れます）。合同式で割り算をする前には、必ず割る数と法が互いに素かを確認する癖をつけてください。

4 べき乗の計算：余りは周期的に繰り返す

$a^1, a^2, a^3, \dots \pmod m$の列は、有限個の値しか取れないので、いずれ周期的に繰り返します。$7^{100}$の一の位（$\bmod 10$）を求めてみます。

$$7^1 \equiv 7,\quad 7^2 \equiv 9,\quad 7^3 \equiv 3,\quad 7^4 \equiv 1 \pmod{10}$$

で周期$4$に戻ってきます。$100 = 4 \times 25$なので$7^{100} \equiv (7^4)^{25} \equiv 1^{25} \equiv 1 \pmod{10}$——一の位は$1$です。指数がどれだけ大きくても、周期さえ見つければ一瞬で終わります。

5 曜日の計算

曜日は法$7$の合同式そのものです。今日を日曜日（$0$）とすると、$n$日後の曜日は$n \bmod 7$が$0$なら日曜、$1$なら月曜、……と決まります。たとえば$100$日後は$100 = 7 \times 14 + 2$なので、$2$日後と同じ曜日、つまり火曜日です。日数がどれだけ先でも、$7$で割った余りだけ見ればよいのが合同式の威力です。