初等数论入门 Lesson 5 欧拉函数

欧拉函数乘积公式

由第三课我们已知

$$\boxed{\varphi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)}$$

欧拉函数的积性我们也证明过：

1. 构造剩余性

   • $A = \{a \mid 1 \le a \le m,\ \gcd(a,m) = 1\}$，共 $\varphi(m)$ 个；
   • $B = \{b \mid 1 \le b \le n,\ \gcd(b,n) = 1\}$，共 $\varphi(n)$ 个；
   • $C = \{c \mid 1 \le c \le mn,\ \gcd(c,mn) = 1\}$，共 $\varphi(mn)$ 个。

2. 用中国剩余定理建立映射

   考虑：

   $$\begin{cases} x \equiv a \pmod{m} \\ x \equiv b \pmod{n} \end{cases} \quad (\gcd(m,n)=1)$$

   • 该方程组在模 $mn$ 下有唯一解 x，且 $1\le x\le mn$

   • 对于不同的 $(a,b)$ 给出了不同的解 $x$

   由此我们建立了一个映射：

   $$f: (a,b) \mapsto x \pmod{mn}$$

   因为 $\gcd(a,m)=1,\;\gcd(b,n)=1,\;\gcd(m,n)=1$ ，故 $\gcd(x,mn)=1$，因此 $x\in C$

3. 证明是双射

   取 $c\in C$，令 $a\equiv c\pmod m,\;b\equiv c\pmod n$，则 $\gcd(a,m)=1,\;\gcd(b,n)=1$，故 $(a,b)\in A\times B$

综上：

$$\boxed{\varphi(mn) = \varphi(m)\varphi(n) \quad (\gcd(m,n) = 1)}$$

除数求和等式

我们要证明：

$$\sum_{d\mid n}\varphi(d)=n$$

等价类证明

考虑分数 $\dfrac 1 n,\dfrac 2 n,\dots,\dfrac n n$

我们把这些分数约分成最简形式 $\dfrac a d$，则：

• $d$ 必然是 $n$ 的因子
• 对于每个 $d$，相应 $a$ 的个数总共有 $\varphi(d)$ 个

因此把这些最简分数合起来，正好是原先 $n$ 个分数。

阶/生成元角度证明

考虑群 $\mathbb Z_n$（模 $n$ 的加法群），对于任意 $k\in\{1,2,\dots,n\}$

• 元素 $k$ 在 $\mathbb Z_n$ 中的阶 是 $\dfrac n {\gcd(k,n)}$
• 反过来，对于每个 $d$，阶恰好等于 $d$ 的元素个数为 $\varphi(d)$

把这些元素的阶分类统计，总元素个数为 $n$。

可以这么理解 ：$\mathbb Z_n$ 中的 $n$ 个元素的阶必然为 $n$ 的因数 $d$，因此把每个 $d$ 对应元素（$\varphi(d)$）相加就是 $n$.

互素数和公式

求 1 到 $n$ 中与 $n$ 互素的数的和，记作：

$$S(n)=\sum_{\substack{1 \le k \le n \\ \gcd(k,n)=1}} k$$

关键在于对称性观察

若 $\gcd(n,k)=1$，则 $\gcd(n-k,n)=1$

因此与 $n$ 互素的数总是成对出现的

且在 $n>2$ 时，$k\ne n - k$

同时有 $k+(n-k)=n$

所以在 $n>2$ 时，答案为：

$$S(n)=\dfrac{n\varphi(n)}2$$

其中：

$$S(1)=\dfrac 1 2 \\ S(2)=1$$