合同式(mod)の意味とよく使う６つの性質

合同式とは，大雑把に言うと割り算の余りのみに注目した等式のことです。

例えば，$7$ と $4$ はどちらも $3$ で割った余りが $1$ です。これを，合同式では

$7\equiv 4 \pmod{3}$

と書きます。

上の合同式は「7合同4モッド3」と読みます。 $7$ と $4$ は $3$ で割った余りのみに注目すれば同じという意味です。

より一般に，$a$ と $b$ を $n$ で割った余りが等しいとき，合同式では

$a\equiv b\pmod{n}$

と書きます。なお，「$a$ と $b$ を $n$ で割った余りが等しいとき」という条件は「$a-b$ が $n$ の倍数のとき」と言い換えることもできます。

mod についての補足

• 上記の $n$ のことを「法」と呼びます。
• $\equiv$ と mod はセットで使われます。
• ただし，法 $n$ が文脈から明らかな場合は $\mathrm{mod}\:n$ という表記を省略する場合があります。
• mod の由来は「測り」を表す「modulo（modulus の活用形）」という単語です。

よく使う合同式の性質を6つ紹介します。特に4，5，6が重要です。以下では明示しない限り $\mathrm{mod}\:n$ を省略します。

1. 合同式の和

$a\equiv b,c\equiv d$ のとき，$a+c\equiv b+d$

が成立します。つまり，合同式は辺々足し算できます。

例えば，$\mathrm{mod}\:3$ では

$8\equiv 2$，$7\equiv 4$ なので，辺々足し算して

$15\equiv 6$

が成立します。

2. 合同式の差

$a\equiv b,c\equiv d$ のとき，$a-c\equiv b-d$

が成立します。つまり，合同式は辺々引き算できます。

3. 合同式の積

$a\equiv b,c\equiv d$ のとき，$ac\equiv bd$

が成立します。つまり，合同式は辺々かけ算できます。

特に，$ac\equiv bc$ です。

4. 合同式の商

$ab\equiv ac$ で，$a$ と $n$ が互いに素なら $b\equiv c$ が成立します。合同式の両辺を $a$ で割って良いのは，$a$ と $n$ が互いに素である場合のみです。

合同式において，足し算，引き算，かけ算は普通の等式と同様に行ってOKですが，割り算は $a$ と $n$ が互いに素という条件がつきます（超重要）。

証明は互いに素の意味と関連する三つの定理の定理2を参照して下さい。

5. 合同式のべき乗

$a\equiv b$ のとき，$a^k\equiv b^k$

合同式の性質5の証明は，二項定理を用いてもよいですし，$a^n-b^n$ の因数分解により証明することもできます。 →因数分解公式（n乗の差，和）

6. 合同式の多項式

$a\equiv b$ で，$f(a)$ を整数係数多項式とするとき，$f(a)\equiv f(b)$

これは，合同式の性質1，3，5を組み合わせることで証明できます。

表記簡略化による本質的な嬉しさ

「$12$ と $7$ を $5$ で割った余りは等しい」と書くよりも
「$12\equiv 7\pmod{5}$」と書く方が楽です。

ほとんど差がないように感じますが，記述式で複雑な問題になると上記のような文言を大量に書く必要があるため，かなり差が出ます。また，繰り返しですが，法 $n$ が明らかなときは最初に宣言した上で $\mathrm{mod}\:n$ を省略して書くこともできます。

余計な情報が削ぎ落とされスッキリ表現されていることで，思考の助けとなります。このように，数学における「表記簡略化」は一見表面上の意味しかないように思われますが，「思考の助けになる」という意味でとても重要です。

実際に，多くの整数問題の定理や性質は合同式を用いることでスッキリとした形で書くことができます。

この性質を合同式なしで書いたらめんどくさいだけでなくて，ごちゃごちゃしていて何言ってるかよく分からないという状況に直面します。

というわけで，合同式の恩恵を最大限受けるために，よく使う性質を覚えてしまいましょう！

最短で得点力を上げる典型問題集【PDF】のT161は，合同式を知っていると見通しがよくなる入試レベルの問題です。

合同式は，平方剰余，原始根，オイラーの定理，ウィルソンの定理，中国剰余定理などなど整数論の有名な定理の多くに登場します。これらは数学オリンピックでは重要な話題です。

Tag:素数にまつわる覚えておくべき性質まとめ

Tag:数学Aの教科書に載っている公式の解説一覧