欧拉函数 $φ(n)$ 是如何定义的？

适用条件

• $n$ 是正整数。
• 计数范围是从 1 到 $n$（包含两端）。
• 互质性由最大公约数为 1 来决定。

理解与推导

1. 确定需要检查的整数范围：从 1 到 $n$。
2. 对于该范围内的每个整数 $a$，计算 $a$ 和 $n$ 的最大公约数，记为 $\gcd(a, n)$。
3. 检查是否 $\gcd(a, n) = 1$。如果是，则 $a$ 与 $n$ 互质。
4. 统计满足此条件的整数 $a$ 的总数。
5. 得到的计数即为 $\varphi(n)$ 的值。

例子

对于 $n=6$，从 1 到 6 的整数是 1, 2, 3, 4, 5, 6。它们与 6 的最大公约数分别是：$\gcd(1,6)=1$，$\gcd(2,6)=2$，$\gcd(3,6)=3$，$\gcd(4,6)=2$，$\gcd(5,6)=1$，$\gcd(6,6)=6$。只有 1 和 5 与 6 的最大公约数为 1。因此，$\varphi(6) = 2$。

容易误解的地方

• 认为 $\varphi(n)$ 计算的是 $n$ 的质因数个数。
• 认为 $\varphi(n)$ 的计数范围包含 0（范围严格是从 1 到 $n$）。
• 混淆互质与质数；一个数可以与 $n$ 互质但本身不是质数（例如，1 与 6 互质，但它不是质数）。

观看对应讲解

继续追问

• 如何使用最大公约数来确定两个数是否互质？
• 为什么质数 p 满足 $φ(p) = p - 1$？
• 欧拉函数的一般公式是什么？