欧拉函数简要推导
命题
定义欧拉函数 \varphi(n) 为 “ 在 1 \sim n 中与 n 互质的数的个数 “。
设 n 有 m 个质因子,从小到大为 p_1, p_2, ...,p_m,则:
证明
考虑构造 m 个集合 A_1,...,A_m,其中 A_i = \{x \in [1, n] \bigcap \mathbb{Z} \mid \, x \bmod p_i = 0 \}。
显然,在 1 \sim n 与 n 不互质的数的集合为:
故 \varphi(n) 为:
由容斥原理,得:
将公因式 n 提取,通分得:
考虑构造 m 个二元组,第 i 个二元组为 (p_i, -1)。则上式分子中的每一项,都可以通过在这 m 个二元组中,依次选择其中的一个数乘起来而得到。故可以化简得:
Q.E.D