definition
\(\varphi(n)\) 表示不超过 \(n\) 且与 \(n\) 互质的正整数的个数。
欧拉函数是一个数论函数（定义域为正整数）和积性函数（对于互质的正整数 \(a,b\) 满足 \(f(a,b)=f(a)f(b)\) ）
积性函数的性质：
\(n=\prod p_i^{a_i}(p_i为质数)\)
\(f(n)=\prod f(p_i^{a_i})\) 。
theorem
- \(\varphi(p)=p-1(p为质数)\)
\(\varphi(n)\) 表示不超过 \(n\) 且与 \(n\) 互质的正整数的个数。
欧拉函数是一个数论函数（定义域为正整数）和积性函数（对于互质的正整数 \(a,b\) 满足 \(f(a,b)=f(a)f(b)\) ）
积性函数的性质：
\(n=\prod p_i^{a_i}(p_i为质数)\)
\(f(n)=\prod f(p_i^{a_i})\) 。