近世代数思想方法在数论中的应用

1、近世代数思想方法在数论中的应用2007年5月第26卷第5期绵阳师范学院journalofmianyangnormaluniversitymay.,2007v01.26no.5近世代数思想方法在数论中的应用张清,唐再良(绵阳师范学院数学与信息科学系,四川绵阳621000)摘要:讨论了近世代数思想方法在证明初等数论定理和素数判断中的应用,介绍了素数判断的多项式时间方法.关键词:群;环;模;数论;素数中图分类号:0156.2文献标识码:a文章编号:1672-612x(2007)05-0012-03l引言数论一度被认为是漂亮的但却没什么大用处的纯数学学科.30多年来,电子计算机的产生与发展,给科学技术

2、带来无比巨大的变革,这使数论有了非常广泛的直接应用途径.例如在近20年来发展起来的高维数值积分的数论网格法的研究中,数论的成果被广泛应用.其中,有关数论算法的广泛使用,部分是因为基于大素数的密码系统的发明.数论更是数学研究的重要内容之一.数论知识在计算机科学,通讯及商业等领域都有着重要的应用.数论的问题以其抽象且难度大而着称,众所周知,抽象也是近世代数的最大特点.近世代数不仅在数学中占有及其重要的地位,而且在其它学科中也有广泛的应用,如理论物理,计算机学科等.其研究的方法和观点,对其他学科产生了越来越大的影响.同时近世代数思想方法多年以来也一直都被用到数论问题的处理中,特别是用到费尔马最后定理

3、的处理.下面我们通过几个初等数论定理的处理来介绍近世代数思想方法在初等数论中的运用.2群论思想在数论定理证明中的应用群论是代数学中最古老最丰富的分支之一,群论思想在近代物理,近代化学,数字通信,系统工程等许多领域都有重要应用,同时群的思想方法也促进了数学科学本身的发展.下面我们通过几个初等数论的定理处理来介绍群论思想方法在数论中的应用.定理1(fermat)设p是一个素数且口是一个不能被p整除的自然数,那么=lmodp.证明:考虑modp的非零剩余类组成的乘法群g=1,2,p一1.对于口是一个不能被p整除的自然数,口=(口)一=1.所以口一e1moap.推论:设p是素数且口是自然数,那么=am

4、odp.证明:如果p整除口,那么;amodp.如果p不整除口,那么由定理1可得;lmodp.以上两种情况都可以得到一amodp.定理2(euler)设n>1是自然数且口是与n互素的整数,那么口;lmodn.证明:考虑modn的剩余类中单位元作成的群g=igcd(x,n)=1.则g的阶为(n).对于任意与n互素的整数口,口=()1.所以)=lmodn.收稿日期:2007-04-27作者简介:张清(1976一),男,硕士,研究方向:代数与符号计算.第5期张清等:近世代数思想方法在数论中的应用?13?定理3(wilson)设p是素数,那么(p一1)!;一1modp.证明考虑too的非零剩余类组

5、成的乘法群g=1,2,p一1.因为s1modp当且仅当(一1)(+1)somodp当且仅当s1modp,所以对于任意的1,.所以(p一1)!=(1xp一1)n()=1p一1=一1.所以(p一1)!;一1modp.eclil3环论思想在数论定理证明中的应用环也是近世代数中一类重要的,基本的代数系统,环论思想与群一样有着广泛的应用.下面我们通过初等数论的定理处理来说明环论思想方法在数论中的应用.定理4(fermat)设是p奇素数.kp;1mod4,那么p是两个平方的和,即存在整数,y使得p=+2y0证明:由于是偶数,那么一1就是一个too平方数.将每个数与它的mo逆元配对,1与p一1;一1modp

6、配对.那么从1到pl的数的乘积mo就等于12_一1一1一_所以()!;一1modp如果一1;2modp,那么p整除+1.现在我们在高斯整数环zi中分解+1为(一i)(+i).既然p不能整除任一个因子,那么p在zi中不是素数.因为高斯整数环是唯一分解环,p是可约的.所以我们就写p=,其中和卢都不是单位.定义y=a+bi的范数为n(7)=a+6.那么n(7)=1当且仅当y是1,一1,或一i当且仅当y是单位.所以p=n(p)=n(ot)n(f1),其中n(ot)>1且n(f1)>1,所以n(ot)=n(f1)=p.女口果ot=+iy,男么p=+.反之,如果p是奇素数且p=+y,那么p同余

7、于1mod4.如果是偶数,那么=omod4,且如果是奇数,那么;1mod4.由于p是奇数,和y不能同时为偶数或奇数.定理5(wolstenh.lme)如果是p一个大于3素数,那么1+1+了1+的分子能被p2整除.证明:设)=(一1)(一2)(一(p一1).将)展开成的幂级数形式)=_.一s1一+s2一+一sp-2+sp一1其中的一些系数能很简单的写出.比如,s=1+2+(p一1)=;sp一=(p一1)!;s一=(1+)(p一1)!.这样我们就建立了与原问题的联系.而其他的系数我们就把他们看成的p函数.现在在系数mo映射下,根据费尔马小定理,)在(z/pz)中的像就是(一1)(一2)(一(p一1

8、)=一1.所以对任意的i<p一1,s是p的倍数.p)=(p一1)!=0).所以0:pppp一.pp一.+sl,-3p一$p-2这是p一1个数的和,前p一2个数都是p的倍数.所以一是p的倍数.由于(p一1)!;lm.如,(p一1)!与p互素.所以1+丢+就是p.的倍数.?14?绵阳师范学院(自然科学版)第26卷问题:口,b,c在什么情况下,口+clz含有无限多个素数.4模方法在素数判断中的应用素数的定义其实就给出了判断素数的方法:尝试每个m,如果有一个m整除/,则/,是合数,否则凡是素数.筛法生成所有小于n的素数.但这些算法的效率不高.需要()步才能决定.3用近世代数的模方法给出了多项式时

9、间算法.引理13】:设口是整数,凡是大于2的自然数且(口,n)=1.那么凡是素数当且仅当(戈+口)=戈+口(modn)利用这个引理判断素数的时候,最多需要计算等式左边n个系数.于是我们可以模一1(其中r比较小)来减少需要计算的系数的个数.凡是素数当且仅当(+口);+口(modx一1,n)对所有的口和r.而当凡是合数时,只对少数的口和r满足上述等式.定义1:设口是整数,r是自然数且(口,r)=1.定义口模r的阶为最小的正整数使得口;1(modr).记为0,(口).算法】:(aks)输人整数n>11.如果(n=口,其中口是自然数,b>1),输出合数.2.找到最小的r使得0,(n)>

10、;log2(n).3.如果存在口r使得1<(口,n)<n,输出合数.4.如果nr,输出素数.5.从口=1到iog(n)l做:如果(+口)+口(modx一1,n),输出合数.6.输出素数.定理131:aks算法返回素数当且仅当凡是素数.定理23】:aks算法的极限时间复杂度为0(1ogn)=o(1og7n?poly(1og(1ogn)hendriklenstra和carlpomerance改进了算法,其时间复杂度为o(1og.n).如果下面的猜想成立,aks时间复杂度可以进一步改进为0(1ogn).e4已经验证了当r100且n10m时,猜想正确.猜想:设r是素数且不能整除n.如果(一

11、1)一一1(modx一1,n),那么凡是素数或n;1(modr).参考文献:1robertb.ash,aeouibeinalgebraicnumbertheory.onlinepreprintbook.2005.2daverusin,wolstenholmecongruence.onlinelecturenotes.2006.3agrawal,kayalandsaxena(aks),primesisinp.annualofmathematics,2004(160):781-7934kayalandsaxena(aks),towardsapolynomialtimetest.2002.5r.bhattaeharjeeandp.pandey,primalitytesting.2001.theapplicationofmodernalgebrawayofthinkinginnumbertheoryzhangqing,tangzailiang(departmentofmathematicsandinformationscience,mianyangnormaluniversity,mianyang,sichuan621000)abstract:inthispaper,wefirsthaveadiscuss