欧拉函数 )
表示小于等于x的素数有多少个 如%3D4)
几个性质：
1、euler(1)=1（唯一和1互质的数就是1本身）。
2、若n是质数p的k次幂，φ(n) = p^k - p^(k-1) = (p - 1)*p^(k - 1)，
因为p为质数，所以与n不互质的数只有p的倍数，一共有p^(k-1)个。
3、若m, n互质，φ(m*n) = φ(m) * φ(n)
4、一个数与其互质的数(<n)的总和是euler(n)*n/2
5、欧拉定理：如果n为正整数且a是一个与n互质的数，那么：a ^ φ(n) ≡ 1 (mod n)
2、若n是质数p的k次幂，φ(n) = p^k - p^(k-1) = (p - 1)*p^(k - 1)，
因为p为质数，所以与n不互质的数只有p的倍数，一共有p^(k-1)个。
3、若m, n互质，φ(m*n) = φ(m) * φ(n)
4、一个数与其互质的数(<n)的总和是euler(n)*n/2
5、欧拉定理：如果n为正整数且a是一个与n互质的数，那么：a ^ φ(n) ≡ 1 (mod n)
京公网安备 11010502036488号