# 定义
定义
设 n 为正整数,定义函数 φ(n) 为小于等于 n 且与 n 互素的正整数的个数
称 φ 为 Euler 函数 (Euler's Totient Function)「オイラーのトーシェント関数」
命题
设 n 的素因子分解为 n=p1k1p2k2⋯pmkm,则
φ(n)=n(1−p11)(1−p21)⋯(1−pm1)
# 性质
命题
设 m,n 为正整数,且 gcd(m,n)=1,则
φ(mn)=φ(m)φ(n)
命题
设 p 为素数,k 为正整数,则
φ(pk)=pk−pk−1=pk(1−p1)
命题
设 n≥3,则
d∣n∑φ(d)=n
其中求和是对 n 的所有正因子 d 进行的
特别地,当 n 为素数 p 时,有
φ(1)+φ(p)=1+(p−1)=p