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

合同式

合同式とは,わり算の余りのみに着目した等式のこと。

pic

合同式について,意味・性質・何の役に立つのか,などを整理しました。これを読めば数学における「mod」という記号の意味がわかります。

合同式(mod)とは

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

例えば,7744 はどちらも 33 で割った余りが 11 です。これを,合同式では

74(mod3)7\equiv 4 \pmod{3}

と書きます。

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

より一般に,aabbnn で割った余りが等しいとき,合同式では

ab(modn)a\equiv b\pmod{n}

と書きます。なお,「aabbnn で割った余りが等しいとき」という条件は「aba-bnn の倍数のとき」と言い換えることもできます。

mod についての補足

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

合同式のよく使う性質

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

1. 合同式の和

ab,cda\equiv b,c\equiv d のとき,a+cb+da+c\equiv b+d

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

例えば,mod3\mathrm{mod}\:3 では

828\equiv 2747\equiv 4 なので,辺々足し算して

15615\equiv 6

が成立します。

2. 合同式の差

ab,cda\equiv b,c\equiv d のとき,acbda-c\equiv b-d

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

3. 合同式の積

ab,cda\equiv b,c\equiv d のとき,acbdac\equiv bd

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

特に,acbcac\equiv bc です。

4. 合同式の商

abacab\equiv ac で,aann が互いに素なら bcb\equiv c が成立します。合同式の両辺を aa で割って良いのは,aann が互いに素である場合のみです。

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

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

5. 合同式のべき乗

aba\equiv b のとき,akbka^k\equiv b^k

151015^{10}44 で割った余りを求めたい! しかし,151015^{10} を計算するのは大変。そこで 151(mod4)15\equiv -1\pmod{4} なので,合同式の上の性質を使うと

1510(1)10=115^{10}\equiv (-1)^{10}=1

と簡単に求まる。

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

6. 合同式の多項式

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

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

合同式(mod)を使うメリット

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

12127755 で割った余りは等しい」と書くよりも
127(mod5)12\equiv 7\pmod{5}」と書く方が楽です。

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

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

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

pp が素数で aapp と互いに素なとき ap11(modp)a^{p-1}\equiv 1\pmod{p} →フェルマーの小定理の証明と例題

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

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

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

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

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

表記を簡略化することもとても重要です。

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

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