有关费尔马小定理的推广
2017-06-01杨燕妮
杨燕妮
(喀什大学 数学与统计学院,新疆 喀什 844006)
有关费尔马小定理的推广
杨燕妮
(喀什大学 数学与统计学院,新疆 喀什 844006)
首先用数学归纳法证明了费尔马小定理，然后通过模p数系乘法的代数结构,不仅导出了公式,同时也证明了费尔马小定理。进一步将此方法推广到了一般模n和任何有限交换群上。最后,借助拉格朗日定理建立了有限非交换群上同样的公式。可见,费尔马小定理是群论最基本的拉格朗日定理之特例。
交换群；非交换群；费尔马小定理；欧拉定理；拉格朗日定理
费尔马小定理[1]是近代密码学瑞沙叶算法[2-3]的理论基础。本文从费尔马小定理的证明出发,分析与p互素的整数在乘法运算下的代数结构,并将其推广到非素数n对应的欧拉定理[4]和一般抽象群的元素上。最终发现费尔马小定理竟然是群论中拉格朗日定理[5]的简单推论。
1 费尔马小定理的归纳法证明
费尔马小定理 设p为一正素数，若a∈且p|a,则：ap-1≡1(modp),∀a∈,p|a。
(1)
众所周知,数学归纳法仅适用于正整数。因此,需先对a作归纳,然后再推广到任意整数。此外,数学归纳法的关键是由a的p-1次方推出a+1的p-1次方。但在模p下,要将(a+1)p-1展开化简并不易。若将a+1取p次方,然后再模p则简单的多。事实上,由二项式定理可知,(a+1)p的展开式中,除头尾两项的系数是1外,其余都是p的倍数,即：
上式分母中的所有整数因子均小于p,因此分子中的p不会被约掉。从而：(a+1)p≡ap+1(modp)。
显然,这里的项数2可被任何正整数取代。换句话说,“和的p次方等于p次方的和”。可见：在模p的环境下,只需将结论中的次方转化成p次方即可。为此,将等式两边同乘以a,有ap≡a(modp)。当p|a时,此同余式与原同余式等价。
数学归纳法必须针对所有正整数,不能排除p的倍数。然而,条件却限制了p|a,怎么办？注意到,修改版ap≡a(modp)对p的倍数显然成立。因此,只需用数学归纳法证明：
ap≡a(modp),∀a∈即可。
(2)
证明:(1)当a=1时,因1p≡1(modp),故同余式(2)成立;
(2)假设当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)显然成立。对负整数a=-k,k∈和正素数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 完全剩余系与费尔马小定理
众所周知,虽然整数有无穷多,但是其模p后只剩p个余数0,1,2,…,p-1。通常用p表示在模p的加法和乘法下形成的代数结构(p,+,·)。费尔马小定理就是在此有限体的乘法结构中产生的,其中且是一个交换群[4]。下面,在这个有限交换群上来构建费尔马小定理。
设a∈，且p|a,即(p,a)=1。群包含p-1个元素,它恰是定理中a的次幂。显然,用a乘以群中的每个数,可得包含p-1个a的倍数的集合：
(1a)(2a)…(p-1)a≡1·2…(p-1)(modp)或(p-1)!ap-1≡(p-1)!(modp)。
由消去律即得费尔马小定理ap-1≡1(modp)。
3 费尔马小定理与欧拉定理
其元素个数等于欧拉函数φ(n),即小于n且与n互素的正整数个数。它同样具有交换群的代数结构[5]。现用与上节同样的方法来构建将费尔马小定理推广到一般模n的公式。
设a∈，且(a,n)=1。令考虑用a乘以群中每个数所得的集合
由消去律可知,其中的元素两两互异。于是
再由交换律可得：
(a1a2…aφ(n))aφ(n)≡a1a2…aφ(n)(modn)。
两边消去a1a2…aφ(n)后,就得到了费尔马小定理的推广——欧拉定理。
欧拉定理若a∈且(a,n)=1,则aφ(n)≡1(modn)。
4 有限交换群上的费尔马小定理
总结前两节的论证过程,一般可归纳为三个步骤:首先,在模环境下,利用消去律把看似不同的两个集合Ga与G同归于一;其次,将集合Ga中所有元素相乘,并利用交换律把a表成方幂形式;最后,再利用消去律即得所求公式。可见,论证的本质在于G是有限交换群。为此,可将公式(1)推广到一般有限交换群上。
定理 设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生成的循环子群={an|n∈} 反过来,T(a)|m是否也是am=e的充分条件呢?为此,令A=且k=T(a)。若A=G,则m=T(a),结论成立;若A≠G,则∃b∈G但b∉A。现将已有的元素列表如下: a,a2,a3,…,ak-1,e ab,a2b,a3b,…,ak-1b,b. 由消去律不难看出,第二行的所有元素不仅两两相异,而且也不同于第一行的所有元素(若aib=aj,则b=aj-i∈A,与假设b∉A矛盾)。上表中共有2·T(a)个元素。若它们就是G的所有元素,则结论已成立。否则,再选取不在这两行的元素c,并考虑下面新的列表: a,a2,a3,…,ak-1,e ab,a2b,a3b,…,ak-1b,b ac,a2c,a3c,…,ak-1c,c. 由消去律同样可知,第三行的所有元素两两相异且不同于前两行的所有元素。上表中共有3·T(a)个元素。如此继续下去,每次构造出的新元素均为T(a)个。因G是有限群,故在有限步后,不妨设为s,就会遍历G中的所有元素。因此,可得m=s·T(a),即T(a)|m。 设H 拉格朗日定理 设G是有限群。若H 证明:仿上节的论证,只需将方幂移至下标H={a1,…,ak-1,ak=e}即可(略)。 推论1 设G是有限群且T(G)=p。若p为素数,则G是循环群。 证明:取非单位元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)。设T(G)=r·T(a),r∈.于是,aT(G)=ar·T(a)=(aT(a))r=er=e。 推论4 设n∈,a∈。若(a,n)=1,则aφ(n)≡1(modn)。 推论5 设p是正素数,a∈。若p|a,则ap-1≡1mod(p)。 事实表明,费尔马小定理的确是拉格朗日定理的特例。 [1] 邓勇.费尔马小定理的一种奇特证明[J].首都师范大学学报(自然科学版),2015,36(2):8-9. [2] 陈少真.密码学基础[M].北京:科学出版社,2008. [3] 肖攸安,李腊元.数字签名技术的研究[J].武汉理工大学学报(交通科学与工程版),2002,26(6):737-740. [4] 张文鹏,李海龙.初等数论[M].西安:陕西师范大学出版社,2013. [5] 张禾瑞.近世代数基础(修订本)[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 新疆维吾尔自治区自然科学基金项目(2016D01A014) 杨燕妮(1988-)，女，甘肃静宁人，助教，硕士，主要从事代数方面研究。 O156 A 1009-3907(2017)04-0029-046 拉格朗日定理
