关于欧拉定理问题及其应用

1、 学院学 术 论 文关于欧拉定理问题及其应用Euler theorem about application and application姓 名 所在学院 专业班级 学 号 指导教师 日 期 关于欧拉定理问题及其应用摘要：从欧拉定理的证明为切入口，探讨欧拉定理证明所体现数学思想方法，在此基础上探究其应用。关键词：欧 拉 定 理，数 学 思 想 方 法，应 用。Abstract: from the proof of the theorem of related euler, euler theorem proving mathematical way of thinking, which ref

2、lected on the basis of the application.Keywords: Euler Set Daniel, number and fixed thoughts, should use to party.在初等数论中，关于欧拉定理问题的理解、应用以及体现出的数学思想方法是理解数学中其他知识的基础，但目前各种教材对这类问题的提出和总结的不够，尤其对它所体现的数学思想方法。为了加深对欧拉定理的有关理解，本文从欧拉定理的证明为切入口，探讨欧拉定理证明所体现数学思想方法，在此基础上探究其应用。一、 欧拉定理的证明及其体现的数学思想方法（一）定理1(Euler): 设n是大于1的

3、整数，（a,n）=1,则a(n) 1 (mod n)证明1： 首先证明下面这个命题： 对于集合Zn=x1,x2,.,x(n),其中xi(i=1,2,(n)是(n)个n的素数，且两两互素，即n的一个化简剩余系，或称简系，或称缩系)，考虑集合S = a*x1(mod n),a*x2(mod n),.,a*x(n)(mod n) 则S = Zn 1) 由于a,n互质，xi也与n互质，则a*xi也一定于p互质，因此 任意xi，a*xi(mod n) 必然是Zn的一个元素 2) 对于Zn中两个元素xi和xj，如果xi xj 则a*xi(mod n) a*xi(mod n)，这个由a、p互质和消去律可以得

4、出。 所以，很明显，S=Zn 既然这样，那么 （a*x1 × a*x2×.×a*x(n)）(mod n) = （a*x1(mod n) × a*x2(mod n) × . × a*x(n)(mod n)）(mod n) = （x1 × x2 × . × x(n)）(mod n) 考虑上面等式左边和右边 左边等于(a*（x1 × x2 × . × x(n)）) (mod n) 右边等于x1 × x2 × . × x(n)）(mod n) 而x1 &

5、#215; x2 × . × x(n)(mod n)和n互质 根据消去律，可以从等式两边约去，就得到：a(n) 1 (mod n) 证明2.：证明：设集合A1,A2,.,Am为模n的一个缩系（若整数A1,A2,.,Am模n分别对应0,1,2,.,n-1中所有m个与n互素的自然数,则称集合A1,A2,.,Am为模n的一个缩系） 则a A1,a A2,.,a Am也是模n的一个缩系（如果a Ax与a Ay (x不等于y)除以n余数相同，则a(Ax-Ay)是n的倍数，这显然不可能） 即A1*A2*A3*AmaA1*aA2*aAm(mod n) （这里m=(n)） 两边约去A1*A

6、2*A3*Am即得1a(n)（mod n） 评注1：注意到, Euler 定理的证明虽然十分简单, 但它揭示了重要的数学思想方法“整体化思想方法”。整体化思想方法就是把单个对象始终放在整体对象构成的系统中加以考察, 通过系统对象之间的整体联系或整体特征, 寻求原问题的解决途径。从以上的证明过程知道, Euler 定理的证明依赖于模m 的简化剩余系的整体性质: “若r1,r2,r(m)是模m 的简化剩余系, (a,m)=1, 则ar_1,ar_2,ar(m)也是模m 的简化剩余系,且模m的任一简化剩余系中所有数的乘积模m 都同余”。类似地, 设a_1,a_2,am 为模m的完全剩余系, 则a_i

7、与且只与某一个i(1im)同余, 由此可得到完全剩余系的整体性质等。利用模m 的完全剩余系( 或简化剩余系) 的整体性质, 就可以另辟蹊径, 获得巧妙简捷的解(证) 题效果。例题1：设(a, m) = 1, 是使 1（mod m） 成立的最小正整数，则（i） / (ii)对于任意的 I , j , 0 I , j -1 , I j , 有 (mod m) （3） 解：(i) 由Euler 定理， （因满足同于式 ，而是最小的） 因此 ，由带余除法 ，有 = q+r，q, q>0 ,0r< . 因此， 由上式及的定义， 利用定理1， 我们得到 1r(mod m)即整数r满足 (mod

8、 m) , 0 .由的定义可知必是r=0 ,即(ii): 若式（3）不成立 ，则存在I , j, 0, j, 使得 (mod m).因i, 所以不妨设i<j . 由(mod m). m/() m/,因为(a,m)=1, 所以m/( ,即(mod m) , 0<i-j< .这与的定义矛盾，所以式3必成立。（二）欧拉定理的推论的证明及其体现的数学思想方法.推论（Fermat定理） 若p是素数，则 证明：若(a,p)=1 ,由定理1及3定理5即得 因而。若(a,p)1,则p/a,故 评注2： Wilson 定理证明过程蕴涵了数学思想方法“配对思想方法”。配对的思想方法就是将整体对象

9、中的满足某种特性的对象进行组合配对, 再利用配对后的特性解决原问题。初等数论中有许多配对的情形存在。如:若(a,m)=1,则(m- a,m)=1,即a 与m- a 同属于模m 的简化剩余系;若d 是正整数n 的正因数, 则d 与n/d 同为正整数n 的正因数;若p1(mod4), 则r 与p- r 同为模p 的平方剩余或同为平方非剩余。例题2：求a在0到41的值解：因为41是素数 ，所以由费马定理有 ，而1841=46*40+1，所以 ，a=14二、有关于欧拉定理的应有问题（一） 欧拉定理对循环小数的应用定理2：有理数a/b,0<a<b ,(a ,b)=1 ,能表成纯循环小数 的充

10、分必要条件是（b ，10）=1 证明：(i)若a/b能表成纯循环小数，则由0<a/b<1及定义知 a/b=0. . . 因而 a/b=+.+10+0. . .=q+a/b,q>0.故a/b=q/(-1) 即a(-1)=bq .由 (a ,b)=1 即得b/(-1), 因而（b ，10）=1(ii) 若（b ，10）=1，则由定理1知有一正整数 t使得 1(modb), 0<t(b) 成立，因此a=qb+a,且 0<q<a/(1-1/b)<-1 故a/b=q+a/b令 q=10+,=10+,=10+,0,则 q=.由0<q<,即得=0，且 .

11、不全是9，也不全是0。因此 q/=0. ., a/b=0. .+1/*(a/b). 反复应用上式即得 a/b=0. . .=0. 评注3:在定理3的条件下，若 t是使得(modb)能成立的最小正整数，且(b)=gt,则全体以b为分母的即约分数化成小数后，若可以分为g个组，每个组有t个循环小数，每个循环组小数有 t个循环数码，这t个循环数码在这同节的首位数码变为末尾的就行了。（二） 有关欧拉定理在信息安全上的应有 （1）目前主要应用在信息安全上。根据Euler-Fermat定理得到的RSA（公开密匙）体制是较为安全的加密方法。利用它可以实现数据加密、数字签名。RSA原理如下：设N=P1*P2.（

12、P1、P2是两个非常大的素数，通常是一百多位).令e1*e2=1(mod(P1-1)*(P2-2).假设有需要加密的数据C(叫做原文)，作变换令B=Ce1(mod N)，则将数据C加密成为密文B.这里把e1、e2叫做密匙.当接收数据的一方接到密文C后，根据Euler-Fermat定理、及预先知道的e2就可以解出原文C=Be2 (mod N).从上面可以知道，当第三方截获加密规则并到到密文B，也就是知道N、B、e1（这就是公开密匙的内涵），欲解出原文C，还必须知道e2，但要知道e2就必须解出P1-1、P2-1，也就是要知道P1及P2.这就牵涉到大数的分解问题，一般来说，按照现在的数学理论及其先进

13、的计算工具，要分解这样的大数没有十来年是办不到的！这就是该算法的一种相对保密性.当然，不排除数学理论会有突飞猛进的时候，那时，这样的算法是否安全，值得商榷.但是这个理论却给出了一种加密的可行之道，就是加密函数的反函数非常不容易求出，所以现在在此原理上已经有另外的加密算法了.设传送密文的为甲方，接收密文的为乙方，那么甲、乙都有自己的一对密匙，甲传送时，按乙的密匙传送，并把自己的签名用自己的密匙加密，那么，只有拥有乙密匙的人才可以解读密文，并且从签名的加密可以知道，这个密文只有拥有甲的密匙的人才能发送.故对数据起到最大的保密效果. （2）经济学中的“欧拉定理”在西方经济学里，产量和生产要素L、K的

14、关系表述为QQ(L，K)，如果具体的函数形式是一次齐次的，那么就有：QL(&eth;Q/&eth;L)K(&eth;Q/&eth;K)，换句话说，产品分配净尽取决于Q能否表示为一个一次齐次函数形式。 因为&eth;Q/&eth;LMPLw/P被视为劳动对产量的贡献，&eth;Q/&eth;KMPKr/P被视为资本对产量的贡献，因此，此式被解释为“产品分配净尽定理”，也就是所有产品都被所有的要素恰好分配完而没有剩余。因为形式上符合数学欧拉定理，所以称为欧拉定理。 欧拉定理中蕴含了丰富的数学思想方法,其应用于我们生活的各方面，在生活、生产中有着非常重要的作用。 其知识结构和数学思想方法形成一个经纬交织, 融会贯通的知识网络, 需要我们去挖掘、揭示。因此, 在初等数论的学习过程中, 应充分利用教材和习题的功能, 注重展示解决问题的思路、思维过程, 体现解决问题策略与方法的多样性, 引导沟通知识间的内在联