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

１０を７で割った余りは３

８を７で割った余りは１

である。

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

１０ ≡ ３　（mod７）

８ ≡ １　（mod７）

である。

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

１０と８の和（１０＋８）を７で割った余りは、余りの和（３＋１）を７で割った余りに等しい。

１０と８の差（１０－２）を７で割った余りは、余りの差（３－１）を７で割った余りに等しい。

１０と８の積（１０x８）を７で割った余りは、余りの積（３x１）を７で割った余りに等しい。

これを合同式で書くと、

１０＋８ ≡ ３＋１　（mod７）

１０－８ ≡ ３－１　（mod７）

１０・８ ≡ ３・１　（mod７）

である。

１０ ≡ ３　（mod７）

８ ≡ １　（mod７）

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

一般化すると、

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

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

割る数（modの数）は７でなくとも構わない。

これが一般に成り立つ。

さらに、

１０のｎ乗を７で割った余りは、３（１０を７で割った余り）のｎ乗を７で割った余りに等しい。

８のｎ乗を７で割った余りは、１（８を７で割った余り）のｎ乗を７で割った余りに等しい。

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

これを合同式で書くと、

１０ⁿ ≡ ３ⁿ　（mod７）

８ⁿ ≡ １ⁿ　（mod７）

である。

１０ ≡ ３　（mod７）

８ ≡ １　（mod７）

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

一般化すると、

割られる数のｎ乗を７で割った余りは、割られる数を７で割った余りのｎ乗を７で割った余りに等しい。

乗数 n は何でもよく、割る数（modの数）も７でなくとも構わない。

さらに、

１０の７乗を７で割った余りは、１０を７で割った余りに等しく、

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

これを合同式で書くと

１０^７ ≡ １０ ≡ ３　（mod７）

８^７ ≡ ８ ≡ １　（mod７）

である。

１０ ≡ ３　（mod７）

８ ≡ １　（mod７）

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

一般化すると

割られる数のｎ乗をｎで割った余りは、割られる数をｎで割った余りに等しい。

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

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

１０の（7-1）乗を７で割った余りは、必ず１

８の（7-1）乗を７で割った余りは、必ず１

になる。

これを合同式で書くと

１０^7-1 = １０^６ ≡ １　（mod７）（∵１０と７は互いに素）

８^7-1  = ８^６ ≡ １　（mod７）（∵８と７は互いに素）

である。

一般化すると、

割られる数のｎ－1乗を、割る数ｎ（modの数）で割った余りは必ず１になる。

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

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

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

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

１０ ≡ ３　（mod７）

８ ≡ １　（mod７）

１０＋８ ≡ ３＋１　（mod７）

１０－８ ≡ ３－１　（mod７）

１０・８ ≡ ３・１　（mod７）

１０＋ n ≡ ３＋ n　（mod７）

１０ー n ≡ ３ー n　（mod７）

１０・ n ≡ ３・ n　（mod７）

１０ⁿ ≡ ３ⁿ　（mod７）

８ⁿ ≡ １ⁿ　（mod７）

１０^７ ≡ １０ ≡ ３≡ ３^７　（mod７）

８^７ ≡ ８ ≡ １ ≡ １^７　（mod７）

１０^7-1 ≡ １０^６ ≡ １　（mod７）（∵１０と７は互いに素、かつ、７は素数）

８^7-1 ≡ ８^６ ≡ １　（mod７）（∵８と７は互いに素、かつ、７は素数）

---

結局、

１０と３など７の倍数だけ異なる数字の間で、以下の式

１０＋ n ≡ ３＋ n　（mod７）

１０ー n ≡ ３ー n　（mod７）

１０・ n ≡ ３・ n　（mod７）

１０ⁿ ≡ ３ⁿ　（mod７）

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

等式（＝）の加法、減法、乗法と同様に扱えることを意味している。

たとえば・・・

２ｘ^３ー３ｘ^２＋ｘ＋３

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

たとえば１０異なる数、１７と７などを用意すれば、

１７^３ ≡７^３ 　（mod １０）

１７^２ ≡７² 　（mod １０）

１７¹ ≡７¹ 　（mod １０）

１７⁰ ≡１７⁰　（mod １０）

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

である。すなわち、

２（１７）^３ー３（１７）^２＋（１７）＋３ ≡ ２（７）^３ー３（７）^２＋（７）＋３　（mod１０）

が成り立つ。

mod７で考えれば、

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

である。

すなわち、

２（１０）^３ー３（１０）^２＋（１０）＋３ ≡ ２（３）^３ー３（３）^２＋（３）＋３　（mod７）

が成り立つ。

なぜなら

１０^３ ≡３^３ 　（mod７）

１０^２ ≡３² 　（mod７）

１０¹ ≡３¹ 　（mod７）

１０⁰ ≡３⁰（mod７）

であるからだ。

２ｘ^３ー３ｘ^２＋ｘ＋３

に３を代入した時、７で割ったあまりは？

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

２０００ー３００＋１０＋３＝１７１３ ≡ ５（mod７）

ゆえに、５だ。

別に１０と３でなくとも、７異なる数であれば、８と１でもよい。

８ ≡ １　（mod７）

なのだから。

すなわち、

２（８）^３ー３（８）^２＋（８）＋３ ≡ ２（１）^３ー３（１）^２＋（１）＋３　（mod７）

が成り立つ。

２ｘ^３ー３ｘ^２＋ｘ＋３

に８を代入した時、７で割ったあまりは？

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

２－３＋１＋３ ≡ ３（mod７）

ゆえに、３だ。

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

たとえば

１０＋ n ≡ ４　（mod７）

ならば

１０ ≡ ４ー n　（mod７）

が成り立つ。

---

ここまで読んだ読者は、

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

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

実は、

１０・ n ≡ ３・ n　（mod７）

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

１０／n ≡ ３／ n　（mod７）

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

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

その条件とは、

両辺（上記例では１０や３）が、nでぴったり割り切れること。

さらに、割る数ｎはmodの数（上記例では７）と互いに素であること。

つまり、

１０／５ ≡ ４５／ ５　（mod７）

は成り立つ。

なぜなら、

１０／５ も ４５／ ５

も答えは整数であり

７と５は互いに素であるからだ。

もちろん

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

１０ ≡ ３　（mod７）

１０ ≡ ４５　（mod７）

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

---

例題

１３¹⁰⁰ を９で割った余りは？

１３¹⁰⁰

≡ ４¹⁰⁰  （mod９）

≡ ４^４ ４^９６ （mod９）

≡ ４^４（４⁸ ）^1２ （mod９）

≡ ４^４（４^９－１ ）^1２ （mod９）

≡ ４^４（1）^1２ （mod９）

≡ 256 (1) （mod９）

≡ 256 （mod９）

≡ 4　（mod９）

答　４