この記事では、「合同式 \((\bmod)\)」についてわかりやすく解説していきます。
合同式の性質や解き方、不定方程式との関係なども説明していきますので、ぜひこの記事を通してマスターしてくださいね。
目次
合同式とは？
合同式とは、割り算の余りが等しいことを表現した等式のことです。
\(a, b, n\) を整数、\(n \neq 0\) とすると、
\(a\) を \(n\) で割った余りと \(b\) を \(n\) で割った余りが等しいとき、次の合同式で表せる。
\begin{align}\color{red}{a \equiv b \pmod{n}}\end{align}
また、このことを「\(a, b\) は \(n\) を法として合同である」と言う。
合同式の記号と読み方
読み上げる際は、記号 \(\equiv\) を「合同」、記号 \(\bmod\) を「モッド」と読みます。
（例：\(a\) 合同 \(b\) モッド \(n\)）
また、割る数 \(n\) のことを「法」といいます。
よって、
「\(a\) と \(b\) を \(n\) で割った余りは等しい」
\(\iff\) 「\(a, b\) は \(n\) を法として合同である」
\(\iff\) 「\(a \equiv b \pmod{n}\)」
は同じことを意味しています。
合同式の例
慣れるまではなかなか理解しにくいので、具体的な数字を当てはめて練習しておくとよいでしょう。
（例）
- \(9\) と \(5\) を \(4\) で割った余りは等しい
\(\iff\) \(9\) と \(5\) は \(4\) を法として合同である
\(\iff\) \(\color{salmon}{9 \equiv 5 \pmod{4}}\) - \(28\) と \(13\) を \(5\) で割った余りは等しい
\(\iff\) \(28\) と \(13\) は \(5\) を法として合同である
\(\iff \color{salmon}{28 \equiv 13 \pmod{5}}\)
合同式で書くと、言葉で書くよりすっきりと表せますね。
また、余りが等しいという関係を守れば合同式をいくつ続けても構いません。
（例）
- \(37 \equiv 22 \equiv 2 \pmod{5}\)
- \(99 \equiv 49 \equiv 9 \equiv −1 \pmod{10}\)
合同式の性質とその証明
合同式には、重要な性質（計算規則）があります。
\(1\) つ \(1\) つの性質とその証明を確認していきましょう。
合同式の和・差・積
複数の合同式において、法が同じであれば辺々を足し算・引き算・かけ算できます。
\(a \equiv b \pmod{n}\), \(c \equiv d \pmod{n}\) のとき、以下が成り立つ。
- 和
\begin{align}\color{red}{a + c \equiv b + d \pmod{n}}\end{align} - 差
\begin{align}\color{red}{a − c \equiv b − d \pmod{n}}\end{align} - 積
\begin{align}\color{red}{ac \equiv bd \pmod{n}}\end{align}
\(a\) を \(n\) で割った余りを \(x\), \(b\) を \(n\) で割った余りを \(y\) とおくと、
\(a \equiv b \pmod{n}\), \(c \equiv d \pmod{n}\) のとき
\(\left\{\begin{array}{l}a = An + r_1 …① \\b = Bn + r_1 …② \\c = Cn + r_2 …③ \\d = Dn + r_2 …④ \end{array}\right.\)
（\(A, B, C, D\) は整数）
と表せる。
① \(\pm\) ③ より
\(\begin{align}a \pm c &= (An + r_1) \pm (Cn + r_2)\\&= (A \pm C)n + (r_1 \pm r_2)\\ &\equiv r_1 \pm r_2 \pmod{n} …⑤\end{align}\)
② \(\pm\) ④ より
\(\begin{align}b \pm d &= (Bn + r_1) \pm (Dn + r_2)\\&= (B \pm D)n + (r_1 \pm r_2)\\& \equiv r_1 \pm r_2 \pmod{n} …⑥\end{align}\)
⑤、⑥より
\(a \pm c \equiv r_1 \pm r_2 \equiv b \pm d \pmod{n}\)
以上より、
\(a \pm c \equiv b \pm d \pmod{n}\) が成り立つ。
（証明終わり）
① \(\times\) ③ より
\(\begin{align}ac &= (An + r_1)(Cn + r_2)\\&= ACn^2 + (Ar_2 + Cr_1)n + r_1r_2\\&= (ACn + Ar_2 + Cr_1)n + r_1r_2\\& \equiv r_1r_2 \pmod{n} …⑦\end{align}\)
② \(\times\) ④ より
\(\begin{align}bd &= (Bn + r_1)(Dn + r_2)\\&= BDn^2 + (Br_2 + Dr_1)n + r_1r_2\\&= (BDn + Br_2 + Dr_1)n + r_1r_2\\&\equiv r_1r_2 \pmod{n} …⑧\end{align}\)
⑦、⑧より
\(ac \equiv r_1r_2 \equiv bd \pmod{n}\)
以上より、
\(ac \equiv bd \pmod{n}\) が成り立つ。
（証明終わり）
また、\(c \equiv c \pmod{n}\) とすれば
- \(a + c \equiv b + c \pmod{n}\)
- \(a − c \equiv b − c \pmod{n}\)
- \(ac \equiv bc \pmod{n}\)
が成り立つことから、合同式は自由に移項したり、両辺を等倍したりできます。
（例）
- \(31 \equiv 23 \pmod{4}\)
\(\iff 8 \equiv 0 \pmod{4}\)
（両辺から \(23\) を引く = 右辺を左辺に移項） - \(12 \equiv −2 \pmod{5}\)
\(\iff 60 \equiv −10 \pmod{5}\)
（両辺に \(5\) をかける）
合同式の商
一方で、合同式を割り算するには、ある重要な条件を満たす必要があります。
\(a\) と \(n\) が互いに素のとき、
\begin{align}\color{red}{ab \equiv ac \pmod{n} \iff b \equiv c \pmod{n}}\end{align}
（見切れる場合は横へスクロール）
\(a\) と \(n\) が互いに素であるとき、
\(ab \equiv ac \pmod{n}\)
\(\iff ab − ac \equiv 0 \pmod{n}\)
\(\iff a(b − c) \equiv 0 \pmod{n}\)
より、\(a(b − c)\) は \(n\) の倍数である。
\(a\) と \(n\) は互いに素であるから、
\(b − c\) は \(n\) の倍数である。
したがって、
\(b − c \equiv 0 \pmod{n}\)
\(\iff b \equiv c \pmod{n}\)
以上より、
\(a\) と \(n\) が互いに素であるならば
\(ab \equiv ac \pmod{n} \iff b \equiv c \pmod{n}\) が成り立つ。
（証明終わり）
合同式をある数 \(a\) で割ってもよいのは、\(a\) と \(n\) が互いに素である場合に限られます。
「互いに素」については以下の記事で説明しています。
互いに素とは？意味や証明問題を簡単にわかりやすく解説！
一方で、合同な \(2\) 数と法が共に \(a\) の倍数であれば、法も含めて \(a\) で割ることができます。
\begin{align}\color{red}{ab \equiv ac \pmod{an} \iff b \equiv c \pmod{n}}\end{align}
（見切れる場合は横へスクロール）
例えば、次の合同式の割り算を考えてみましょう。
（例）
\(15 \equiv 45 \pmod{10}\)
これを \(15\) も \(45\) も \(15\) で割れるぞ！と計算してしまうと
\(1 \equiv 3 \pmod{10}\) （誤り）
\(1\) と \(3\) を \(10\) で割った余りは異なるため、つじつまが合いません。
これは、\(15\) と法 \(10\) が互いに素ではないからです。
一方、\(3\) と法 \(10\) は互いに素なので、両辺を \(3\) で割ることはできます。
\(3 \cdot 5 \equiv 3 \cdot 15 \pmod{10}\)
\(\iff 5 \equiv 15 \pmod{10}\)
\(5\) と \(15\) を \(10\) で割った余りは共に \(5\) なので、成り立ちます。
また、合同式の両辺と法はどれも \(5\) の倍数なので、法ごと \(5\) で割ることもできます。
\(5 \cdot 3 \equiv 5 \cdot 9 \pmod{5 \cdot 2}\)
\(\iff 3 \equiv 9 \pmod{2}\)
\(3\) と \(9\) を \(2\) で割った余りは共に \(1\) なので、成り立っていますね。
合同式のべき乗
合同式は、両辺をべき乗しても成り立ちます。
\(a \equiv b \pmod{n}\) のとき、\(k\) を自然数とすると以下が成り立つ。
\begin{align}\color{red}{a^k \equiv b^k}\end{align}
\(a^k − b^k\) \( = \) \((a − b)(a^{n−1} + a^{n−2}b + \cdots + ab^{n−2} + b^{n−1})\)
より、\(a^k − b^k\) は \(a − b\) で割り切れる。
\(a \equiv b \pmod{n}\) より
\(a − b \equiv 0 \pmod{n}\) であるから、
\(a^k − b^k \equiv 0\)
したがって
\(a^k \equiv b^k\) が成り立つ。
（証明終わり）
この性質は、大きな数を割った余りを求めるのにとても便利です。
（例）
\(15^{50}\) を \(7\) で割った余り
\(15 \equiv 1 \pmod{7}\) より、
\(15^{50} \equiv 1^{50} \pmod{7}\)
また、
\(1^{50} \equiv 1 \pmod{7}\) より
\(15^{50} \equiv 1 \pmod{7}\)
よって余りは \(1\)
合同式の多項式
合同式の和・差・積とべき乗の性質から、多項式においても合同式が成り立ちます。
\(a \equiv b \pmod{n}\) のとき、多項式 \(f(x)\) の係数が整数であれば以下が成り立つ。
\begin{align}\color{red}{f(a) \equiv f(b) \pmod{n}}\end{align}
合同式の計算問題の解き方
ここでは、合同式の計算問題の解き方をパターン別に紹介していきます。
【パターン①】合同式の方程式
まずは、最も基本的な合同式の方程式を解く問題です。
次の合同式を解け。
(1) \(x − 4 \equiv 3 \pmod{6}\)
(2) \(5x \equiv 13 \pmod{7}\)
合同式の性質を利用して、\(x\) について合同式を解きましょう。
(1)
\(x − 4 \equiv 3 \pmod{6}\) より
\(x \equiv 7 \equiv 1 \pmod{6}\)
よって、\(x \equiv 1 \pmod{6}\)
答え： \(\color{red}{x \equiv 1 \pmod{6}}\)
(2)
\(13 \equiv 20 \pmod{7}\) より
\(5x \equiv 20 \pmod{7}\)
法 \(7\) と \(5\) は互いに素であるから、両辺を \(5\) で割って
\(x \equiv 4 \pmod{7}\)
答え： \(\color{red}{x \equiv 4 \pmod{7}}\)
式変形のやり方はいくらでもあるので、別の方法で変形しても一致することを実感してみてくださいね！
【パターン②】余りを求める問題
合同式を利用すると、割り算の余りを求めることができます。
(1) \(16^{100}\) を \(5\) で割った余りを求めよ。
(2) \(2^{50}\) を \(7\) で割った余りを求めよ。
さすがに \(100\) 乗や \(50\) 乗は計算したくありませんね。
合同式のべき乗の性質を利用しましょう。
(1)
\(16 \equiv 1 \pmod{5}\) より、
\(16^{100} \equiv 1^{100} \equiv 1 \pmod{5}\)
よって、余りは \(1\)
答え： \(\color{red}{1}\)
(2)
\(8 \equiv 1 \pmod{7}\) より、
\(2^3 \equiv 1 \pmod{7}\)
\(\begin{align} 2^{50} &= 2^{3 \cdot 16 + 2} \\ &= (2^3)^{16} \cdot 2^2 \\ &= 4(2^3)^{16} \end{align}\)
より、
\(\begin{align} 2^{50} &= 4(2^3)^{16} \\ &\equiv 4 \cdot 1^{16} \\ &\equiv 4 \pmod{7} \end{align}\)
よって、余りは \(4\)
答え： \(\color{red}{4}\)
【パターン③】1 の位を求める問題
合同式を利用して、自然数の一の位を求めることもできます。
\(13^{100}\) の一の位を求めよ。
自然数の一の位の数は、その数を \(10\) で割ったときの余りと考えられますね。
\(13 \equiv 3 \pmod{10}\)
\(3^2 \equiv 9 \pmod{10}\)
\(3^3 \equiv 7 \pmod{10}\)
\(3^4 \equiv 1 \pmod{10}\)
より
\(\begin{align} 13^{100} &\equiv 3^{100} \\ &\equiv (3^4)^{25} \\ &\equiv 1^{25} \\ &\equiv 1 \pmod{10} \end{align}\)
よって \(13^{100}\) の一の位は \(1\)
答え： \(\color{red}{1}\)
【パターン④】不定方程式への利用（おまけ）
合同式は、二元一次不定方程式を解くのにも利用できます。
\(51x − 25y = 19\) の整数解を求めよ。
左辺と右辺が等しいことから、両辺を同じ数で割った余りも当然等しいはずです。
そこで、小さい方の係数を法とした合同式を立てるとうまく解けます。
\(51x − 25y = 19\) …①
\(25\) を法とすると、①より
\(51x − 25y \equiv 19 \pmod{25}\)
\(−25y \equiv 0 \pmod{25}\) から、
\(51x \equiv 19 \pmod{25}\)
\(51 \equiv 1 \pmod{25}\) より、
\(51x \equiv x \pmod{25}\)
よって \(x \equiv 19 \pmod{25}\)
したがって、\(k\) を整数とすると
\(x = 25k + 19\)
①より
\(\begin{align} y &= \frac{51x − 19}{25} \\ &= \frac{51(25k + 19) − 19}{25} \\ &= \frac{51 \cdot 25k + 50 \cdot 19}{25} \\ &= 51k + 38 \end{align}\)
答え： \(\color{red}{\left\{\begin{array}{l} x = 25k + 19\\ y = 51k + 38\end{array}\right.}\)（\(\color{red}{k}\)：整数）
以上で問題も終わりです。
合同式では、「余り」に着目することで大きな数でもとても扱いやすくなります。
合同式の計算にはコツが必要ですから、しっかり練習して、ぜひマスターしてくださいね！