合同式（mod）の性質と使い方｜足し算・かけ算・累乗ができる証明・余りの計算・一の位と曜日の例題【数学A・大学受験】

合同式の定義と性質

証明

「余りが等しい」と「差が m の倍数」は同じこと

$a=mq_1+r_1$、$b=mq_2+r_2$（$0\le r_1,\ r_2<m$）とすると、$a-b=m(q_1-q_2)+(r_1-r_2)$。ここで $-m<r_1-r_2<m$ なので、$a-b$ が $m$ の倍数になるのは $r_1-r_2=0$、つまり余りが等しいときだけです。

足し算・引き算・かけ算ができる理由

$a-b=mk$、$c-d=ml$（$k,\ l$ は整数）とおきます。

$$\begin{aligned}(a+c)-(b+d)&=(a-b)+(c-d)=m(k+l)\\(a-c)-(b-d)&=(a-b)-(c-d)=m(k-l)\\ac-bd&=ac-bc+bc-bd=c(a-b)+b(c-d)=m(ck+bl)\end{aligned}$$

どれも $m$ の倍数なので、それぞれ合同です。かけ算は、$a=b+mk$、$c=d+ml$ を長方形の面積で表すと、$bd$ 以外の部分がすべて $m$ の倍数になる、と見ることもできます（下の図）。

累乗ができる理由

かけ算の性質で $c=a,\ d=b$ とすると $a^2\equiv b^2$。これをくり返すと $a^3\equiv b^3$、…、一般に $a^n\equiv b^n\pmod{m}$（数学的帰納法）。

大学受験（数学A）での使い方

大きな数の余りは、累乗して1（または $-1$）になる数を見つけるのがコツです。余りは $-1$ のように負の数で表してもかまいません（$6\equiv-1\pmod{7}$）。

よくある間違い

• 両辺を勝手に割る：$2\times3\equiv2\times0\pmod{6}$（どちらも6で割ると余り0）ですが、$3\equiv0\pmod{6}$ ではありません。割ってよいのは、割る数と $m$ が互いに素のときだけです。
• 指数まで mod m で小さくする：$10\equiv3\pmod{7}$ でも、$2^{10}\equiv2$、$2^3\equiv1\pmod{7}$ で一致しません。指数は「1になる周期」で減らします（$2^3\equiv1$ なら指数を3で割った余りを見る）。
• 負の数の余り：$-1$ を7で割った余りは $6$（$-1=7\times(-1)+6$）。答えは $0$〜$m-1$ にそろえます。

練習問題

1. 大学受験 $47\times53$ を 6 で割った余りを求めなさい。
   答えと解説を見る

   $47\equiv5$、$53\equiv5\pmod{6}$。$5\times5=25\equiv1$。答え $1$
2. 大学受験 $7^{2026}$ の一の位の数を求めなさい。
   答えと解説を見る

   $7^2=49\equiv9$、$7^4\equiv81\equiv1\pmod{10}$。$2026=4\times506+2$ なので $7^{2026}\equiv7^2\equiv9$。答え $9$
3. 大学受験 $5^{100}$ を 13 で割った余りを求めなさい。
   答えと解説を見る

   $5^2=25\equiv-1\pmod{13}$ なので $5^4\equiv1$。$5^{100}=(5^4)^{25}\equiv1$。答え $1$

関連する公式

• 整数の性質（約数の個数・倍数の判定）
• ユークリッドの互除法
• 1次不定方程式（整数解）
• 日暦算（曜日の計算）
• ガウス記号
• n進法
• フェルマーの小定理
• オイラーの定理
• 中国剰余定理

よくある質問

あわせて読みたい

• 合格大作戦 算数・数学公式辞典（公式一覧）