SURトップ > SURの数学 FAQ > 整数の合同ってどんなもの?
SUR の数学 FAQ ●それって何?シリーズ
整数の合同ってどんなもの?

合同式の考え方と基本性質

「三角形の合同」というのは,「平行移動・回転移動・対称移動でぴったり重なる」という意味でした。整数の合同というのは,たとえば

……≡-13≡-6≡1≡8≡15≡22≡……
……≡-12≡-5≡2≡9≡16≡23≡……
……≡-11≡-4≡3≡10≡17≡24≡……

という関係のことです。

この場合だと,「7で割った余りが等しい整数は同じとみなして,整数全体を7種類に分類しよう」という発想です。


普通は上のようにずらずら並べることはなく,たとえば「2014≡3059 (mod 5)」というように書きます。「2014を5で割った余りと,3059を5で割った余りは等しい」と言葉で説明するより簡単ですね。このとき,以下の性質が成り立ちます:

簡単にいえば,「足し算,引き算,掛け算はイコールと同じように計算できる」ということです。ただし,割り算はとりあえず保留しておきます。これはすべて整数の世界の話なので,「割り切れなかったらどうなるの?」と聞かれたら困りますし。


いきなりできる応用

問1。2921×3753 を 7 で割った余りを求めよ。

答。2921≡2 (mod 7),3753≡1 (mod 7) なので,2921×3753≡2×1 (mod 7) が成り立つ。よって,2921×3753 を 7 で割った余りは 2。

問2。9100を 7 で割った余りを求めよ。

答。9≡2 (mod 7) であることに注目すれば,9×9×9×9×……×9≡2×2×2×2×……×2 (mod 7) であるので,9100≡2100 (mod 7) が成り立つことがわかる。

ところが,23=8≡1 (mod 7) であることに注目すると,2100=(23)33×2≡133×2 (mod 7) という計算ができるので,9100 を7で割った余りは2である。

どうですか? 合同式の考え方自体はものすごく簡単なんですが,けっこう役に立ちそうかな,と思っていただければさいわいです。


合同式の「割り算」

先ほど保留した割り算について考えてみましょう。たとえば6÷3を計算するのは,「3x=6 となるxを求める」のと同じですから,こちらを考えてみましょう。

例1。4x≡1 (mod 7) となる整数xを求めよ。

答。全部試してみれば文句のつけようがないですよね。(整数は無数にあるんじゃないか? と思ったあなた。それは正しい。) 以下すべて mod 7 で,x≡0 なら 4x≡0。x≡1 なら 4x≡4。x≡2 なら 4x≡8≡1。x≡3 なら 4x≡12≡5……と書くのは面倒なので,表にしてみると,

x0123456
4x0415263

という具合になります。注目すべきは,7で割った余りは 0,1,2,……,6 のどれかなので,この7つを調べればすべての整数を調べたことになる,ということです。ここが合同式の一番のありがたみといっても過言でないでしょう。

よって,4x≡1 (mod 7) となるのは x≡2 (mod 7) のときです。おわり。

例2。3x≡6 (mod 9) となる整数xを求めよ。

答。「mod 9 での3倍の表」を書く。

x012345678
3x036036036

よって,3x≡6 (mod 9) となるのは x≡2 または 5 または 8 (mod 9) のとき。言い替えれば,x≡2 (mod 3) のとき。

例1をよく見ると,1≡8(mod 7) なので,「4x≡8(mod 7) ならば x≡2(mod 7)」という計算をしていることになりますね。これを一般化すると,以下のようになります:


さらに「割り算」

mod 7 の世界で考えると,4×2≡1(mod 7) なので,“2は4の逆数だ”と主張できそうです。(もちろん“4は2の逆数”でもあります。大学での数学では「逆数」ではなく「逆元」と呼びます)

さらに,3×5≡1(mod 7) ですし,1×1≡1(mod 7),6×6≡1(mod 7) なので,「mod 7 の世界では,0以外のすべての数は逆数をもつ」ことがわかります。この意味で「mod 7 の世界では割り算ができる」のです。

一方,mod 9 の世界では 3×□≡1(mod 9) となる数はありません。すなわち“3の逆数は存在しない”のです。ちょっとひねくれた世界ですね。

一般には,「p が素数のとき,mod p の世界では割り算ができる」ことが知られています。キチンと述べれば,「p が素数で,整数aがpで割り切れないならば,ax≡1(mod p) となる整数xが必ず存在する。しかも,x は mod p でただ1つに決まる」のです。


Wilson の定理

最後に,美しい定理をご紹介しましょう。

p が素数ならば,(p-1)!≡-1 (mod p)

という定理を「Wilson の定理」と呼びます。ここで,! は階乗の記号で,(p-1)!=1×2×3×…×(p-2)×(p-1) です。

実は,ここまで読み進めたみなさんにとっては,証明はもはや簡単です。たとえば,p=7 の場合だと 1×2×3×4×5×6 を計算するわけですが,先ほどの計算から2×4,3×5はいずれも1になり,残るのは 1 と 6≡-1 (mod 7) だけなので,全部かければ確かに -1 です。

一般のpの場合でも証明はほぼ同じで,互いに逆数になっているものを組み合わせて1を作っていけばいいのです。そうすると,自分自身が逆数になっている数だけは残ってしまいますが,「自分自身が逆数になっている数」ってのはどんなのだろう? と考えれば解決します。


合同式の考え方をざっと紹介しましたが,これは大学で「数論」と呼ばれている分野の入門になります。「p が素数ならば,mod p の世界で割り算ができる」というのは,大学での数学の言葉を借りれば「p が素数ならば,Z/pZ は有限体である」となって,数論の基本かつ大切な定理です。

もう少しこの世界をのぞいてみたい,というひとは,ぜひ姉妹編「フェルマーの小定理って何?」をごらんください。(yosi)


SUR
最終更新:2005年11月18日