SURトップ > SURの数学 FAQ > フェルマーの小定理ってどんなもの?
SUR の数学 FAQ ●それって何?シリーズ
フェルマーの小定理ってどんなもの?

Fermat の小定理とは,

p が素数ならば,任意の整数 n に対して np≡n (mod p) が成り立つ

という定理です。または,

p が素数で,整数 n が p で割り切れないならば, np-1≡1 (mod p) が成り立つ

という形で述べることもあります。(どちらも同じ意味なのは少し考えればわかります。)


証明

名前は「小定理」と控えめですが,美しい定理ですね。

証明の方法はいろいろありますが,「整数の合同ってどんなもの?」で説明したアイデアを利用してみましょう。

「mod 7 での4倍の表」を書いてみると,

x0123456
4x0415263

となります。これを式で書くと,

4×1≡4 (mod 7)
4×2≡1 (mod 7)
4×3≡5 (mod 7)
4×4≡2 (mod 7)
4×5≡6 (mod 7)
4×6≡3 (mod 7)

となりますね。この6つの式を,左辺同士・右辺同士それぞれ掛けてみると,

(4×1)×(4×2)×(4×3)×(4×4)×(4×5)×(4×6)≡1×2×3×4×5×6 (mod 7)
46×(6!)≡6! (mod 7)

となります。ここまで来ればこっちのもの。6!と7は互いに素なので,この等式の両辺を6!で割ってもよく,46≡1 (mod 7) が結論されます。

実は,Wilson の定理によれば 6!≡-1 (mod 7) なんですが……

この証明のキーポイントは,

の2点です。後者に関しては,pが素数なら (p-1)! はpで割り切れるはずがないのですぐに一般化ができますね。

前者を一般化すると, 「p が素数で, a は p で割り切れない整数とする。このとき,a×1,a×2,a×3,……,a×(p-1) の (p-1) 個の整数はいずれもpで割り切れず,かつ p で割った余りはすべて異なる」となります。

こちらの一般的な証明はなんとなく難しそうですが,「これら (p-1) 個の整数の中から2つを選んだとき,差がpで割り切れない」と考えれば解決します。


応用

mod 7 の世界で,「累乗の表」を作ってみましょう。たとえば,「mod 7 での 3xの表」を書くと

x12345678910
3x3264513264

のようになり,あるところから数字の並びが繰り返すことがわかります。

「あるところ」といっても,Fermat の小定理から 36≡1 (mod 7) なんだから,6個ずつ繰り返すに決まってるじゃないかと思ったひと。いいところに目をつけていますが,「mod 7 での 2xの表」だと

x12345678910
2x2412412412

という具合で,必ずしも6個ずつとは限りません。0は論外にしても,1x だと 1, 1, 1, …… だし, 6≡-1 (mod 7) だと -1, 1, -1, 1, ……ですね。

そこで,この状況を「mod 7 での 3 の位数は6である」「2の位数は3である」「1の位数は1である」「6の位数は2である」というように述べます。

整数 a に対して,ak≡1 (mod 7) となる最小の自然数 k を「mod 7 での a の位数」と呼ぶわけです。ak≡1 となる自然数が存在しない場合は,位数は0と約束します。

Fermat の小定理から,以下の定理が導かれます。

p が素数で,整数 n が p で割り切れないならば, mod p での n の位数は (p-1) の約数である。

さらに,ここでは証明しませんが,

p が素数ならば,mod p での位数がちょうど (p-1) になるような整数 n が存在する。

ということが知られており,「mod p での原始根」と呼ばれます。

こうした事実を抽象化して本質を暴きだすことが,大学での数学の第一歩となるのです。


今の話では,mod p の p は素数の場合ばかりを考えていました。p が素数でなかったら何が起こるのかは,みなさん自分の手で確かめてみてください。(yosi)


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