欧拉函数简要推导

    欧拉函数简要推导

    命题

    定义欧拉函数 φ(n)\varphi(n) 为 “ 在 1∼n1 \sim n 中与 nn 互质的数的个数 “。

    设 nn 有 mm 个质因子,从小到大为 p1,p2,...,pmp_1, p_2, ...,p_m,则:

    φ(n)=n∏i=1m(1−1pi)\varphi(n) = n \prod\limits_{i = 1}^m \left(1 - \frac{1}{p_i}\right)

    证明

    考虑构造 mm 个集合 A1,...,AmA_1,...,A_m,其中 Ai={x∈[1,n]⋂Z∣ x mod pi=0}A_i = \{x \in [1, n] \bigcap \mathbb{Z} \mid \, x \bmod p_i = 0 \}。

    显然,在 1∼n1 \sim n 与 nn 不互质的数的集合为:

    ⋃i=1mAi\bigcup\limits_{i=1}^m A_i

    故 φ(n)\varphi(n) 为:

    n−∣⋃i=1mAi∣n - \left| \bigcup\limits_{i=1}^m A_i \right|

    由容斥原理,得:

    n−(np1+⋯+npm)+(np1p2+np1p3+⋯ )−⋯+(−1)mnp1p2...pmn - \left( \frac{n}{p_1} + \cdots + \frac{n}{p_m} \right) + \left(\frac{n}{p_1p_2} + \frac{n}{p_1p_3} + \cdots\right) - \cdots + (-1)^{m}\frac{n}{p_1p_2 ... p_m}

    将公因式 nn 提取,通分得:

    n⋅(−1)m+(−1)m−1(p1+p2+⋯ )+⋯+p1p2...pmp1p2...pmn \cdot \frac{(-1)^{m} + (-1)^{m - 1} \left( p_1 + p_2 + \cdots \right) + \cdots + p_1p_2 ... p_m }{p_1p_2 ... p_m}

    考虑构造 mm 个二元组,第 ii 个二元组为 (pi,−1)(p_i, -1)。则上式分子中的每一项,都可以通过在这 mm 个二元组中,依次选择其中的一个数乘起来而得到。故可以化简得:

    n⋅(p1−1)(p2−1)⋯(pm−1)p1p2⋯pmn \cdot \frac{(p_1 - 1)(p_2 - 1) \cdots (p_m - 1)}{p_1p_2 \cdots p_m}
    n∏i=1m(1−1pi)n \prod\limits_{i=1}^m \left(1-\frac{1}{p_i}\right)

    Q.E.D