フェルマーの小定理
(Fermat's Little Theorem)

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

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

 
フェルマーの小定理

 p を素数,xをpで割り切れない整数とする。 このとき,xp−1−1はpで割り切れる。即ち,

p−1 ≡1  (mod p)

が成立する。

 整数の合同と1次合同式の項で,mを法とする整数の逆元のことを説明しました。mを法とする逆元はxとmが互いに素のとき,存在しました。これは,m=p:素数の場合は,xがpで割り切れないことを意味しますから,フェルマーの定理はm=p:素数の場合,pを法とするxの逆元はxp−2であることを示しています。

 例えば 101 は素数ですから,1100−1,2100−1,3100−1,4100−1,....98100−1,99100−1,100100−1 が すべて,101 で割り切れることが得られます。


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

例えば,

971234≡9734*((9710012)≡9734≡52 (mod 101)

となります。


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

p を素数,xを整数とする。 このとき,x−xはpで割り切れる。即ち,

≡x  (mod p)

が成立する。

 

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

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

フェルマーの小定理の証明

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

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


(補助定理)
 pを素数,a,bを整数とすると,

(a+b) ≡ a+b (mod p)


が成立する。

証明

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

(a+b) = apC1p-11pC2p-22pC3p-33 +...+ pCp-11p-1 +b

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


 上の補助定理で,a=1,b=1と置くと,

=(1+1) ≡ 1+1 ≡1+1≡2(mod p)

が得られます。また,a=2,b=1と置くと,

=(2+1) ≡ 2+1 ≡2+1≡3(mod p)

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

≡n(mod p)

が得られます。

 更に,(-1)≡-1(mod p)が任意の素数に対して,成立します。実際,p=2のときは -1≡1(mod 2)で成立します。更に,p>2なら,pは奇数ですから,(-1)=-1が成立します。以上から,全ての整数nに対して

≡n(mod p)

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


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

応用:フェルマーの素数判定
 

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

 n,整数,aをgcd(a,n)=1となる整数としたとき,

n-1 ≡1  (mod n)

とならなければnは合成数である。

 例えば,2231≡67  (mod 231) ですから,231は合成数であることが分かります。

更に,2120910≡9801  (mod 12091) ですから,12091は合成数であることが分かります。

 全ての合成数が上の方法で判定することはできません。例えば,29341はgcd(a,29341)=1となるaに対してa29340≡1(mod 29341)となります。しかし,実は,29341は合成数です。ですから,この合成数は上の判定法では,合成数であるとは判定してくれません。

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

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


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

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

181006655297358 ≡167696422262194 (mod 181006655297359)

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

 

まとめ

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