最終更新:2019/04/30

合同式の意味とよく使う6つの性質

分野: 整数問題  レベル: 基本公式

合同式について,合同式の意味,6つの性質,合同式が何の役に立つのか,などを整理しました。

合同式とは

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

例えば,$7$ と $4$ は,どちらも $3$ で割った余りが $1$ です。これを,合同式では
$7\equiv 4\:\mathrm{mod}\:3$
と書きます。

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

より一般に,$a$ と $b$ を $n$ で割った余りが等しいとき,合同式では
$a\equiv b\:\mathrm{mod}\:n$
と書きます。

合同式のよく使う性質

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

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$ と $p$ が互いに素なら $b\equiv c$ が成立します。合同式の両辺を $a$ で割って良いのは,$a$ と $p$ が互いに素である場合のみです。

合同式において,足し算,引き算,かけ算は普通の等式と同様に行ってOKですが,割り算は $a$ と $p$ が互いに素という条件がつきます。(超重要)
証明は互いに素の意味と関連する三つの定理の定理2を参照して下さい。

5. 合同式のべき乗

$a\equiv b$ のとき,$a^n\equiv b^n$

$15^{10}$ を $4$ で割った余りを求めたい! しかし,$15^{10}$ を計算するのは大変。そこで $15\equiv -1\:\mathrm{mod}\:4$ なので,合同式の上の性質を使うと
$15^{10}\equiv (-1)^{10}=1$
と簡単に求まる。

合同式の性質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\:\mathrm{mod}\:5$ 」と書く方が楽です。
ほとんど差がないように感じますが,記述式である程度複雑な問題になると上記のような文言を大量に書く必要があるため,かなり差が出ます。また,考えている $n$ が明らかなときは最初に宣言した上で $\:\mathrm{mod}\:n$ を省略して書くこともできます。

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


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

$p$ が素数で $a$ が $p$ と互いに素なとき $a^{p-1}\equiv 1\:\mathrm{mod}\:p$
→フェルマーの小定理の証明と例題

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

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

合同式を使うさらに難しい話題

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

表記を簡略化することも本質的に重要です。

Tag: 素数にまつわる覚えておくべき性質まとめ
Tag: 数学Aの教科書に載っている公式の解説一覧