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

整数

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$$

と表すことができます。

わか
わか

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」と「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個のグループに分けることができる。

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

合同式の利用方法

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

例題1

\(3^{30}\)を8で割った余りを求めよ

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

よって、あまりは 1

(合同式の累乗を利用して \(9^{15}\equiv1^{15}\))

「9」を「8」で割ったあまりが「1」であることを利用しています

例題2

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

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

よって、あまりは 24

「49」を「25」で割ったあまりが「−1」であることを利用しています

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

例題2

自然数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の倍数

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

まとめ:合同式(mod)

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

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

・定義は

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

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

$$a\equiv b\pmod n$$

と表す。

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

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

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

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

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

コメント

タイトルとURLをコピーしました