有關(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。

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

在含有m個元素的非交換群G里,am=e,?a∈G是否成立?顯然,沒有交換性,要把元素a表為方冪形式很難。為此,考慮群G中由元素a生成的循環(huán)子群={an|n∈}={a,a2,a3,…,aT(a)=e}僅含T(a)個元素。若am=e,則T(a)|m。否則,由帶余除法可知,存在商q和余數(shù)r使得m=q·T(a)+r且0

反過來,T(a)|m是否也是am=e的充分條件呢?為此,令A(yù)=且k=T(a)。若A=G,則m=T(a),結(jié)論成立;若A≠G,則?b∈G但b?A?，F(xiàn)將已有的元素列表如下:

a,a2,a3,…,ak-1,e

ab,a2b,a3b,…,ak-1b,b.

由消去律不難看出,第二行的所有元素不僅兩兩相異,而且也不同于第一行的所有元素(若aib=aj,則b=aj-i∈A,與假設(shè)b?A矛盾)。上表中共有2·T(a)個元素。若它們就是G的所有元素,則結(jié)論已成立。否則,再選取不在這兩行的元素c,并考慮下面新的列表:

a,a2,a3,…,ak-1,e

ab,a2b,a3b,…,ak-1b,b

ac,a2c,a3c,…,ak-1c,c.

由消去律同樣可知,第三行的所有元素兩兩相異且不同于前兩行的所有元素。上表中共有3·T(a)個元素。如此繼續(xù)下去,每次構(gòu)造出的新元素均為T(a)個。因G是有限群,故在有限步后,不妨設(shè)為s,就會遍歷G中的所有元素。因此,可得m=s·T(a),即T(a)|m。

6 拉格朗日定理

設(shè)H

拉格朗日定理 設(shè)G是有限群。若H

證明:仿上節(jié)的論證,只需將方冪移至下標H={a1,…,ak-1,ak=e}即可(略)。

推論1 設(shè)G是有限群且T(G)=p。若p為素數(shù),則G是循環(huán)群。

證明:取非單位元a∈G且令H=,則1

推論2 若G是有限群且a∈G,則T(a)|T(G)。

證明:令H=,則T(a)=T(H)|T(G),得證。

推論3 若G是有限群且a∈G,則aT(G)=e。

證明:由推論2知T(a)|T(G)。設(shè)T(G)=r·T(a),r∈.于是,aT(G)=ar·T(a)=(aT(a))r=er=e。

推論4 設(shè)n∈,a∈。若(a,n)=1,則aφ(n)≡1(modn)。

推論5 設(shè)p是正素數(shù),a∈。若p|a,則ap-1≡1mod(p)。

事實表明,費爾馬小定理的確是拉格朗日定理的特例。

[1] 鄧勇.費爾馬小定理的一種奇特證明[J].首都師范大學學報(自然科學版),2015,36(2):8-9.

[2] 陳少真.密碼學基礎(chǔ)[M].北京:科學出版社,2008.

[3] 肖攸安,李臘元.數(shù)字簽名技術(shù)的研究[J].武漢理工大學學報(交通科學與工程版),2002,26(6):737-740.

[4] 張文鵬,李海龍.初等數(shù)論[M].西安:陜西師范大學出版社,2013.

[5] 張禾瑞.近世代數(shù)基礎(chǔ)(修訂本)[M].北京:高等教育出版社,2010.

責任編輯：程艷艷

OnGeneralizationofFermat’sLittleTheorem

YANGYanni

(CollegeofMathematicsandStatistics,KashgarUniversity,Kashgar844006,China)

Firstly, Fermat’s little theorem was proved by using mathematical induction. Secondly, the formula was obtained and Fermat’s little theorem was proved by using algebraic structure of residues system multiplication of modulop. Thirdly, this method was extended to the general residues system of modulonand any finite abelian group. Finally, the same formula was established on finite non-abelian group by using Lagrange’s theorem. The fact shows that Fermat’s little theorem is a special case of the most basic Lagrange’s theorem in group theory.

abelian group; non-abelian group; Fermat’s Little Theorem; Euler’s Theorem; Lagrange’s Theorem

2017-03-27

新疆維吾爾自治區(qū)自然科學基金項目(2016D01A014)

楊燕妮(1988-)，女，甘肅靜寧人，助教，碩士，主要從事代數(shù)方面研究。

O156

A

1009-3907(2017)04-0029-04