2014/04/26

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

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

$a$ と $b$ の $n$ で割った余りが等しいことを,
$a\equiv b\:\mathrm{mod}\:n$
と書くといろいろ便利。


上記の式は「 $a$ 合同 $b$ モッド $n$ 」と読みます。高校の新課程では合同式を扱っているようです。このページでは合同式を使うメリットと,合同式の恩恵を最大限受けるために覚えておくべき性質を紹介します。

合同式を使うメリット

表記簡略化による本質的な嬉しさ
「 $12$ と $7$ を $5$ で割った余りは等しい」と書くよりも
「 $12\equiv 7\:\mathrm{mod}\:5$ 」と書く方が楽です。
ほとんど差がないように感じますが,記述式である程度複雑な問題になると上記のような文言を大量に書く必要があるため,かなり差が出ます。また,考えている $n$ が明らかなときは最初に宣言した上で $\:\mathrm{mod}\:n$ を省略して書くこともできます。

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


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

$a\equiv b\:\mathrm{mod}\:p$ なら $a^n\equiv b^n\:\mathrm{mod}\:p$

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

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

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

合同式のよく使う性質

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

$a\equiv b,c\equiv d$ のとき,
1:$a+c\equiv b+d$
2:$a-c\equiv b-d$
3:$ac\equiv bd$ 特に,$ac\equiv bc$
また,
4:$ab\equiv ac$ で, $a$ と $p$ が互いに素なら $b\equiv c$

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


$a\equiv b$ で,$f(a)$ を整数多項式とするとき,
5:$a^n\equiv b^n$
6:$f(a)\equiv f(b)$

この2つは非常に重要で多くの問題で活躍します。

$15^{10}$ を $4$ で割った余りは,$15\equiv -1\:\mathrm{mod}\:4$ なので,
$15^{10}\equiv (-1)^{10}=1$ と簡単に求まる。

5の証明は二項定理を用いてもよいですし,$a^n-b^n$ の因数分解により証明することもできます。
→因数分解公式(n乗の差、和)

6は,1,3、5を組み合わせることで証明できます。


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

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

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

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