最后更新于3年前
设 mmm 是一个正整数，则 mmm 个整数1,⋯ ,m1, \cdots,m1,⋯,m 中与 mmm 互素的整数的个数，记作φ(m)\varphi(m)φ(m)
对于素数幂m=pαm=p^\alpham=pα，有φ(m)=pα−pα−1\varphi(m)=p^\alpha-p^{\alpha-1}φ(m)=pα−pα−1
∣(Z/mZ)∗∣=φ(m)\left|{\left(Z/mZ\right)}^{*}\right|=\varphi(m)(Z/mZ)∗=φ(m)
若(m,n)=1(m,n)=1(m,n)=1，则φ(m⋅n)=φ(m)⋅φ(n)\varphi(m\cdot n)=\varphi(m)\cdot \varphi(n)φ(m⋅n)=φ(m)⋅φ(n)
若m=p1α1p2α2⋯psαsm=p_{1}^{\alpha_1}p_{2}^{\alpha_2}\cdots p_{s}^{\alpha_s}m=p1α1p2α2⋯psαs，则φ(m)=m(1−1p1)(1−1p2)⋯(1−1ps)\varphi(m)=m\left(1-\frac{1}{p_1}\right)\left(1-\frac{1}{p_2}\right)\cdots\left(1-\frac{1}{p_s}\right)φ(m)=m(1−p11)(1−p21)⋯(1−ps1)
若p,qp,qp,q为两个素数，则φ(p⋅q)=p⋅q−p−q+1\varphi(p\cdot q)=p\cdot q-p-q+1φ(p⋅q)=p⋅q−p−q+1
∑d∣mφ(d)=m\sum_{d\mid m}{\varphi(d)}=m∑d∣mφ(d)=m