# 定义

定义
nn 为正整数,定义函数 φ(n)\varphi(n) 为小于等于 nn 且与 nn 互素的正整数的个数
φ\varphiEuler 函数 (Euler's Totient Function)「オイラーのトーシェント関数」

命题
nn 的素因子分解为 n=p1k1p2k2pmkmn = p_1^{k_1} p_2^{k_2} \cdots p_m^{k_m},则

φ(n)=n(11p1)(11p2)(11pm)\varphi(n) = n \left(1 - \frac{1}{p_1}\right)\left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_m}\right)

# 性质

命题
m,nm,n 为正整数,且 gcd(m,n)=1\gcd(m,n) = 1,则

φ(mn)=φ(m)φ(n)\varphi(mn) = \varphi(m) \varphi(n)

命题
pp 为素数,kk 为正整数,则

φ(pk)=pkpk1=pk(11p)\varphi(p^k) = p^k - p^{k-1} = p^k \left(1 - \frac{1}{p}\right)

命题
n3n \geq 3,则

dnφ(d)=n\sum_{d \mid n} \varphi(d) = n

其中求和是对 nn 的所有正因子 dd 进行的
特别地,当 nn 为素数 pp 时,有

φ(1)+φ(p)=1+(p1)=p\varphi(1) + \varphi(p) = 1 + (p - 1) = p