![](https://waka-blog.com/wp-content/themes/cocoon-master/images/man.png)
modってなに?
整数問題もっと簡単に求められるといいな、、、。
という人のために記事です。
今回は「合同式(mod)」について解説します。
今回の記事を読むことで
「合同式(mod)とは」「合同式の定義」「合同式の性質」「合同式の利用方法」
について理解することができます。
それでは見ていきましょう。
合同式とは
合同式とは、割り算のあまりのみに着目した等式
高校数学では、発展的な内容なため授業で習わない場合もあります。
しかし、合同式を使うことによって計算を楽に進めることができます。
「あまり」に着目して計算を進めることで、特に「整数問題」などで活躍します。
合同式の定義
合同式の定義について確認します。
整数a,b 自然数nに対して
$$a\equiv b\pmod n$$
aをnで割ったあまり と bをnで割ったあまり が等しいことを表し、
「aとbはnを法として合同である」という
例えば、
10と4は3で割った時の余りが「1」で等しいので
$$10\equiv4\pmod3$$
100と23は7で割った時の余りが「2」で等しいので
$$100\equiv23\pmod7$$
と表すことができます。
![わか](https://waka-blog.com/wp-content/uploads/2021/10/4934_ViI8mgvj-150x150.png)
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\) (合同式の除法)
![](https://waka-blog.com/wp-content/uploads/2021/10/4934_ViI8mgvj-150x150.png)
合同式は「わり算」に注意!
互いに素の解説は以下の記事を参考にしてください
証明
合同式の性質の証明を理解することで、合同式に対する理解を深めることができます。それぞれ証明していきます。
\(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」と「1」「−2」は同じものとして考えることができます。
つまり「負のあまり」を考えることによって、合同式では「負の数」も取り扱います。
「負の数のあまりの絶対値が小さいとき」など、計算を簡単にすることができます。
絶対値の小さな「あまり」を考えることで、計算が楽になる
全ての自然数を「あまり」でグループ分けできる
合同式で、全ての整数をグループ分けを表すことができます。
例えば
全ての整数は3で割ったとき余りが0、1、2の3種類にグループ分けすることができます。
\(n\equiv0\pmod3\)
$$n=3,6,9,12,15,\cdots$$
全ての3の倍数
\(n\equiv1\pmod3\)
$$n=1,4,7,10,13,\cdots$$
全ての(3の倍数+1)の数
\(n\equiv2\pmod3\)
$$n=2,5,8,11,14\cdots$$
全ての(3の倍数+2)の数
全ての自然数は、mod p において(pで割ったときの余りを考えると)
$$n\equiv\underbrace{0,1,2\cdots p-1}_{p個}$$
(余りが0、1、2、・・・、p−1)
p個のグループに分けることができる。
自然数を、あまりで分類するのは、「整数問題や証明」で使うので、合同式は使用する場面があります。
合同式の利用方法
それでは、合同式をどのように使うのか例題を通じて理解しましょう。
\(3^{30}\)を8で割った余りを求めよ
$$3^{30}\equiv3^{2\cdot15}\equiv9^{15}\equiv1^{15}\equiv1\pmod8$$
よって、あまりは 1
(合同式の累乗を利用して \(9^{15}\equiv1^{15}\))
![](https://waka-blog.com/wp-content/uploads/2021/10/4934_ViI8mgvj-150x150.png)
「9」を「8」で割ったあまりが「1」であることを利用しています
\(7^{50}\)を25で割った余りを求めよ
$$7^{50}\equiv7^{2\cdot25}\equiv49^{25}\equiv(-1)^{25}\equiv-1\equiv24\pmod25$$
よって、あまりは 24
![](https://waka-blog.com/wp-content/uploads/2021/10/4934_ViI8mgvj-150x150.png)
「49」を「25」で割ったあまりが「−1」であることを利用しています
余りが「1」か「−1」となる累乗の数を探す
自然数nに対して、\(n^5-n\)が3の倍数であることを示せ。
1. \(n\equiv0\pmod3\)のとき
$$n^5-n\equiv0^5-0\equiv0\pmod3$$
したがって3の倍数
2. \(n\equiv1\pmod3\)のとき
$$n^5-n\equiv1^5-1\equiv0\pmod3$$
したがって3の倍数
3. \(n\equiv2\pmod3\)のとき
$$n^5-n\equiv2^5-2\equiv30\equiv0\pmod3$$
したがって3の倍数
(※\(n\equiv-1\)のときとしてもよい)
1,2,3より \(n^5-n\)は3の倍数
![](https://waka-blog.com/wp-content/uploads/2021/10/4934_ViI8mgvj-150x150.png)
整数係数多項式の場合、代入ができるので直感的に計算できますね。
まとめ:合同式(mod)
合同式(mod)のまとめは以下の通りです。
・合同式とは「合同式とは、割り算のあまりのみに着目した等式」
・定義は
整数a,b 自然数nに対して、
「aをnで割ったあまり」と「bをnで割ったあまり」が等しいことを
$$a\equiv b\pmod n$$
と表す。
・合同式は「和」「差」「積」「累乗」に関しては「=」と同様に計算することができる(「商」は同様に計算できないので注意)
合同式を利用した証明問題は大学入試でもよく出題されます。
以下の記事を参考にしてください。
以上で「合同式(mod)」の解説を終わります。
少しでも参考になれば幸いです。それではまた。
コメント