1.11

Euler 函数 φ:N→N\varphi : \mathbb{N} \rightarrow \mathbb{N} 定义为 φ(n)=∣{ x:0<x≤n∧gcd(x,n)=1 }∣, \varphi(n) = |\{\ x: 0<x\leq n \wedge \gcd(x,n) = 1\ \}|, 即 φ(n)\varphi(n) 表示小于等于 nn 且与 nn 互素的正整数个数，例如 φ(1)=1\varphi(1)=1，因为 1 与其本身互素；φ(9)=6\varphi(9) = 6，因为 9 与 1, 2, 4, 5, 7, 8 互素。证明：φ∈EF\varphi \in \mathcal{EF}.

证明

我们有 φ(n)=n∏p∣n(1−1p)\varphi(n) = n \prod\limits_{p|n}(1- \frac{1}{p})

∵∏p∣np=∏i=0n  IF  Pi∣n  THEN  Pi  ELSE  1\because \prod\limits_{p|n} p = \prod\limits_{i=0}^n\ \text{ IF } \ P_i|n \ \text{ THEN }\ P_i \ \text{ ELSE }\ 1

=∏i=0n  IF  epi≥1  THEN  Pi  ELSE  1=\prod\limits_{i=0}^n\ \text{ IF } \ \text{ep}_i \geq 1 \ \text{ THEN }\ P_i \ \text{ ELSE }\ 1

=∏i=0n(PiN(1−˙epi(n))+N2(1−˙epi(n)))∈EF=\prod\limits_{i=0}^n(P_iN(1\dot{-} \text{ep}_i(n))+N^2(1\dot{-}\text{ep}_i(n))) \in \mathcal{EF}

同理，∏p∣n(p−1)=∏i=0n((Pi−1)N(1−˙epi(n))+N2(1−˙epi(n)))∈EF\prod\limits_{p|n} (p-1) =\prod\limits_{i=0}^n((P_i-1)N(1\dot{-} \text{ep}_i(n))+N^2(1\dot{-}\text{ep}_i(n))) \in \mathcal{EF}

∴φ(n)=N(n−˙1)+N2(n−˙1)[∏p∣n(p−1)∏p∣np]∈EF\therefore \varphi(n) = N(n\dot{-}1)+N^2(n \dot{-}1)\left[\dfrac{\prod\limits_{p|n} (p-1)}{\prod\limits_{p|n} p}\right] \in \mathcal{EF}.