有關(guān)費爾馬小定理的推廣

2017-06-01 12:19:11楊燕妮

長春大學學報 2017年4期

關(guān)鍵詞：次方拉格朗歸納法

楊燕妮

(喀什大學數(shù)學與統(tǒng)計學院,新疆喀什 844006)

有關(guān)費爾馬小定理的推廣

楊燕妮

(喀什大學數(shù)學與統(tǒng)計學院,新疆喀什 844006)

首先用數(shù)學歸納法證明了費爾馬小定理，然后通過模p數(shù)系乘法的代數(shù)結(jié)構(gòu),不僅導(dǎo)出了公式,同時也證明了費爾馬小定理。進一步將此方法推廣到了一般模n和任何有限交換群上。最后,借助拉格朗日定理建立了有限非交換群上同樣的公式。可見,費爾馬小定理是群論最基本的拉格朗日定理之特例。

交換群；非交換群；費爾馬小定理；歐拉定理；拉格朗日定理

費爾馬小定理[1]是近代密碼學瑞沙葉算法[2-3]的理論基礎(chǔ)。本文從費爾馬小定理的證明出發(fā),分析與p互素的整數(shù)在乘法運算下的代數(shù)結(jié)構(gòu),并將其推廣到非素數(shù)n對應(yīng)的歐拉定理[4]和一般抽象群的元素上。最終發(fā)現(xiàn)費爾馬小定理竟然是群論中拉格朗日定理[5]的簡單推論。

1 費爾馬小定理的歸納法證明

費爾馬小定理設(shè)p為一正素數(shù)，若a∈且p|a,則：ap-1≡1(modp),?a∈,p|a。

(1)

眾所周知,數(shù)學歸納法僅適用于正整數(shù)。因此,需先對a作歸納,然后再推廣到任意整數(shù)。此外,數(shù)學歸納法的關(guān)鍵是由a的p-1次方推出a+1的p-1次方。但在模p下,要將(a+1)p-1展開化簡并不易。若將a+1取p次方,然后再模p則簡單的多。事實上,由二項式定理可知,(a+1)p的展開式中,除頭尾兩項的系數(shù)是1外,其余都是p的倍數(shù),即：

上式分母中的所有整數(shù)因子均小于p,因此分子中的p不會被約掉。從而：(a+1)p≡ap+1(modp)。

顯然,這里的項數(shù)2可被任何正整數(shù)取代。換句話說,“和的p次方等于p次方的和”?？梢姡涸谀的環(huán)境下,只需將結(jié)論中的次方轉(zhuǎn)化成p次方即可。為此,將等式兩邊同乘以a,有ap≡a(modp)。當p|a時,此同余式與原同余式等價。

數(shù)學歸納法必須針對所有正整數(shù),不能排除p的倍數(shù)。然而,條件卻限制了p|a,怎么辦？注意到,修改版ap≡a(modp)對p的倍數(shù)顯然成立。因此,只需用數(shù)學歸納法證明：

ap≡a(modp),?a∈即可。

(2)

證明:(1)當a=1時,因1p≡1(modp),故同余式(2)成立;

(2)假設(shè)當a=k時,同余式(2)成立,即kp≡k(modp)。于是,(k+1)p≡kp+1≡k+1(modp)。即當a=k+1時,(2)也成立.由歸納原理可知,ap≡a(modp),?a∈成立。

進一步,當a=0時,同余式(2)顯然成立。對負整數(shù)a=-k,k∈和正素數(shù)p≠2,由于：

(-k)p=-kp?ap=(-k)p=-(kp)≡-k=a(modp),

此時(2)成立。當p=2時,因1+1≡0(mod2)。故-1≡1(mod2)。因此,(-k)p≡-kp(modp)恒成立。

綜上可知,同余式ap≡a(modp),對?a∈成立,于是費爾馬小定理得證。

2 完全剩余系與費爾馬小定理

眾所周知,雖然整數(shù)有無窮多,但是其模p后只剩p個余數(shù)0,1,2,…,p-1。通常用p表示在模p的加法和乘法下形成的代數(shù)結(jié)構(gòu)(p,+,·)。費爾馬小定理就是在此有限體的乘法結(jié)構(gòu)中產(chǎn)生的,其中且是一個交換群[4]。下面,在這個有限交換群上來構(gòu)建費爾馬小定理。

設(shè)a∈，且p|a,即(p,a)=1。群包含p-1個元素,它恰是定理中a的次冪。顯然,用a乘以群中的每個數(shù),可得包含p-1個a的倍數(shù)的集合：

(1a)(2a)…(p-1)a≡1·2…(p-1)(modp)或(p-1)!ap-1≡(p-1)!(modp)。

由消去律即得費爾馬小定理ap-1≡1(modp)。

3 費爾馬小定理與歐拉定理

其元素個數(shù)等于歐拉函數(shù)φ(n),即小于n且與n互素的正整數(shù)個數(shù)。它同樣具有交換群的代數(shù)結(jié)構(gòu)[5]?，F(xiàn)用與上節(jié)同樣的方法來構(gòu)建將費爾馬小定理推廣到一般模n的公式。

設(shè)a∈，且(a,n)=1。令考慮用a乘以群中每個數(shù)所得的集合

由消去律可知,其中的元素兩兩互異。于是

再由交換律可得：

(a1a2…aφ(n))aφ(n)≡a1a2…aφ(n)(modn)。

兩邊消去a1a2…aφ(n)后,就得到了費爾馬小定理的推廣——歐拉定理。

歐拉定理若a∈且(a,n)=1,則aφ(n)≡1(modn)。

4 有限交換群上的費爾馬小定理

總結(jié)前兩節(jié)的論證過程,一般可歸納為三個步驟:首先,在模環(huán)境下,利用消去律把看似不同的兩個集合Ga與G同歸于一;其次,將集合Ga中所有元素相乘,并利用交換律把a表成方冪形式;最后,再利用消去律即得所求公式。可見,論證的本質(zhì)在于G是有限交換群。為此,可將公式(1)推廣到一般有限交換群上。

定理設(shè)G是含有m個元素的交換群。若a∈G,則am=e,其中e為G的單位元。

證明:令G={a1,a2,…,am}。由消去律可知,Ga={a1a,a2a,…,ama}中的元素兩兩互異.于是,Ga=G.將Ga與G中的所有元素分別各自相乘,再由交換律將a表成方冪形式,可得：

(a1a2…?am)am=(a1a2…?am)。

消去a1a2…?am就得到am=e。