为什么质数 p 满足 $φ(p) = p - 1$？

适用条件

• $p$ 是质数。
• $\varphi(p)$ 定义为从 1 到 $p$ 中与 $p$ 互质的整数个数。

理解与推导

1. 设 $p$ 为质数。
2. 考虑从 1 到 $p$ 的整数。
3. 注意到从 1 到 $p-1$ 的所有整数都不包含 $p$ 作为因数。
4. 因为 $p$ 是质数，它的因数只有 1 和 $p$。因此，任何小于 $p$ 的整数与 $p$ 除了 1 以外没有公因数。
5. 这意味着对于所有 $a \in \{1, 2, \ldots, p-1\}$，都有 $\gcd(a, p) = 1$。
6. 统计这些整数的数量，即 $p - 1$。
7. 得出结论 $\varphi(p) = p - 1$。

例子

设 $p=5$。从 1 到 5 的整数是 1, 2, 3, 4, 5。它们与 5 的最大公约数分别是：$\gcd(1,5)=1$，$\gcd(2,5)=1$，$\gcd(3,5)=1$，$\gcd(4,5)=1$，$\gcd(5,5)=5$。与 5 互质的整数是 1, 2, 3 和 4。共有 $5-1=4$ 个这样的整数。因此，$\varphi(5) = 4$。

容易误解的地方

• 认为 1 不与 $p$ 互质（1 与每个正整数都互质）。
• 认为 $\varphi(p)$ 计算的是小于 $p$ 的质数个数（它计算的是所有与 $p$ 互质的整数，而不仅仅是质数）。

观看对应讲解

继续追问

• 如何推导 $φ(p^k) = p^k - p^{k-1}$？
• 欧拉函数的一般公式是什么？
• 如何计算从 2 到 3 的 sqrt(x) 定积分？