【整数】合同式（mod）とは【定義、性質、計算方法】

modってなに？

整数問題もっと簡単に求められるといいな、、、。

という人のために記事です。

今回は「合同式（mod）」について解説します。

今回の記事を読むことで

「合同式（mod）とは」「合同式の定義」「合同式の性質」「合同式の利用方法」

について理解することができます。

それでは見ていきましょう。

合同式とは
合同式の定義
合同式の性質
合同式の利用方法
まとめ：合同式（mod）

合同式とは

合同式とは、割り算のあまりのみに着目した等式

高校数学では、発展的な内容なため授業で習わない場合もあります。

しかし、合同式を使うことによって計算を楽に進めることができます。

「あまり」に着目して計算を進めることで、特に「整数問題」などで活躍します。

合同式の定義

合同式の定義について確認します。

合同式の定義

整数a,b　自然数nに対して

$a\equiv b\pmod n$

aをnで割ったあまり　と　bをnで割ったあまり　が等しいことを表し、

「aとbはnを法として合同である」という

例えば、

10と４は３で割った時の余りが「1」で等しいので

$10\equiv4\pmod3$

100と23は7で割った時の余りが「2」で等しいので

$100\equiv23\pmod7$

と表すことができます。

わか

mod は「割り算の余り」を表す「modulo（モジュロ）」という単語の頭文字です。

合同式の性質

続いて、合同式の性質を紹介します。

性質

合同式は「＝」と同じような性質があります

合同式の性質

$a\equiv b \pmod n\quad c\equiv d \pmod n$ のとき

①　 $a+c\equiv b+d$ 　（合同式の和）

②　 $a-c\equiv b-d$ 　（合同式の差）

③　 $a\times c\equiv b\times d$ 　（合同式の積）

④　 $a^k\equiv b^k$ 　（k：自然数）（合同式の累乗）

⑤　f(a)を整数係数多項式とすると

$f(a)\equiv f(b)$ 　（合同式の多項式）

合同式は　和　、差　、積　、累乗　、多項式　において「＝」と同様の計算をすることができます。

しかし「わり算」は特別なので注意しましょう。

注意

合同式の商（わり算）は特殊な場合しか成り立たないので注意してください。

以下が特殊な成立する場合です。

aとnが互いに素のとき

$a\times b\equiv a\times c\pmod n$ ならば

$b\equiv c$ 　（合同式の除法）

合同式は「わり算」に注意！

互いに素の解説は以下の記事を参考にしてください

証明

合同式の性質の証明を理解することで、合同式に対する理解を深めることができます。それぞれ証明していきます。

$a\equiv b \pmod n$ より

$a=p_1n+r\quad,\quad b=p_2n+r$

$c\equiv d \pmod n$ より

$c=p’_1n+r’\quad,\quad d=p’_2n+r’$

とおける。

①証明（合同式の和）

$a+c\equiv b+d\pmod n$ を示す

$a+c=p_1n+r+p’_1n+r’$

$=(p_1+p’_1)n+\color{red}{r+r’}$

$b+d=p_2n+r+p’_2+r’$

$=(p_2+p’_2)n+\color{red}{r+r’}$

したがって $a+c\equiv b+d\pmod n$

②証明（合同式の差）

$a-c\equiv b-d\pmod n$ を示す

$a-c=(p_1n+r)-(p’_1n+r’)$

$=(p_1-p’_1)n+\color{red}{r-r’}$

$b-d=(p_2n+r)-(p’_2+r’)$

$=(p_2-p’_2)n+\color{red}{r-r’}$

したがって $a-c\equiv b-d\pmod n$

③証明（合同式の積）

$a\times c\equiv b\times d\pmod n$ を示す

$a\times c=(p_1n+r)\times(p’_1n+r’)$

$=p_1p’_1n^2+(p_1r’+rp’_1)n+\color{red}{rr’}$

$b\times d=(p_2n+r)\times(p’_2n+r’)$

$=p_2p’_2n^2+(p_2r’+rp’_2)n+\color{red}{rr’}$

したがって $a\times c\equiv b\times d\pmod n$

④証明（合同式の累乗）

$a^k\equiv b^k$ を示す

$a^k=(p_1n+r)^k$

$=(p_1n)^k+_kC_1(p_1n)^{k-1}r+\cdots+_kC_{k-1}p_1nr+\color{red}{r^k}$

$b^k=(p_2n+r)^k$

$=(p_2n)^k+_kC_1(p_2n)^{k-1}r+\cdots+_kC_{k-1}p_2nr+\color{red}{r^k}$

したがって $a^k\equiv b^k$

⑤証明

$f(a)\equiv f(b)$

①、③、④の証明を組み合わせれば、証明できます。

「負のあまり」の導入

同号式は「負の数」を取り扱うことができます。

例えば

$16\equiv1\equiv\color{red}{-2}\pmod3$

$16=5\times3+1$

$16=6\times3-2$

以上のように考えれば、mod3で考えたとき「16」と「１」「−２」は同じものとして考えることができます。

つまり「負のあまり」を考えることによって、合同式では「負の数」も取り扱います。

「負の数のあまりの絶対値が小さいとき」など、計算を簡単にすることができます。

絶対値の小さな「あまり」を考えることで、計算が楽になる

全ての自然数を「あまり」でグループ分けできる

合同式で、全ての整数をグループ分けを表すことができます。

例えば

全ての整数は３で割ったとき余りが０、１、２の３種類にグループ分けすることができます。

$n\equiv0\pmod3$

$n=3,6,9,12,15,\cdots$

全ての３の倍数

$n\equiv1\pmod3$

$n=1,4,7,10,13,\cdots$

全ての（３の倍数＋１）の数

$n\equiv2\pmod3$

$n=2,5,8,11,14\cdots$

全ての（３の倍数＋２）の数

全ての自然数は、mod p において（pで割ったときの余りを考えると）

$n\equiv\underbrace{0,1,2\cdots p-1}_{p個}$

（余りが０、１、２、・・・、p−１）

p個のグループに分けることができる。

自然数を、あまりで分類するのは、「整数問題や証明」で使うので、合同式は使用する場面があります。

合同式の利用方法

それでは、合同式をどのように使うのか例題を通じて理解しましょう。

例題１

$3^{30}$ を８で割った余りを求めよ

$3^{30}\equiv3^{2\cdot15}\equiv9^{15}\equiv1^{15}\equiv1\pmod8$

よって、あまりは　１

（合同式の累乗を利用して　 $9^{15}\equiv1^{15}$ ）

「９」を「８」で割ったあまりが「１」であることを利用しています

例題２

$7^{50}$ を25で割った余りを求めよ

$7^{50}\equiv7^{2\cdot25}\equiv49^{25}\equiv(-1)^{25}\equiv-1\equiv24\pmod25$

よって、あまりは　２４

「４９」を「２５」で割ったあまりが「−１」であることを利用しています

余りが「１」か「−１」となる累乗の数を探す

例題２

自然数nに対して、 $n^5-n$ が3の倍数であることを示せ。

1. 　 $n\equiv0\pmod3$ のとき

$n^5-n\equiv0^5-0\equiv0\pmod3$

したがって３の倍数

2.　 $n\equiv1\pmod3$ のとき

$n^5-n\equiv1^5-1\equiv0\pmod3$

したがって３の倍数

3.　 $n\equiv2\pmod3$ のとき

$n^5-n\equiv2^5-2\equiv30\equiv0\pmod3$

したがって３の倍数

（※ $n\equiv-1$ のときとしてもよい）

1,2,3より　 $n^5-n$ は3の倍数

整数係数多項式の場合、代入ができるので直感的に計算できますね。

まとめ：合同式（mod）

合同式（mod）のまとめは以下の通りです。

・合同式とは「合同式とは、割り算のあまりのみに着目した等式」

・定義は

整数a,b　自然数nに対して、

「aをnで割ったあまり」と「bをnで割ったあまり」が等しいことを

$a\equiv b\pmod n$

と表す。

・合同式は「和」「差」「積」「累乗」に関しては「＝」と同様に計算することができる（「商」は同様に計算できないので注意）

合同式を利用した証明問題は大学入試でもよく出題されます。

以下の記事を参考にしてください。

以上で「合同式（mod）」の解説を終わります。

少しでも参考になれば幸いです。それではまた。