楊燕妮

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

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

楊燕妮

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

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

交換群；非交換群；費(fèi)爾馬小定理；歐拉定理；拉格朗日定理

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

1 費(fèi)爾馬小定理的歸納法證明

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

(1)

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

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

顯然,這里的項(xiàng)數(shù)2可被任何正整數(shù)取代。換句話說(shuō),“和的p次方等于p次方的和”。可見(jiàn)：在模p的環(huán)境下,只需將結(jié)論中的次方轉(zhuǎn)化成p次方即可。為此,將等式兩邊同乘以a,有ap≡a(modp)。當(dāng)p|a時(shí),此同余式與原同余式等價(jià)。

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

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

(2)

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

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

進(jìn)一步,當(dāng)a=0時(shí),同余式(2)顯然成立。對(duì)負(fù)整數(shù)a=-k,k∈和正素?cái)?shù)p≠2,由于：

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

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

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

2 完全剩余系與費(fèi)爾馬小定理

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

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

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

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

3 費(fèi)爾馬小定理與歐拉定理

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

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

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

再由交換律可得：

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

兩邊消去a1a2…aφ(n)后,就得到了費(fèi)爾馬小定理的推廣——?dú)W拉定理。

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

4 有限交換群上的費(fèi)爾馬小定理

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

定理 設(shè)G是含有m個(gè)元素的交換群。若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 有限非交換群上的費(fèi)爾馬小定理

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

反過(guò)來(lái),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è)元素。若它們就是G的所有元素,則結(jié)論已成立。否則,再選取不在這兩行的元素c,并考慮下面新的列表:

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

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

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

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

6 拉格朗日定理

設(shè)H

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

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

推論1 設(shè)G是有限群且T(G)=p。若p為素?cái)?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是正素?cái)?shù),a∈。若p|a,則ap-1≡1mod(p)。

事實(shí)表明,費(fèi)爾馬小定理的確是拉格朗日定理的特例。

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

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

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

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

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

責(zé)任編輯：程艷艷

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ū)自然科學(xué)基金項(xiàng)目(2016D01A014)

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

O156

A

1009-3907(2017)04-0029-04