4d-读书笔记 欧拉函数
来源-算法爱好者（2017-12-1）
#啊，12月了，还有30天，2017！
欧拉函数的定义:E(k)=([1,n-1]中与n互质的整数个数).
小于或等于N的正整数中与N互质的数的个数。
例如，φ(8)=4， 因为2,3,5,7均和8互质。
φ(n) 的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。
phi(1)=1
phi(N)=N (打不出来）
phi(p^k)=p^k-p^(k-1)=(p-1)p^(k-1)
phi(mn)=phi(m)phi(n), gcd(m,n)=1
phi(kp)=phi(kp)(p-1)/p
第一种情况
如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。
第二种情况
如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
第三种情况
如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则
φ（p^k）=p^k-p^(k-1)
比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
φ（p^k）=p^k-p^(k-1)=p^k(1-1/p)
第四种情况
如果n可以分解成两个互质的整数之积，
n=p1xp2
则
φ(n)=φ(p1p2)=φ(p1)φ(p2)
!欧拉函数是 积性函数
第五种情况
因为任意一个大于1的正整数，都可以写成一系列质数的积。
φ(n)=φ(p1p2)=φ(p1)φ(p2)...φ(pr)
φ(n)=(p1^k1)(p2^k2)...φ(pr^kr)
φ(n)=(p1^k1)(1-1/p1) (p2^k2)(1-1/p2)...(pr^kr)(1-1/pr)
φ(n)=(pz^k1) (p2^k2)...(pr^kr)(1-1/p1)(1-1/p2)...(1/1/pr)
φ(n)=φ(kp)=φ(kp) (p-1)/p
φ(n)=(p1^k1)(p2^k2)...(pr^k^)(1-1/p1)(1-1/p2)...(1-1/pr)
#进一步，代码和应用
#啊，12月了，还有30天，2017！
欧拉函数的定义:E(k)=([1,n-1]中与n互质的整数个数).
小于或等于N的正整数中与N互质的数的个数。
例如，φ(8)=4， 因为2,3,5,7均和8互质。
φ(n) 的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。
phi(1)=1
phi(N)=N (打不出来）
phi(p^k)=p^k-p^(k-1)=(p-1)p^(k-1)
phi(mn)=phi(m)phi(n), gcd(m,n)=1
phi(kp)=phi(kp)(p-1)/p
第一种情况
如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。
第二种情况
如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
第三种情况
如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则
φ（p^k）=p^k-p^(k-1)
比如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。
这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、...、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。
φ（p^k）=p^k-p^(k-1)=p^k(1-1/p)
第四种情况
如果n可以分解成两个互质的整数之积，
n=p1xp2
则
φ(n)=φ(p1p2)=φ(p1)φ(p2)
!欧拉函数是 积性函数
第五种情况
因为任意一个大于1的正整数，都可以写成一系列质数的积。
φ(n)=φ(p1p2)=φ(p1)φ(p2)...φ(pr)
φ(n)=(p1^k1)(p2^k2)...φ(pr^kr)
φ(n)=(p1^k1)(1-1/p1) (p2^k2)(1-1/p2)...(pr^kr)(1-1/pr)
φ(n)=(pz^k1) (p2^k2)...(pr^kr)(1-1/p1)(1-1/p2)...(1/1/pr)
φ(n)=φ(kp)=φ(kp) (p-1)/p
φ(n)=(p1^k1)(p2^k2)...(pr^k^)(1-1/p1)(1-1/p2)...(1-1/pr)
#进一步，代码和应用
