東大塾長の山田です。
このページでは、「合同式」について解説します。
合同式は、教科書では発展として扱われていますが、私大入試や国立の2次試験では合同式をわかっていないと解けない問題が普通に出題されます。
つまり、合同式はバッチリできなければいけません！
今回は「合同式とは何か？」という基本から、合同式の性質、そして例題を解きながら合同式の使い方を超わかりやすく解説していきます。
ぜひ最後まで読んで、合同式をマスターしてください！
1. 合同式とは？
\( a,b \)を整数，\( m \)を正の整数とする。
「\( a \) を \( m \) で割った余り」と「\( b \) を \( m \) で割った余り」が等しいことを
\( \displaystyle \large{ \color{red}{ a \equiv b \pmod m } } \)
と表す。この式を合同式といい，「\( a \) 合同 \( b \) モッド \( m \)」と読む。
「\( a \) を \( m \) で割った余り」と「\( b \) を \( m \) で割った余り」が等しいことは、\( a-b \) が \( m \) の倍数であることと同じです。
このとき、「\( a,b \) は \( m \) を法として合同である」といいます。
「法」とは「割る数」のことです。つまり、「\( m \) を法として合同」とは「\( m \) で割った余りが同じ」ということです。
例えば、「7を3で割った余り」と「4を3で割った余り」は、どちらも1となり等しいです。
よって「7と4は，3を法として合同である」といえ、\( \color{red}{ 7 \equiv 4 \pmod 3 } \) と表します。
・ \( 10 \equiv 5 \pmod 5 \)
・ \( 11 \equiv 3 \pmod 4 \)
・ \( 4 \equiv 0 \pmod 2 \)
・ \( 14 \equiv -1 \pmod 3 \)
・ \( 8 \equiv -2 \pmod {10} \)
2. 合同式の性質
合同式は次のような性質があります。
\( a \equiv b \pmod m, \ c \equiv d \pmod m \) のとき，次のことが成り立つ。
- \( \color{red}{ a+c \equiv b+d \pmod m } \)
- \( \color{red}{ a-c \equiv b-d \pmod m } \)
- \( \color{red}{ ac \equiv bd \pmod m } \)
- \( \color{red}{ a^n \equiv b^n \pmod m } \)（\( n \)は自然数）
つまり
- ①・②・③ → 方程式と同様に移行（加法・減法）や乗法が可能
- ④ → 両辺を何乗しても合同が成り立つ【重要!!】
ということです。
ただし、除法に関する性質は成り立たないので注意してください。
除法については、次の性質が成り立ちます。
\( a \)と\( m \)が互いに素なとき
\( \displaystyle \large{ \color{red}{ ax \equiv ay \pmod m \\
\Rightarrow \ x \equiv y \pmod m } } \)
例えば、\( 12, 18 \)は\( 6 \)を法として合同なので
\( \color{blue}{ 12 \equiv 18 \pmod 6 } \)
この両辺を3（3と法6は互いに素でない）で割ってみると
\( \color{blue}{ 4 \equiv 6 \pmod 6 } \)
となり、\( 4, 6 \)は\( 6 \)を法として合同ではないので、成り立ちません。
\( \color{red}{ 15 \equiv 30 \pmod 5 } \) を3（3と法5は互いに素）で割ると
\( \color{red}{ 5 \equiv 10 \pmod 5 } \) となり、成り立ちます。
このように、「割る数」と「法」が互いに素でないと、合同式の除法の性質は使えません。
3. 合同式の使い方
それでは、合同式を使った例題を実際にみてみましょう。
3.1 【例題1】合同式の方程式
次の合同式を解け。
(1) \( x+3 \equiv 1 \pmod 5 \)
(2) \( 5x \equiv 8 \pmod 9 \)
【解答】
(1) \( x+3 \equiv 1 \pmod 5 \)
与式より \( x \equiv 1-3 \equiv -2 \pmod 5 \)
\( -2 \equiv 3 \pmod 5 \) だから
\( \color{red}{ x \equiv 3 \pmod 5 \ \cdots 【答】 } \)
(2) \( 5x \equiv 8 \pmod 9 \)
与式の両辺に2をかけると
\( 10x \equiv 16 \pmod 9 \)
ここで \( 10x \equiv x \pmod 9 \)，\( 16 \equiv 7 \pmod 9 \) だから
\( \color{red}{ x \equiv 7 \pmod 9 \ \cdots 【答】 } \)
(2)【別解】
\( 8 \equiv 35 \pmod 9 \) だから
与式は \( 5x \equiv 35 \pmod 9 \)
法9と5は互いに素だから、両辺を5で割ると
\( \color{red}{ x \equiv 7 \pmod 9 \ \cdots 【答】 } \)
3.2 【例題2】余りを求める問題
\( 13^{100} \)を\( 6 \)で割った余りを求めよ。
【解答】
\( 13 \equiv 1 \pmod 6 \) だから
\( 13^{100} \equiv 1^{100} \pmod 6 \)（∵合同式の性質④）
\( 1^{100} \equiv 1 \pmod 6 \) だから
\( 13^{100} \equiv 1^{100} \equiv 1 \pmod 6 \)
よって \( 13^{100} \)を\( 6 \)で割った余りは \( \color{red}{ 1 \ \cdots 【答】 } \)
3.3 【例題3】1の位の数を求める問題
\( 7^{555} \)の一の位の数を求めよ。
自然数の一の位の数は、その数を\( 10 \)で割ったときの余りです。
よって、\( 7^{555} \)を\( 10 \)で割ったときの余りを求めれば良いわけです。
【解答】
\( 7^2 \equiv 49 \equiv 9 \pmod {10} \)
\( 7^3 \equiv 343 \equiv 3 \pmod {10} \)
\( 7^4 \equiv 2401 \equiv 1 \pmod {10} \)
ゆえに \( 7^{555} \equiv 7^3 \cdot (7^4)^{138} \equiv 7^3 \equiv 3 \pmod {10} \)
よって，\( 7^{555} \)の一の位は \( \color{red}{ 3 \ \cdots 【答】 } \)
4. 合同式のまとめ
以上が合同式のついての解説です。合同式の便利さや使い方はしっかり理解できましたか？
合同式は大学入試では必要な知識なので、必ずマスターしておきましょう！
どうすればmodの値がもとめられますか？
この場合modのmは割る数です。