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

上传资料

关闭

关闭

关闭

封号提示

内容

首页 [资料]欧拉函数公式及其证实

[资料]欧拉函数公式及其证实.doc

[资料]欧拉函数公式及其证实

有绝交才有至交吖
2017-09-21 0人阅读 举报 0 0 暂无简介

简介:本文档为《[资料]欧拉函数公式及其证实doc》,可适用于职业岗位领域

资料欧拉函数公式及其证实欧拉函数:欧拉函数是数论中很重要的一个函数欧拉函数是指:对于一个正整数n小于n且和n互质的正整数(包括)的个数记作φ(n)。完全余数集合:定义小于n且和n互质的数构成的集合为Zn称呼这个集合为n的完全余数集合。显然|Zn|,φ(n)。有关性质:对于素数pφ(p)=p。对于两个不同素数pq它们的乘积n=p*q满足φ(n)=(p)*(q)。这是因为Zn={,,,,n}{p,p,,(q)*p}{q,q,,(p)*q}则φ(n)=(n)(q)(p)=(p)*(q),φ(p)*φ(q)。欧拉定理:φ(n)对于互质的正整数a和n有amodn。证明:()令Zn={x,x,,x}S={a*xmodn,a*xmodn,,a*φ(n)xmodn}φ(n)则Zn=S。因为a与n互质x(iφ(n))与n互质所以a*x与n互质所以a*xiiimodnZn。若ij那么xx且由a,n互质可得a*xmodna*xmodn(消去ijij律)。φ(n)()a*x*x**xmodnφ(n)(a*x)*(a*x)**(a*x)modnφ(n)(a*xmodn)*(a*xmodn)**(a*xmodn)modnφ(n)x*x**xmodnφ(n)φ(n)对比等式的左右两端因为x(iφ(n))与n互质所以aimodn(消去律)。注:消去律:如果gcd(c,p)=则acbcmodpabmodp。费马定理:p若正整数a与素数p互质则有amodp。证明这个定理非常简单由于φ(p)=p代入欧拉定理即可证明。*****************************************************************************补充:欧拉函数公式k()p的欧拉函数k对于给定的一个素数pφ(p)=p。则对于正整数n=pkkφ(n)=pp证明:kk小于p的正整数个数为p个其中kkk和p不互质的正整数有{p*,p*,,p*(p)}共计p个kkkk所以φ(n)=p(p)=pp。()p*q的欧拉函数假设p,q是两个互质的正整数则p*q的欧拉函数为φ(p*q)=φ(p)*φ(q)gcd(p,q)=。证明:令n=p*qgcd(p,q)=根据中国余数定理有Zn和Zp×Zq之间存在一一映射(我的想法是:aZpbZqb*pa*qZn。)所以n的完全余数集合的元素个数等于集合Zp×Zq的元素个数。而后者的元素个数为φ(p)*φ(q)所以有φ(p*q)=φ(p)*φ(q)。()任意正整数的欧拉函数任意一个整数n都可以表示为其素因子的乘积为:Ikn=p(I为n的素因子的个数)iii=根据前面两个结论很容易得出它的欧拉函数为:IIkΦ(n)=p(p)=n(pi)iiii=i=对于任意n>|Φ(n),因为必存在p是偶数。i

用户评价(0)

关闭

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

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

提示

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

文档小程序码

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

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/3

[资料]欧拉函数公式及其证实

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利