数论论文-关于欧拉定理问题及其应用

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

摘要：从欧拉定理的证明为切入口，探讨欧拉定理证明所体现数学思想方法，在此基础上

探究其应用。

关键词：欧拉定理，数学思想方法，应用。

在初等数论中，关于欧拉定理问题的理解、应用以及体现出的数学思想方法是理解数学中其他知识的基础，但目前各种教材对这类问题的提出和总结的不够，尤其对它所体现的数学思想方法。为了加深对欧拉定理的有关理解，本文从欧拉定理的证明为切入口，探讨欧拉定理证明所体现数学思想方法，在此基础上探究其应用。

一、欧拉定理和其推论的证明

（一）欧拉定理的证明及其体现的数学思想方法

1.定理(Euler):设n是大于1的整数，（a,n）=1,则a^φ(n) ≡ 1 (mod n) 证明： 首先证明下面这个命题：

对于集合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互质和消去律可以得出。 所以，很明显，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)

word文档 可自由复制编辑

而x1 × x2 × ... × xφ(n)(mod n)和n互质

根据消去律，可以从等式两边约去，就得到：a^φ(n) ≡ 1 (mod n)

证明：设集合{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*„„Am≡aA1*aA2*„„aAm(mod n) （这里m=φ(n)） 两边约去A1*A2*A3*„„Am 即得1≡a^φ(n)（mod n）

2.（例题）设(a, m) = 1, d是（d，a）1（mod m）成立的最小正整数，则 （i）d/ m

(ii)对于任意的 I , j , 0  I , j ，d-1 , I  j , 有j i aa (mod m) 解：(i) 由Euler 定理， 0d)(m（因)(m满足同于式，而0d是最小的） 因此，由带余除法，有)=(m= qd+r，qZ, q>0 ,0r<0d

. 因此，由上式及 0d的定义， 利用定理1，我们得到 1r(mod m) 即整数r满足 1ra(mod m) , 0 0dr由 0d的定义可知必是r=0 ,即)(/0md

(ii): 若式（3）不成立，则存在I , j, 0i, j 10d, 使得jiaa(mod m). 因ij, 所以不妨设 i因为(a,m)=1, 所以m/( )1j ia ,即 1jia(mod m) , 0（二）欧拉定理的推论的证明及其体现的数学思想方法 1.推论（Fermat定理） 若p是素数，则(a ，p ) .(modpa) 证明：若(a,p)=1 ,由定理1及￡3定理5即得 (a ，p ) .(modpa)

若(a,p)1,则p/a,故a p ).(modpa

2.（例题 ）1841 1777(mod41),a求a在0到41的值

解：因为41是素数，所以由费马定理有40 17771(mod41)，而1841=46*40+1，所以 1841，1777177714(mod41)，a=14 二、有关于欧拉定理的应用问题

word文档 可自由复制编辑

（一） 欧拉定理对循环小数的应用定理

1.有理数a/b,0„..=q+a/b,q>0. 故a/b=q/(t 10-1) 即a(t 10-1)=bq .由 (a ,b)=1 即得b/(t 10-1), 因而（b ，10）=1 (ii) 若（b ，10）=1，则由定理1知有一正整数 t使得 t 101(modb), 0反复应用上式即得 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(mod N)，则将数据C加密成为密文B.这里把e1、e2叫做密匙. 当接收数据的一方接到密文C后，根据Euler-Fermat定理、及预先知道的e2就可以解出原文C=B^e2 (mod N).

从上面可以知道，当第三方截获加密规则并到到密文B，也就是知道N、B、e1

（这就是公开密匙的内涵），欲解出原文C，还必须知道e2，但要知道e2就必须解出-1、P2-1也就是要知道P1及P2.这就牵涉到大数的分解问题，一般来说，按照现在的数学理论及其先进的计算工具，要分解这样的大数没有十来年是办不到的！这就是该算法的一种相对保密性.当然，不排除数学理论会有突飞猛进的时候，那时，这样的算法是否安全，值得商榷. 但是这个理论却给出了一种加密的可行之道，就是加密函数的反函数非常不容易求出，所以 现在在此原理上已经有另外的加密算法了.

word文档 可自由复制编辑

设传送密文的为甲方，接收密文的为乙方，那么甲、乙都有自己的一对密匙，甲传送时，按 乙的密匙传送，并把自己的签名用自己的密匙加密，那么，只有拥有乙密匙的人才可以解读 密文，并且从签名的加密可以知道，这个密文只有拥有甲的密匙的人才能发送.故对数据起到最大的保密效果. （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.

word文档 可自由复制编辑