数论论文

关于欧拉定理问题及其应用摘要：从欧拉定理的证明为切入口，探讨欧拉定理证明所体现数学思想方法，在此基础上探究其应用。关键词：欧拉定理，数学思想方法，应用。在初等数论中，关于欧拉定理问题的理解、应用以及体现出的数学思想方法是理解数学中其他知识的基础，但目前各种教材对这类问题的提出和总结的不够，尤其对它所体现的数学思想方法。为了加深对欧拉定理的有关理解，本文从欧拉定理的证明为切入口，探讨欧拉定理证明所体现数学思想方法，在此基础上探究其应用。一、欧拉定理和其推论的证明（一）欧拉定理的证明及其体现的数学思想方法1.定理(Euler):设n是大于1的整数，（a,n）=1,则a^φ(n)≡1(modn)证明：首先证明下面这个命题：对于集合Zn={x1,x2,...,xφ(n)},其中xi(i=1,2,„φ(n))是φ(n)个n的素数，且两两互素，即n的一个化简剩余系，（或称简系，或称缩系)，考虑集合S={a*x1(modn),a*x2(modn),...,a*xφ(n)(modn)}则S=Zn1)由于a,n互质，xi也与n互质，则a*xi也一定于p互质，因此任意xi，a*xi(modn)必然是Zn的一个元素2)对于Zn中两个元素xi和xj，如果xi≠xj则a*xi(modn)≠a*xi(modn)，这个由a、p互质和消去律可以得出。所以，很明显，S=Zn既然这样，（a*x1×a*x2×...×a*xφ(n)）(modn)=（a*x1(modn)×a*x2(modn)×...×a*xφ(n)(modn)）(modn)=（x1×x2×...×xφ(n)）(modn)考虑上面等式左边和右边左边等于(a*（x1×x2×...×xφ(n)）)(modn)右边等于x1×x2×...×xφ(n)）(modn)而x1×x2×...×xφ(n)(modn)和n互质根据消去律，可以从等式两边约去，就得到：a^φ(n)≡1(modn)证明：设集合{A1,A2,...,Am}为模n的一个缩系（若整数A1,A2,...,Am模n分别对应0,1,2,...,n-1中所有m个与n互素的自然数,则称集合{A1,A2,...,Am}为模n的一个缩系）则{aA1,aA2,...,aAm}也是模n的一个缩系（如果aAx与aAy(x不等于y)除以n余数相同，则a(Ax-Ay)是n的倍数，这显然不可能）即A1*A2*A3*„„Am≡aA1*aA2*„„aAm(modn)（这里m=φ(n)）两边约去A1*A2*A3*„„Am即得1≡a^φ(n)（modn）2.（例题）设(a,m)=1,d是（d，a）1（modm）成立的最小正整数，则（i）d/m(ii)对于任意的I,j,0I,j，d-1,Ij,有jiaa(modm)解：(i)由Euler定理，0d)(m（因)(m满足同于式，而0d是最小的）因此，由带余除法，有)=(m=qd+r，qZ,q0,0r0d.因此，由上式及0d的定义，利用定理1，我们得到1r(modm)即整数r满足1ra(modm),00dr由0d的定义可知必是r=0,即)(/0md(ii):若式（3）不成立，则存在I,j,0i,j10d,使得jiaa(modm).因ij,所以不妨设ij.由jiaa(modm).m/(jiaa)m/1jijaa,因为(a,m)=1,所以m/()1jia,即1jia(modm),0i-j0d.这与0d的定义矛盾，所以式（二）欧拉定理的推论的证明及其体现的数学思想方法1.推论（Fermat定理）若p是素数，则(a，p).(modpa)证明：若(a,p)=1,由定理1及￡3定理5即得(a，p).(modpa)若(a,p)1,则p/a,故ap).(modpa2.（例题）18411777(mod41),a求a在0到41的值解：因为41是素数，所以由费马定理有4017771(mod41)，而1841=46*40+1，所以1841，1777177714(mod41)，a=14二、有关于欧拉定理的应用问题（一）欧拉定理对循环小数的应用定理1.有理数a/b,0ab,(a,b)=1,能表成纯循环小数的充分必要条件是（b，10）=1证明：(i)若a/b能表成纯循环小数，则由0a/b1及定义知a/b=0.1a2a„„.ta1a2ata„..因而t10a/b=110t1a+210t2a+„„..+101ta+ta+0.1a2a„„.ta1a2a„.ta„..=q+a/b,q0.故a/b=q/(t10-1)即a(t10-1)=bq.由(a,b)=1即得b/(t10-1),因而（b，10）=1(ii)若（b，10）=1，则由定理1知有一正整数t使得t101(modb),0t(b)成立，因此t10a=qb+a,且0qt10a/t10(1-1/b)t10-1故t10a/b=q+a/b令q=10q+ta,q=102q+1ta,„„„„,1tq=10tq+1a,09ia,则q=tttttaaaq11110.......1010.由0q1101t,即得tq=0，且1a2a„„.ta不全是9，也不全是0。因此q/t10=0.1a2a„„.ta,a/b=0.1a2a„„.ta+1/t10*(a/b).反复应用上式即得a/b=0.1a2a„„.ta1a2a„.ta„..=0.taa.1..........评注：在定理3的条件下，若t是使得110t(modb)能成立的最小正整数，且φ(b)=gt,则全体以b为分母的即约分数化成小数后，若可以分为g个组，每个组有t个循环小数，每个循环组小数有t个循环数码，这t个循环数码在这同节的首位数码变为末尾的就行了。（二）有关欧拉定理在信息安全上的应用（1）目前主要应用在信息安全上。根据Euler-Fermat定理得到的RSA（公开密匙）体制是较为安全的加密方法。利用它可以实现数据加密、数字签名。RSA原理如下：设N=P1*P2.（P1、P2是两个非常大的素数，通常是一百多位).令e1*e2=1(mod(P1-1)*(P2-2)).假设有需要加密的数据C(叫做原文)，作变换令B=C^e1(modN)，则将数据C加密成为密文B.这里把e1、e2叫做密匙.当接收数据的一方接到密文C后，根据Euler-Fermat定理、及预先知道的e2就可以解出原文C=B^e2(modN).从上面可以知道，当第三方截获加密规则并到到密文B，也就是知道N、B、e1（这就是公开密匙的内涵），欲解出原文C，还必须知道e2，但要知道e2就必须解出-1、P2-1也就是要知道P1及P2.这就牵涉到大数的分解问题，一般来说，按照现在的数学理论及其先进的计算工具，要分解这样的大数没有十来年是办不到的！这就是该算法的一种相对保密性.当然，不排除数学理论会有突飞猛进的时候，那时，这样的算法是否安全，值得商榷.但是这个理论却给出了一种加密的可行之道，就是加密函数的反函数非常不容易求出，所以现在在此原理上已经有另外的加密算法了.设传送密文的为甲方，接收密文的为乙方，那么甲、乙都有自己的一对密匙，甲传送时，按乙的密匙传送，并把自己的签名用自己的密匙加密，那么，只有拥有乙密匙的人才可以解读密文，并且从签名的加密可以知道，这个密文只有拥有甲的密匙的人才能发送.故对数据起到最大的保密效果.（2）经济学中的“欧拉定理”在西方经济学里，产量和生产要素L、K的关系表述为Q＝Q(L，K)，如果具体的函数式是一次齐次的，那么就有：Q＝L(ðQ/ðL)＋K(ðQ/ðK)，换句话说，产品分配净尽取决于Q能否表示为一个一次齐次函数形式。因为ðQ/ðL＝MPL＝w/P被视为劳动对产量的贡献，ðQ/ðK＝MPK＝r/P视为资本对产量的贡献，因此，此式被解释为“产品分配净尽定理”，也就是所有产品都被所有的要素恰好分配完而没有剩余。因为形式上符合数学欧拉定理，所以称为欧拉定理。欧拉定理中蕴含了丰富的数学思想方法,其应用于我们生活的各方面，在生活、生产中有着非常重要的作用。其知识结构和数学思想方法形成一个经纬交织,融会贯通的知识网络,需要我们去挖掘、揭示。因此,在初等数论的学习过程中,应充分利用教材和习题的功能,注重展示解决问题的思路、思维过程,体现解决问题策略与方法的多样性,引导沟通知识间的内在联系,突出问题的背景和思想方法的阐述,注重数学思想方法的总结、提炼,数学知识和相关数学思想方法有机联系起来,使我们从整体上把握初等数论的理论体系,理解数学思想方法的内涵,开阔思维视野,健全认知结构。参考文献：[1]闵嗣鹤,严士健.初等数论[M].北京:高等教育出版社,2003.91-95.[2]于秀源,瞿维建.初等数论[M].济南:山东教育出版社,2001.66-68.[3]潘承洞,潘承彪.数学思想方法[M].北京:北京大学出版社,1999.144-145.