欧拉函数证明欧拉函数的证明不要用“易证”、“由某某原理易得”、“Mod”敝人才疏很难领悟谢我知道啊大哥你搞什么 我要证明！
来源：学生作业帮助网 编辑：六六作业网 时间：2024/12/27 17:21:42
欧拉函数证明欧拉函数的证明不要用“易证”、“由某某原理易得”、“Mod”敝人才疏很难领悟谢我知道啊大哥你搞什么 我要证明！
欧拉函数证明
欧拉函数的证明
不要用“易证”、“由某某原理易得”、“Mod”
敝人才疏
很难领悟
谢
我知道啊
大哥你搞什么 我要证明！
欧拉函数证明欧拉函数的证明不要用“易证”、“由某某原理易得”、“Mod”敝人才疏很难领悟谢我知道啊大哥你搞什么 我要证明！
E(x)表示比x小的且与x互质的正整数的个数.
*若p是素数,E(p)=p-1.
*E(p^k)=p^k-p^(k-1)=(p-1)*P^(k-1)
证：令n=p^k,小于n的正整数数共有n-1即(p^k-1)个,其中与p不质的数共[p^(k-1)-1]个(分别为1*p,2*p,3*p...p(p^(k-1)-1)).
所以E(p^k)=(p^k-1)-(p^(k-1)-1)=p^k-p^(k-1).得证.
*若ab互质,则E(a*b)=E(a)*E(b),欧拉函数是积性函数.
*对任意数n都可以唯一分解成n=p1^a1*p2^a2*p3^a3*...*pn^an(pi为素数).
则E(n)=E(p1^a1)*E(p2^a2)*E(p3^a3)*...*E(pn^an)
=(p1-1)*p1^(a1-1)*(p2-1)*p2^(a2-1)*...*(pn-1)*pn^(an-1)
=(p1^a1*p2^a2*p3^a3*...*pn^an)*[(p1-1)*(p2-1)*(p3-1)*...*(pn-1)]/(p1*p2*p3*...*pn)
=n*(1-1/p1)*(1-1/p2)*...*(1-1/pn)
* E(p^k) =(p-1)*p^(k-1)=(p-1)*p^(k-2)*p
E(p^(k-1))=(p-1)*p^(k-2)
->当k>1时,E(p^k)=E(p*p^(k-1))=E(p^(k-1))*p.
(当k=1时,E(p)=p-1.)
由上式: 设P是素数,
若p是x的约数,则E(x*p)=E(x)*p.
若p不是x的约数,则E(x*p)=E(x)*E(p)=E(x)*(p-1).
*快速求欧拉函数方法：
首先来回顾一下线性筛选素数方法：
自己好好看看资料，什么是欧拉函数！
这是地址：http://baike.baidu.com/view/107769.htm