下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 欧拉函数公式及其证明

欧拉函数公式及其证明.doc

欧拉函数公式及其证明

AndyPengYu
2017-12-12 0人阅读 举报 0 0 暂无简介

简介:本文档为《欧拉函数公式及其证明doc》,可适用于初中教育领域

欧拉函数:欧拉函数是数论中很重要的一个函数欧拉函数是指:对于一个正整数n小于n且和n互质的正整数(包括)的个数记作phi(n)。完全余数集合:定义小于n且和n互质的数构成的集合为Zn称呼这个集合为n的完全余数集合。显然|Zn|=phi(n)。有关性质:对于素数pphi(p)=p。对于两个不同素数pq它们的乘积n=p*q满足phi(n)=(p)*(q)。这是因为Zn={,,,,n}{p,p,,(q)*p}{q,q,,(p)*q}则phi(n)=(n)(q)(p)=(p)*(q)=phi(p)*phi(q)。欧拉定理:对于互质的正整数a和n有aphi(n)equivmodn。证明:()令Zn={x,x,,xphi(n)}S={a*xmodn,a*xmodn,,a*xphi(n)modn}则Zn=S。①因为a与n互质xi(leilephi(n))与n互质所以a*xi与n互质所以a*ximodnisinZn。②若inej那么xinexj且由a,n互质可得a*ximodnnea*xjmodn(消去律)。()aphi(n)*x*x**xphi(n)modnequiv(a*x)*(a*x)**(a*xphi(n))modnequiv(a*xmodn)*(a*xmodn)**(a*xphi(n)modn)modnequivx*x**xphi(n)modn对比等式的左右两端因为xi(leilephi(n))与n互质所以aphi(n)equivmodn(消去律)。注:消去律:如果gcd(c,p)=则acequivbcmodprArraequivbmodp。费马定理:若正整数a与素数p互质则有apequivmodp。证明这个定理非常简单由于phi(p)=p代入欧拉定理即可证明。*****************************************************************************补充:欧拉函数公式()pk的欧拉函数对于给定的一个素数pphi(p)=p。则对于正整数n=pkphi(n)=pkpk证明:小于pk的正整数个数为pk个其中和pk不互质的正整数有{p*,p*,,p*(pk)}共计pk个所以phi(n)=pk(pk)=pkpk。()p*q的欧拉函数假设p,q是两个互质的正整数则p*q的欧拉函数为phi(p*q)=phi(p)*phi(q)gcd(p,q)=。证明:令n=p*qgcd(p,q)=根据中国余数定理有Zn和ZptimesZq之间存在一一映射(我的想法是:aisinZpbisinZqhArrb*pa*qisinZn。)所以n的完全余数集合的元素个数等于集合ZptimesZq的元素个数。而后者的元素个数为phi(p)*phi(q)所以有phi(p*q)=phi(p)*phi(q)。()任意正整数的欧拉函数任意一个整数n都可以表示为其素因子的乘积为:In=prodpiki(I为n的素因子的个数)i=根据前面两个结论很容易得出它的欧拉函数为:IIPhi(n)=prodpiki(pi)=nprod(pi)i=i=对于任意n|Phi(n),因为必存在pi是偶数。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/3

欧拉函数公式及其证明

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利