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）」の解説を終わります。
少しでも参考になれば幸いです。それではまた。
コメント