フェルマーは数論について多くの事実を発見しましたが，彼の名前の付く次の定理は初等整数論での基本的定理として 多くの場面で利用されています。 証明の難しさについては，フェルマーの最終定理とは全く比べものになりませんが，馴染み深く良く使われると言うことでは， 最終定理以上かもしれません。

　この定理は，１６４０年フレニクル(Frenicle de Bessy)宛の手紙の中にあるもので，次のものです。

　

フェルマーの小定理

　整数の合同と１次合同式の項で，ｍを法とする整数の逆元のことを説明しました。ｍを法とする逆元はｘとｍが互いに素のとき，存在しました。これは，ｍ＝ｐ：素数の場合は，ｘがｐで割り切れないことを意味しますから，フェルマーの定理はｍ＝ｐ：素数の場合，ｐを法とするｘの逆元はｘ^ｐ－２であることを示しています。

　例えば 101 は素数ですから，１¹⁰⁰－１，２¹⁰⁰－１，３¹⁰⁰－１，４¹⁰⁰－１，．．．．９８¹⁰⁰－１，９９¹⁰⁰－１，１００¹⁰⁰－１　が すべて，101 で割り切れることが得られます。

　この定理を使うと，ｐを法とする高い冪の計算が，ｐ以下の冪の計算に還元されることが分かります。

例えば，

９７^１２３４≡９７^３４＊（（９７^１００）^１２）≡９７^３４≡５２　(mod １０１）

となります。

　フェルマーの小定理は次の形（第二形式）で表されることもあります。上の形を第一形式ということにします。

　第一形式のフェルマーの小定理の両辺にｘを掛けたのが，第二形式ですから，第一形式から，第二形式が導かれます。また，ｘがｐで割り切れない場合，ｘにはｐを法とした逆元ｙが存在します。このｙを第二形式の両辺に掛けると，第一形式が得られます。

　以上から，第一形式と第二形式が同値であること示されました。

　フェルマーの小定理の証明は色々あります。ここでは２項定理を使った証明を紹介します。

まず，次の補助定理を証明します。

証明

　２項係数 _pC_i=p(p-1)* ・・・*(p-i+1)/i! の式の形を注意すると，これは，i=1，．．．p-1 に対して，ｐは_pC_iを割り切ることが分かります。実際 i!＝１・２・．．．i はｐと互いに素ですから，分子の内，(p-1)* ・・・*(p-i+1)を割り切ります。従って，_pC_iのｐは_pC_iに実際に現れ，従ってｐの倍数になります。従って ，２項展開

（ａ＋ｂ）^ｐ ＝ ａ^ｐ ＋_pC₁ａ^ｐ-1ｂ¹ ＋_pC₂ａ^ｐ-2ｂ² ＋_pC₃ａ^ｐ-3ｂ³ ＋．．．＋ _pC_p-1ａ¹ｂ^p-1 ＋ｂ^ｐ

の右辺の中間項はすべてｐで割り切れます。従ってこの両辺をｐを法として考えれば，求める式が得られます。（証明終）

　上の補助定理で，ａ＝１，ｂ＝１と置くと，

２^ｐ＝（１＋１）^ｐ ≡ １^ｐ＋１^ｐ ≡１＋１≡２(mod ｐ)

が得られます。また，ａ＝２，ｂ＝１と置くと，

３^ｐ＝（２＋１）^ｐ ≡ ２^ｐ＋１^ｐ ≡２＋１≡３(mod ｐ)

が得られます。以下同様にして，任意の正整数に対して，

ｎ^ｐ≡ｎ(mod ｐ)

が得られます。

　更に，（-１）^ｐ≡-１(mod ｐ)が任意の素数に対して，成立します。実際，ｐ＝２のときは　-１≡１(mod ２)で成立します。更に，ｐ＞２なら，ｐは奇数ですから，（-１）^ｐ＝-１が成立します。以上から，全ての整数ｎに対して

ｎ^ｐ≡ｎ(mod ｐ)

が成立することが分かります。

　これで，第二形式のフェルマーの小定理の証明が終わりました。

　フェルマーの小定理は，色々なところで理論的根拠として良く使われますが，数値的な応用もあります。それはフェルマーの小定理の対偶を使った，素数判定法です。次はフェルマーの小定理の対偶です。

　例えば，２^２３１≡６７  (mod ２３１)　ですから，２３１は合成数であることが分かります。

更に，２^{１２０９１０}≡９８０１  (mod １２０９１)　ですから，１２０９１は合成数であることが分かります。

　全ての合成数が上の方法で判定することはできません。例えば，２９３４１はｇｃｄ（ａ,２９３４１）＝１となるａに対してａ^{２９３４０}≡１(mod ２９３４１）となります。しかし，実は，２９３４１は合成数です。ですから，この合成数は上の判定法では，合成数であるとは判定してくれません。

　合成数で，上の判定法では判定できない合成数をカーマイケル（Carmichael）数と言います。このような数は無限にあることが1992年に証明されました。

　ですから，この判定法だけで合成数であることを決定は出来ませんが，ａを動かせば，かなりの割合で合成数であることを判定します。

　ここでこの判定法を実行する上での１つの問題があります。この判定法はｎが大きいときにｎ－１乗と言う大きな冪乗を計算する必要があります。この計算が膨大になれば，判定が実行できません。しかし，実は大きな数であっても冪乗は高速に出来る方法があります。この方法については，項を改めて説明します。

　ここでは，その方法を使ってTiny Basic で計算した，一つの例を挙げます。

２^{181006655297358} ≡167696422262194　(mod 181006655297359）

です。この計算はTiny Basic で十分可能です。181006655297359 は合成数であることが分かります。しかしその素因数分解を求めるのは素朴な方法では簡単なことではありません。

　 フェルマーの小定理は証明は簡単な定理ですが，初等整数論では基本的定理で多くの理論的基礎として出てきます。またそれだけでなく，素数判定の第一歩としての方法を与えてくれます。