任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）计算这个值的方法就叫做欧拉函数，以φ(n)表示。

• 计算8的欧拉函数，和8互质的 1、2、3、4、5、6、7、8
  φ(8) = 4
  如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则φ(n) = φ(p^k) = p^k - p^(k-1)。也就是φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4
• 计算7的欧拉函数，和7互质的 1、2、3、4、5、6、7
  φ(7) = 6
  如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。
• 计算56的欧拉函数
  φ(56) = φ(8) * φ(7) = 4 * 6 = 24
  如果n可以分解成两个互质的整数之积，即 n = p * k ，则φ(n) = φ(p * k) = φ(p1)*φ(p2)

image.png
image.png