arongnet 阅读(1098) 评论(23)

pk的欧拉函数

对于给定的一个素数p,我们知道Φ(p) = p-1。假设一个整数n是p的k次幂,也就是

                n = pk            k∈N+

容易证明


  Φ(n) = pk - pk-1
  
证明:
 已知少于小于pk的正整数个数为pk-1个,其中
 和pk不互质的正整数有{p×1,p×p2,...,p×(pk-1-1)}共计pk-1-1个
 所以Φ(n) = pk -1 - (pk-1-1) = pk - pk-1

pq的欧拉函数

假设p,q是两个互质的正整数,则pq的欧拉函数为

                Φ(pq) = Φ(p)Φ(q)           gcd(p,q)=1
证明:
 ∵M= pq,gcd(p,q) =1
 ∴根据中国余数定理,有
 ZM和Zp×Zq之间存在一一映射
 所以M的完全余数集中元素的个数等于集合Zp×Zq元素的个数
 而后者的元素个数为Φ(p)Φ(q),所以有
 Φ(pq) = Φ(p)Φ(q)

任意正整数的欧拉函数

任意一个整数n都可以表示为其素因子的乘积为:

            I
 n = ∏  piki
    i=1

根据前面两个结论,很容易得出它的欧拉函数为:


               I
 Φ(n) = ∏  piki-1(pi-1)
       i=1

对于任意n>2,很显然,2 | Φ(n)


评论列表
三番马尧
re: 欧拉函数公式
看不懂啊!
三番马尧
re: 欧拉函数公式
看不懂啊
alan
re: 欧拉函数公式
何谓互质
ALAN
re: 欧拉函数公式
新证法!
用归纳法证:
1.当n=1时 等式成立
2.假设当n=k时 等式成立 即Φ(n) = pk - pk-1
那么n=k+1时
pk+1 - pk=pk*p-(pk-1)*p=Φ(n)*p
即Φ(n)=pk+1 - p(k+1)-1
由1,2可得 Φ(n)=pk+1 - p(k+1)-1
结论成立
QZ
re: 函数产生的背景是什么????
谁可以帮我啊
hujk2008
re: 欧拉函数公式
还不是很明白
cx0998
re: 欧拉函数公式
∵M= pq,gcd(p,q) =1
∴根据中国余数定理,有
ZM和Zp×Zq之间存在一一映射
这个因果关系不是很明白,请指点一下!
haha
re: 欧拉函数公式
我靠,这不就是大学高等数学的基础知识嘛~,我还以为是什么呢,还有那个alan你的证明错了,下面的朋友说的对from the identical equation ,you cannot get the next conclusion ,大学书上有证明,很简单的,你一看就知道了
wasley
re: 欧拉函数公式
太简单了,有深一点的吗?
风卷残楼
re: 欧拉函数公式
谁可以帮我一下啊
用c语言编程写出欧拉公式解微分方程的程序来
1.构造一个微分方程
2编程
3输出
风卷残楼
re: 欧拉函数公式
谁可以帮我一下啊 
用c语言编程写出欧拉公式解微分方程的程序来 
1.构造一个微分方程 
2编程 
3输出 
Fancy Mouse
re: 欧拉函数公式
其实还有更简单的欧拉函数计算方法。假设n的质因子是p1~pn
fai(n) = n*(1-1/p1)*(1-1/p2)*...*(1-1/pn)
cici
re: 欧拉函数公式
还有没有其他关于欧拉函数计算证明的方法啊?
kef
re: 欧拉函数公式
不错!
tony
re: 欧拉函数公式
你很厉害啊;谢谢你的文章

发表评论
切换编辑模式