欧拉定理的证明

欧拉定理的证明欧拉定理的证明一、引言在数学及许多分支中都可以见到很多以欧拉命名的常数、公式和定理。在数论中，欧拉定理（EulerTheorem，也称费马-欧拉定理或欧拉函数定理）是一个关于同余的性质。欧拉定理得名于瑞士数学家莱昂哈德·欧拉，该定理被认为是数学世界中最美妙的定理之一，欧拉定理实际上是费马小定理的推广.二、内容在数论中，欧拉定理,（也称费马--欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互质，则：.1.知识准备：（1）欧拉函数：欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数...

欧拉定理的证明一、引言在数学及许多分支中都可以见到很多以欧拉命名的常数、公式和定理。在数论中，欧拉定理（EulerTheorem，也称费马-欧拉定理或欧拉函数定理）是一个关于同余的性质。欧拉定理得名于瑞士数学家莱昂哈德·欧拉，该定理被认为是数学世界中最美妙的定理之一，欧拉定理实际上是费马小定理的推广.二、内容在数论中，欧拉定理,（也称费马--欧拉定理）是一个关于同余的性质。欧拉定理表明，若n,a为正整数，且n,a互质，则：.1.知识准备：（1）欧拉函数：欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n).（2）完全余数集合：定义小于n且和n互质的数构成的集合为Zn，称呼这个集合为n的完全余数集合。显然|Zn|＝φ(n)。其中，“|A|”表示这个集合中元素的个数，比如A=｛a,b}则|A|=2.（3）有关性质：对于素数p，φ(p)=p-1。对于两个不同素数p，q，它们的乘积n=p*q满足φ(n)=(p-1)*(q-1).因为Zn={1,2,3, ...,n-1}-{p,2p,...,(q-1)*p}-{q,2q,...,(p-1)*q}，则φ(n)=(n-1)-(q-1)-(p-1)=(p-1)*(q-1) ＝φ(p)*φ(q).2.证明方法：证明：(1)首先证明下面这个命题：对于集合Zn={x1,x2,...,xφ(n)}，S = {a*x1(mod n),a*x2(mod n),...,a*xφ(n)(mod n)} ，其中xi(i=1,2,„φ(n))是不大于n且与n互素的数，即n的一个化简剩余系，或称简系，或称缩系)，则Zn=S.1) 由于a,n互质，xi也与n互质，则a*xi也一定于n互质，因此任意xi，a*xi(mod n) 必然是Zn的一个元素2) 对于Zn中两个元素xi和xj，如果xi ≠ xj 则a*xi(mod n) ≠ a*xj(mod n)，这个由a、n互质和消去律可以得出。所以，很明显，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)和n互质根据消去律，可以从等式两边约去，就得到： a^φ(n) ≡ 1 (mod n) 推论：对于互质的数a、n，满足a^(φ(n)1) ≡ a (mod n) 费马定理: a是不能被质数p整除的正整数，则有a^(p-1) ≡ 1 (mod p)证明这个定理非常简单，由于φ(p)=p-1，代入欧拉定理即可证明。同样有推论：对于不能被质数p整除的正整数a,①因为a与n互质，xi(1≤i≤φ(n))与n互质，所以a*xi 与n互质，所以a*xi modn∈Zn。②若i≠j，那么xi≠xj，且由a,n互质可得a*ximodn≠a*xjmodn（消去律）。(2) aφ(n)*x1*x2*...*xφ(n)modn≡(a*x1)*(a*x2)*...*(a*xφ(n))modn≡(a*x1modn)*(a*x2modn)*...*(a*xφ(n)modn)modn≡ x1*x2*...*xφ(n)modn对比等式的左右两端，因为xi (1≤i≤φ(n))与n互质，所以（消去律）。注：消去律：如果gcd(c,p)=1，则ac≡bcmodp⇒a≡bmodp。费马定理：若正整数a与素数p互质，则有ap-1≡1modp。证明这个定理非常简单，由于φ(p)=p-1，代入欧拉定理即可证明。费马小定理:a是不能被质数p整除的正整数，则有a^(p-1)≡1(modp)证明这个定理非常简单，由于p是质数，所以有φ(p)=p-1，代入欧拉定理即可证明。推论：对于任意正整数a，有a^p≡a(modp)，因为a能被p整除时结论显然成立。应用首先看一个基本的例子。令a=3，n=5，这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4，所以φ(5)=4（详情见[欧拉函数]）。计算:a^{φ(n)}=3^4=81，而81=801Ξ1（mod5）。与定理结果相符。这个定理可以用来简化幂的模运算。比如计算7^{222}的个位数，实际是求7^{222}被10除的余数。7和10[[互素]]，且φ(10)=4。由欧拉定理知7^4Ξ1(mod10)。所以7^{222}=(7^4)^55*(7^2)Ξ1^{55}*7^2Ξ49Ξ9(mod10)。

                    本文档为【欧拉定理的证明】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

欧拉定理的证明

你可能还喜欢