割り算の余りの問題は、余りによって場合分けをする必要があったり、記述量が多かったりとけっこう大変です。
そこで、今回は「合同式（mod）で余りの問題をサクッと解く方法」を紹介します。
よく出るパターンの入試問題 を使ってわかりやすく解説するので、ぜひ最後まで読んでみてください！
合同式(mod)の計算のしかた【Lv.0】
合同式（mod）の計算 についておさらいしたい人は、こちらのページを読んでおきましょう。
合同式(mod)の定義や性質から、計算のやり方までわかりやすく教えてほしい！ 合同式(mod)の計算を、例題を通して学びたい！ 整数や不定方程式の応用・入試問題を合同式(mod)で解けるようになりたい！ こういった要望に応えま[…]
合同式(mod)で割り算の余りの問題を解こう【Lv.1】
合同式（mod）をうまく使って「割り算の余りの問題をサクッと解く方法」を見ていきましょう。
【問題1】$m$ と $n$ を正の整数とする。$n$ を $m$ で割ると $7$ 余り、$n+13$ は $m$ で割り切れるとき、$m$ の値をすべて求めよ。[11 鹿児島大]
「$m$ で割った余り」の世界、「$\text{mod} \ m$」のもとで考えましょう。
- 【解答】を見る
-
【解答】
$n$ を $m$ で割ると $7$ 余るので
$ $ $m＞7$ かつ
$ $ $ n \equiv 7 \pmod m $
両辺に $13$ を足して
$ $ $ n+13 \equiv 20 \pmod m $・・・①
また、$n+13$ は $m$ で割り切れるので
$ $ $ n+13 \equiv 0 \pmod m $ ・・・②
①、② より
$ $ $ 20 \equiv 0 \pmod m $ ・・・（注）
$m＞7$ に注意すると
$ $ $ 20 = m , \ 2m $
∴ $ m = 10, \ 20 $
（注）$20$ を $m$ で割った余りが $0$ ということです。
$ $ $m$ が $7$ より大きい整数であることに注意すると、$ m = 10, \ 20 $ と分かります。
合同式（mod）を使わずにまともに解くやり方よりも、ずっとスッキリした解答が書けますね。
合同式(mod)で割り算の余りの問題を解こう【Lv.2】
【問題2】$a, \ b,\ c$ を正の整数とするとき、次の問題に答えよ。[類 12 関西大]
(1) $a^2$ を $3$ で割った余りは $0$ または $1$ であることを示せ。
(2) $a^2 + b^2 = c^2$ を満たすとき、$a, \ b $ の少なくとも一方は $3$ の倍数であることを示せ。
(1) $a^2$ を $3$ で割った余りは $0$ または $1$ であることを示せ。
$a$ を $3$ で割った余りに注目しましょう。
- 【解答】を見る
-
【解答】
$a$ を $3$ で割った余りは $0, \ 1, \ 2$ のいずれかなので、次のように場合分けできる。
$ $[1] $ a \equiv 0 \pmod 3 $ のとき
$ $ $ a^2 \equiv 0^2 \equiv 0 \pmod 3 $
∴ 余りは $0$
$ $[2] $ a \equiv 1 \pmod 3 $ のとき
$ $ $ a^2 \equiv 1^2 \equiv 1 \pmod 3 $
∴ 余りは $1$
$ $[3] $ a \equiv 2 \pmod 3 $ のとき
$ $ $ a^2 \equiv 2^2 \equiv 1 \pmod 3 $
∴ 余りは $1$ ・・・（注）
$ $[1]〜[3] より、$a^2$ を $3$ で割った余りは $0$ または $1$ である。[終]
（注）[3] $a \equiv 2 \equiv −1 \pmod 3 $ なので、場合分け [2]・[3]は、次のようにまとめて書いてもOK。
$ $ [2] $ a \equiv \pm 1 \pmod 3 $ のとき
$ $ $ a^2 \equiv (\pm 1)^2 \equiv 1 \pmod 3 $
$ $ ∴ 余りは $1$
(2) $a^2 + b^2 = c^2$ を満たすとき、$a, \ b $ の少なくとも一方は $3$ の倍数であることを示せ。
(1) の結果をうまく使います。
- 【解答】を見る
-
【解答】
(1) より、$c^2$ を $3$ で割った余りは $0 , \ 1$ のいずれかなので、次のように場合分けできる。
以下、$ \mod 3 $ のもとで（$3$ を法として）考える。
$ $ [ア] $ c^2 \equiv 0 $ のとき
$ $ $ a^2 + b^2 \equiv 0 $
∴ $ \begin{cases}
a^2 \equiv 0 \\
\\
b^2 \equiv 0 \\
\end{cases}$(1) の [1] より
$ $ $ \begin{cases}
a \equiv 0 \\
\\
b \equiv 0 \\
\end{cases}$∴ $a, \ b $ はともに $3$ の倍数である。
$ $ [イ] $ c^2 \equiv 1 $ のとき
$ $ $ a^2 + b^2 \equiv 1 $
∴ $ \begin{cases}
a^2 \equiv 1 \\
\\
b^2 \equiv 0 \\
\end{cases}$ または $ \begin{cases}
a^2 \equiv 0 \\
\\
b^2 \equiv 1 \\
\end{cases}$(1) の [2]、[3] より
$ $ $ \begin{cases}
a \equiv 1, \ 2 \\
\\
b \equiv 0 \\
\end{cases}$ または $ \begin{cases}
a \equiv 0 \\
\\
b \equiv 1, \ 2 \\
\end{cases}$∴ $a, \ b $ のうち一方は $3$ の倍数である。
$ $[ア]、[イ] より、$a, \ b $ の少なくとも一方は $3$ の倍数である。[終]
（注）$a^2 + b^2 = c^2$ より、次のように整理できます。※ $□^2 \equiv 0, \ 1 \pmod 3 $
$ c^2 $ を $3$ で割った余り $ a^2 $ を $3$ で割った余り $ b^2 $ を $3$ で割った余り [ア] 0 0 0 [イ] 1 1 0 0 1
こんな感じで、合同式（mod）を使うとスッキリと素早く解答を書くことができます。
ぜひマスターしておきましょう！
質問・要望があれば気軽にコメントください👍