３．合同式（mod）～余りで分類する方法～

3.1　合同式の定義と演算

世の中には「合同式」という余りを計算するための非常に便利な道具があるのですが、残念なことに高校ではあまり深い内容まで扱ってもらえていないようです。

ここでは合同式というものを習ったことが無い人や理解が曖昧な人のために、合同式の定義から確認していきます。

 

●　　●　　●　　《定義》　　●　　●　　●

２つの整数$a、b$を正の整数$n$で割ったときの余りが等しいとき、

「$a$と$b$は$n$を法として合同である」

といい、これを

「$a\equiv b(\mathrm{mod}n)$」

と書く。これより、

$a\equiv b(\mathrm{mod}n)$

$⟺$ ($a$を$n$で割った余り) $=$ ($b$を$n$で割った余り)

$⟺a-b$ が$n$で割り切れる

が成り立つ。

●　　●　　●　　●　　●　　●　　●　　●

 

以上が合同式の定義です。

式のまま考えると良く解らない人は次のような具体例で考えてみてください。

例えば$100$という数を$12$で割ると余りは$4$です。また、$64$という数も$12$で割ると余りは$4$ですから、合同式を用いて表せば、

$100\equiv 64(\mathrm{mod}12)$

と書くことができます。基本はたったこれだけです。

しかしこれだけを知ったところで合同式のありがたみは全く伝わらないでしょうから、以下に合同式において可能な式変形を示しておきます。それぞれに名前が付いていますが、覚える必要は全くありません。

これらより、$a\equiv b(\mathrm{mod}n)$、$c\equiv d(\mathrm{mod}n)$ならば以下の式変形が可能です。

このように合同式では基本的に割り算以外の四則演算が可能です（コレ重要！）。

しかし特殊な場合に限って割り算も可能となります。$ma\equiv mb(\mathrm{mod}n)$であり、$m$と$n$の最大公約数$\text{GCD}(m,n)$が$1$、つまり$m$と$n$が互いに素であるとき、両辺を$m$で割ることができます。式に直すと、$$ma\equiv mb(\mathrm{mod}n)⟺a\equiv b(\mathrm{mod}n)\cdots (\ast )$$となります。さらに、$ma\equiv mb(\mathrm{mod}n)$であり、$m$と$n$の最大公約数$\text{GCD}(m,n)$が$j(\geqq 2)$のとき、両辺は$m$で、法$n$は$j$で割ることができます。式に直すと、$$ma\equiv mb(\mathrm{mod}n)⟺a\equiv b(\mathrm{mod}{\displaystyle \frac{n}{j}})$$となります。このことより、$n$が$m$の倍数であれば、法も含めて$m$で割ることができます。

割り算についてまとめると、

（５）$ma\equiv mb(\mathrm{mod}n)⟺a\equiv b(\mathrm{mod}{\displaystyle \frac{n}{\text{GCD}(m,n)}})$

となりますが、この変形は$\text{GCD}(m,n)=1$のときに行うことが大半だと思います。ですから割り算については$(\ast )$の形で覚えてしまって構いません。（$m$と$n$が互いに素であるという条件をお忘れなく！）

---

では先ほどの続きを。上記の性質より、$100\equiv 4(\mathrm{mod}12)$、$64\equiv 4(\mathrm{mod}12)$が言えます。また$$100\equiv 64(\mathrm{mod}12)$$について、全ての項が$4$の倍数なので法も含めて$4$で割れば$$25\equiv 16(\mathrm{mod}3)\cdots (\text{\#})$$となります。$$25=24+1\equiv 1(\mathrm{mod}3)$$および$$16=15+1\equiv 1(\mathrm{mod}3)$$ですから、$(\text{\#})$は正しいですね。

$12$で割ったときの余りが等しい数同士の差は$12$で割れるので、当然ですが$100\equiv 64(\mathrm{mod}12)$より、$100-64=36\equiv 0(\mathrm{mod}12)$も成り立ちます。確かにその差$36$は$12$で割り切れますよね。

 

ここで簡単な例題を取り上げてみます。

---

《解答例》以下、合同式はすべて$\text{mod }5$とする。

$18=15+3\equiv 3$より、$${18}^4+{18}^3+{18}^2+18\equiv 3^4+3^3+3^2+3$$となる。さらに$9=10-1\equiv -1$より、$$\begin{array}{rl}& 3^4+3^3+3^2+3\\ & =9^2+3\cdot 9+9+3\\ & \equiv (-1{)}^2+3\cdot (-1)+(-1)+3\\ & =0\end{array}$$となるから、${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$の最小値を求めればよい。$x\equiv 3-16=-13\equiv 26-13=13$より、$x$は整数$k$を用いて$$x=26k+13$$と表せるから、このような$x$で最小のものは$k=0$としたときの$13$であり、これが求める最小値である。よって$$x=13\cdots \cdots (\text{答})$$である。

---

---

・・・と、ここまでは前座で、次のページからがメインです。次の項では合同式の威力をさらに体感していただくために色々な例題を解いていきます。

 

次へ進む　目次へ戻る