フェルマーの小定理

概要

を素数、 を と互いに素な整数とするとき、

が成り立つ。これをフェルマーの小定理という。前提を満たせば、 を で割った余りが必ず になるという優れもの。

とにかく前提が肝なので、証明まで理解して、知識の漏れの無いように押さえておこう。

大学入試では、知っておかなければ解けない問題はないが、知っていると見通しが良くなる問題はちょいちょいある。（下の補足も参照）

例

例えば 、 とすると、

より確かに成り立っていることがわかる。

証明

以下、合同式の法は全て とする。

は素数なので、 は と互いに素となる。

まず、それぞれに を掛けた を で割った余りが互いに異なること () を、背理法で示す。

() の証明

を 〜 の中の相異なる つの整数（ とする）として、 と を で割った余りが同じだと仮定する。

このとき、差である は で割り切れることになるが、いま と は互いに素なので、 が の倍数となる。

ところが、上の設定から の範囲は

なので、 が の倍数となることは無い。よって矛盾が生じるので、() が示された。 ■

この () と、 が素数 と互いに素であることから、これら 個の整数を で割った余りとして、必ず 〜 が 回ずつ出てくることになる。（どの数がどの余りに対応するかはわからない）

よって、

を得る。

と、法である素数 は互いに素であるから、 で両辺を割ってよく

が成り立つことが示された。■

補足

フェルマーの小定理を使った演習問題の動画は、こちらのokedouのリンクから確認できる。

教科書には出てこない定理なので、入試で「フェルマーの小定理より」といきなり使って良いかどうかは意見が分かれるところ。個人的には、見通しを立てる道具として使って、答案を書くときには地道に書いた方が良いと考えている。

また、これは整数論の世界ですごく有名な定理であるものの、フェルマーの最終定理というオバケ定理があることによって名前に「小」がつけられていて、可哀想である。