如何推导 $φ(p^k) = p^k - p^{k-1}$ ？

Q: 如何推导 φ(p^k) = p^k − p^{k−1}？

为了推导 $\varphi(p^k)$，我们需要计算从 1 到 $p^k$ 中与 $p^k$ 互质的整数个数。一个整数与 $p^k$ 不互质，当且仅当它与 $p^k$ 有共同的质因数。因为 $p$ 是 $p^k$ 唯一的质因数，所以不互质的整数恰好是 $p$ 的倍数。在 $[1, p^k]$ 范围内，$p$ 的倍数有 $p^{k-1}$ 个。从总数 $p^k$ 中减去这些数，就得到了互质整数的个数：$\varphi(p^k) = p^k - p^{k-1}$。

为了推导

\varphi(p^k)

，我们需要计算从 1 到

p^k

中与

p^k

互质的整数个数。一个整数与

p^k

不互质，当且仅当它与

p^k

有共同的质因数。因为

p

是

p^k

唯一的质因数，所以不互质的整数恰好是

p

的倍数。在

[1, p^k]

范围内，

p

的倍数有

p^{k-1}

个。从总数

p^k

中减去这些数，就得到了互质整数的个数：

\varphi(p^k) = p^k - p^{k-1}

。

适用条件

$p$ 是质数。
$k$ 是正整数（由上下文暗示）。
计数范围是从 1 到 $p^k$ （包含两端）。

理解与推导

考虑从 1 到 $p^k$ 的整数。
确定整数 $a$ 与 $p^k$ 不互质的条件： $\gcd(a, p^k) > 1$ 。
因为 $p$ 是 $p^k$ 唯一的质因数， $\gcd(a, p^k) > 1$ 当且仅当 $p$ 整除 $a$ 。
计算 $[1, p^k]$ 范围内 $p$ 的倍数的数量。它们是 $p, 2p, 3p, \ldots, p^{k-1} \cdot p$ 。
这样的倍数有 $p^{k-1}$ 个。
从整数总数中减去不互质整数的数量： $p^k - p^{k-1}$ 。
得出结论 $\varphi(p^k) = p^k - p^{k-1}$ 。

例子

设 $p=2$ 且 $k=3$ ，所以 $p^k = 8$ 。从 1 到 8 的整数是 1, 2, 3, 4, 5, 6, 7, 8。2 的倍数是 2, 4, 6, 8（共有 $2^{3-1} = 4$ 个）。与 8 互质的整数是 1, 3, 5, 7。数量为 $8 - 4 = 4$ 。使用公式： $\varphi(8) = 2^3 - 2^2 = 8 - 4 = 4$ 。

容易误解的地方

认为所有偶数都不与 $p^k$ 互质，而不管 $p$ 是什么（只有特定质数 $p$ 的倍数才被排除）。
忘记范围包含 $p^k$ 本身，它是 $p$ 的倍数，因此不互质。

观看对应讲解

哔哩哔哩【数论特别篇】初中生都能听懂的欧拉函数！！！

1:12 – 1:35原站看这一段 ↗

继续追问

答案依据视频资料生成并经过独立核验。若有疑问，请核对原视频或联系原作者。

如何推导 φ(pk)=pk−pk−1φ(p^k) = p^k - p^{k-1}φ(pk)=pk−pk−1？