３．合同式（mod）～余りで分類する方法～
3.1 合同式の定義と演算
世の中には「合同式」という余りを計算するための非常に便利な道具があるのですが、残念なことに高校ではあまり深い内容まで扱ってもらえていないようです。
ここでは合同式というものを習ったことが無い人や理解が曖昧な人のために、合同式の定義から確認していきます。
● ● ● 《定義》 ● ● ●
２つの整数$a、b$を正の整数$n$で割ったときの余りが等しいとき、
「$a$と$b$は$n$を法として合同である」
といい、これを
「$a \equiv b \pmod{n}$」
と書く。これより、
$a \equiv b \pmod{n}$
$\iff $ ($a$を$n$で割った余り) $=$ ($b$を$n$で割った余り)
$ \iff \ \ a-b$ が$n$で割り切れる
が成り立つ。
● ● ● ● ● ● ● ●
以上が合同式の定義です。
式のまま考えると良く解らない人は次のような具体例で考えてみてください。
例えば$100$という数を$12$で割ると余りは$4$です。また、$64$という数も$12$で割ると余りは$4$ですから、合同式を用いて表せば、
$100 \equiv 64 \pmod{12}$
と書くことができます。基本はたったこれだけです。
しかしこれだけを知ったところで合同式のありがたみは全く伝わらないでしょうから、以下に合同式において可能な式変形を示しておきます。それぞれに名前が付いていますが、覚える必要は全くありません。
① 「反射律」：
$\small a \equiv a \pmod{n}$
② 「対称律」：
$\small a \equiv b \pmod{n} \Longrightarrow b \equiv a \pmod{n}$
③ 「推移律」：
$\small a \equiv b \pmod{n}$ かつ $\small b \equiv c \pmod{n}\Longrightarrow a \equiv c \pmod{n}$
これらより、$a \equiv b \pmod{n}$、$c \equiv d \pmod{n}$ならば以下の式変形が可能です。
（１） $a+c \equiv b+d \pmod{n}$
（２） $a-c \equiv b-d \pmod{n}$
（３） $ac \equiv bd \pmod{n}$
（４） $a^k \equiv b^k \pmod{n}$ （ただし$k$は任意の自然数）
このように合同式では基本的に割り算以外の四則演算が可能です（コレ重要！）。
しかし特殊な場合に限って割り算も可能となります。$ma \equiv mb \pmod{n}$であり、$m$と$n$の最大公約数$\text{GCD}(m,n)$が$1$、つまり$m$と$n$が互いに素であるとき、両辺を$m$で割ることができます。式に直すと、$$\small ma \equiv mb \pmod{n} \iff a \equiv b \pmod{n} \quad \cdots (*)$$となります。さらに、$ma \equiv mb \pmod{n}$であり、$m$と$n$の最大公約数$\text{GCD}(m,n)$が$j(\geqq 2)$のとき、両辺は$m$で、法$n$は$j$で割ることができます。式に直すと、$$\small ma \equiv mb \pmod{n} \iff a \equiv b \pmod{\dfrac{n}{j}}$$となります。このことより、$n$が$m$の倍数であれば、法も含めて$m$で割ることができます。
割り算についてまとめると、
（５）$\small ma \equiv mb \pmod{n} \iff a \equiv b \pmod{\dfrac{n}{\text{GCD}(m,n)}}$
となりますが、この変形は$\text{GCD}(m,n)=1$のときに行うことが大半だと思います。ですから割り算については$(*)$の形で覚えてしまって構いません。（$m$と$n$が互いに素であるという条件をお忘れなく！）
では先ほどの続きを。上記の性質より、$100 \equiv 4 \pmod{12}$、$64 \equiv 4 \pmod{12}$が言えます。また$$100 \equiv 64 \pmod{12}$$について、全ての項が$4$の倍数なので法も含めて$4$で割れば$$25 \equiv 16 \pmod{3} \quad \cdots (\text{#})$$となります。$$25 = 24+1 \equiv 1 \pmod{3}$$および$$16 =15+1 \equiv 1 \pmod{3}$$ですから、$(\text{#})$は正しいですね。
$12$で割ったときの余りが等しい数同士の差は$12$で割れるので、当然ですが$100 \equiv 64 \pmod{12}$より、$100-64=36 \equiv 0 \pmod{12}$も成り立ちます。確かにその差$36$は$12$で割り切れますよね。
ここで簡単な例題を取り上げてみます。
《解答例》以下、合同式はすべて$\text{mod }5$とする。
$18 = 15 + 3 \equiv 3 $より、$$\small 18^4+18^3+18^2+18 \equiv 3^4+3^3+3^2+3 $$となる。さらに$9 = 10-1 \equiv -1$より、$$\small \begin{align} & \quad 3^4+3^3+3^2+3 \\ &= 9^2+3 \cdot 9 +9 +3 \\ &\equiv (-1)^2+3 \cdot (-1)+(-1)+3 \\ &=0 \end{align}$$となるから、$18^4+18^3+18^2+18$を$5$で割った余りは$$0 \ \cdots \cdots (\text{答})$$である。
《解答例》以下、合同式はすべて$\text{mod }26$とする。
$2005 = 77 \cdot 26 + 3 \equiv 3 $、および、$42+x = 26+16+x\equiv 16+x$より、$16+x \equiv 3 $となるような$x$の最小値を求めればよい。$\small x \equiv 3-16=-13 \equiv 26-13=13$より、$x$は整数$k$を用いて$$x=26k+13$$と表せるから、このような$x$で最小のものは$k=0$としたときの$13$であり、これが求める最小値である。よって$$x=13 \ \cdots \cdots (\text{答})$$である。
（コメント）
$9 \equiv -1$などのように、解答例の中で負の値が度々出てきますが、これは$9$で割って$8$余るような整数を$$9k+8 \ (k \in \mathbb{Z})$$と書くか$$9k-1 \ (k \in \mathbb{Z})$$と書くかの違いに過ぎません。合同式では負の数を扱うことで計算の負担をグッと軽減できる場合があります。$(-1)^{100}$と$8^{100}$ではどちらの計算の方が大変か一目瞭然ですよね（笑）。
それから、合同の記号「$\equiv$」は$\pmod{\text{◯◯}}$という書き方の他に、あまり一般的ではないですが
「${\equiv}_{◯◯}$」
という書き方や
「${\equiv}_{(◯◯)}$」
という書き方があります。
例えば「$16 \equiv 106 \pmod{10}$」と書きたいときには
「$16 {\equiv}_{10} 106$」
や
「$16 {\equiv}_{(10)} 106$」
と書けるということです。こうすることで等号「$=$」と合同「$\equiv$」がスムーズに書き下せるというメリットが生まれますが、これらの記号はよっぽど激しい計算をしない限りあまり使いません。
・・・と、ここまでは前座で、次のページからがメインです。次の項では合同式の威力をさらに体感していただくために色々な例題を解いていきます。