« Hippocrates theorem | トップページ | Sum and Product of Roots »

合同式のもとになる考え方

10を7で割った余りは3

8を7で割った余りは1

 

これを合同式で書くと・・・

10 ≡ 3 (mod7)

8 ≡ 1 (mod7)

である。

 

調べると、不思議なことに、

10と8の和(10+8)を7で割った余りは、余りの和(3+1)を7で割った余りに等しい。

10と8の差(10-2)を7で割った余りは、余りの差(3-1)を7で割った余りに等しい。

10と8の積(10x8)を7で割った余りは、余りの積(3x1)を7で割った余りに等しい。

これを合同式で書くと、

10+8 ≡ 3+1 (mod7)

10-8 ≡ 3-1 (mod7)

10・8 ≡ 3・1 (mod7)

である。

10 ≡ 3 (mod7)

8 ≡ 1 (mod7)

と比べてみると不思議さがわかる。

一般化すると、

あるふたつの数の和や差、積を、7で割った余りは、

もとの数を7で割った余りの和や差、積を、7で割った余りに等しくなる。

割る数(modの数)は7でなくとも構わない。

これが一般に成り立つ。

 

さらに、

10のn乗を7で割った余りは、3(10を7で割った余り)のn乗を7で割った余りに等しい。

8のn乗を7で割った余りは、1(8を7で割った余り)のn乗を7で割った余りに等しい。

ということもわかっている。

これを合同式で書くと、

10n ≡ 3n (mod7)

n ≡ 1n (mod7)

である。

10 ≡ 3 (mod7)

8 ≡ 1 (mod7)

と比べてみると不思議さがわかる。

一般化すると、

「ある数」のn乗を7で割った余りは、「ある数」を7で割った余りのn乗を7で割った余りに等しい。

乗数 n は何でもよく、割る数(modの数)も7でなくとも構わない。

 

さらに、

10の7乗を7で割った余りは、10を7で割った余りに等しく、

8の7乗を7で割った余りは、8を7で割った余りに等しい。

これを合同式で書くと

10 ≡ 10 ≡ 3 (mod

≡ 8 ≡ 1 (mod

である。

10 ≡ 3 (mod7)

8 ≡ 1 (mod7)

と比べてみると不思議さがわかる。

一般化すると

「ある数」のn乗をnで割った余りは、「ある数」をnで割った余りに等しい。

この場合、割る数 n (modの数)は乗数 n と一致していなければならない。

 

驚くのは、次の法則だ。なんと

10の(7-1)乗を7で割った余りは、必ず1

8の(7-1)乗を7で割った余りは、必ず1

になる。

これを合同式で書くと

107-1 = 10 ≡ 1 (mod)(∵10と7は互いに素)

7-1  = 8 ≡ 1 (mod)(∵8と7は互いに素)

である。

一般化すると、

「ある数」のn-1乗を、割る数n(modの数)で割った余りは必ず1になる。

これを「フェルマーの小定理」という。

ただし、これにはちょっと条件があり、割る数 n (modの数)は必ず素数でなければならない。しかも割る数 n と、「ある数」は互いに素でなければならない(約数を共有しない)。

 

こういう考え方が合同式のもとになっている。

 

ちなみに、上記例をすべて合同式で書けば、下記のようになる。

 

10 ≡ 3 (mod7)

8 ≡ 1 (mod7)

 

10+8 ≡ 3+1 (mod7)

10-8 ≡ 3-1 (mod7)

10・8 ≡ 3・1 (mod7)

 

10+ n ≡ 3+ n (mod7)

10ー n ≡ 3ー n (mod7)

10・ n ≡ 3・ n (mod7)

 

10n ≡ 3n (mod7)

n ≡ 1n (mod7)

 

10 ≡ 10 ≡ 3≡ 3 (mod

≡ 8 ≡ 1 ≡ 1 (mod

 

107-1 ≡ 10 ≡ 1 (mod)(∵10と7は互いに素、かつ、7は素数)

7-1 ≡ 8 ≡ 1 (mod)(∵8と7は互いに素、かつ、7は素数)

 


 

結局、

10と3など7の倍数だけ異なる数字の間で、以下の式

10+ n ≡ 3+ n (mod7)

10ー n ≡ 3ー n (mod7)

10・ n ≡ 3・ n (mod7)

10n ≡ 3n (mod7)

などがnにかかわらず成立するということは、合同式(≡)の加法、減法、乗法は、

等式(=)の加法、減法、乗法と同様に扱えることを意味している。

 

たとえば・・・

2xー3x+x+3

のような多項式関数があたえられたとき、

たとえば10異なる数、17と7などを用意すれば、

17≡7  (mod 10)

17≡72  (mod 10)

171 ≡71  (mod 10)

170 ≡170 (mod 10)

なのであるから、xに17を代入したときと7を代入したとき、それぞれの答えを10で割った余りは同じ

である。すなわち、

2(17)ー3(17)+(17)+3 ≡ 2(7)ー3(7)+(7)+3 (mod10)

が成り立つ。

 

mod7で考えれば、

xに7異なる数、たとえば10を代入したときと3を代入したとき、それぞれの答えを7で割った余りは同じ

である。

すなわち、

2(10)ー3(10)+(10)+3 ≡ 2(3)ー3(3)+(3)+3 (mod7)

が成り立つ。

なぜなら

10≡3  (mod7)

10≡32  (mod7)

101 ≡31  (mod7)

100 ≡30 (mod7)

であるからだ。

2xー3x+x+3

に3を代入した時、7で割ったあまりは?

このとき、3のかわりに10を代入してよく、するとカンタンなのだ。

2000ー300+10+3=1713 ≡ 5(mod7)

ゆえに、5だ。

 

別に10と3でなくとも、7異なる数であれば、8と1でもよい。

8 ≡ 1 (mod7)

なのだから。

すなわち、

2(8)ー3(8)+(8)+3 ≡ 2(1)ー3(1)+(1)+3 (mod7)

が成り立つ。

2xー3x+x+3

に8を代入した時、7で割ったあまりは?

このとき、8のかわりに1を代入してよく、するとカンタンなのだ。

2-3+1+3 ≡ 3(mod7)

ゆえに、3だ。

 

また、加法、減法に関しては、等式(=)と同様に移項することができる。

たとえば

10+ n ≡ 4 (mod7)

ならば

10 ≡ 4ー n (mod7)

が成り立つ。

 


 

ここまで読んだ読者は、

商に関してどうなっているのか?

と思うのではないだろうか。

実は、

10・ n ≡ 3・ n (mod7)

が成り立つからと言って、

10/n ≡ 3/ n (mod7)

は、一般には成り立たない。

ただし、ある条件がそろうと成りたつ。

その条件とは、

両辺(上記例では10や3)が、nでぴったり割り切れること。

さらに、割る数nはmodの数(上記例では7)と互いに素であること。

つまり、

10/5 ≡ 45/ 5 (mod7)

は成り立つ。

なぜなら、

10/5 も 45/ 5

も答えは整数であり

7と5は互いに素であるからだ。

もちろん

割る前の合同式、上記例では

10 ≡ 3 (mod7)

10 ≡ 45 (mod7)

が成り立つことは絶対条件である。


例題

13100 を9で割った余りは?

 

13100

≡ 4100  (mod9)

≡ 496 (mod9)

≡ 4(48 12 (mod9)

≡ 4(4-112 (mod9)

≡ 4(1)12 (mod9)

≡ 256 (1) (mod9)

≡ 256 (mod9)

≡ 4 (mod9)

答 4

 

« Hippocrates theorem | トップページ | Sum and Product of Roots »