欧拉函数

字数 2566 2025-12-02 15:18:51

好的，这次我们讲解一个在数论中非常基本且重要的概念。

欧拉函数

第一步：定义与基本含义
欧拉函数，通常记作 φ(n)，是一个定义在正整数集合上的函数。对于任意一个正整数 n，φ(n) 的值等于“小于等于 n 的正整数中，与 n 互质的数的个数”。
- 关键概念解释：
  - 互质：两个正整数 a 和 b 互质，意味着它们的最大公约数 (gcd) 为 1，即 gcd(a, b) = 1。除了 1 以外，它们没有其他的公共质因数。
  - 小于等于 n：这个范围包含了 n 本身。但请注意，gcd(n, n) = n，所以只有当 n=1 时，n 才与自身互质（因为 gcd(1,1)=1）。
第二步：通过具体例子理解计算
让我们计算几个小数值的 φ(n)，来直观感受它。
- 例子 1： n = 6
  小于等于 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, 2, 3, 4, 5, 6 中，与 6 互质的数是 1 和 5。
    因此，φ(6) = 2。
- 例子 2： n = 7 （7是一个素数）
  小于等于 7 的正整数有：1, 2, 3, 4, 5, 6, 7。
  因为 7 是素数，所以所有小于 7 的数（1到6）都与 7 互质。同时，我们需要检查 7 本身：gcd(7, 7) = 7 ≠ 1，所以 7 不与自身互质。
  因此，与 7 互质的数是 1, 2, 3, 4, 5, 6。
  所以，φ(7) = 6。
- 例子 3： n = 1
  小于等于 1 的正整数只有 1 本身。根据定义，gcd(1, 1) = 1，所以 1 与 1 互质。
  因此，φ(1) = 1。（这是一个特例）
第三步：欧拉函数的关键性质
通过观察上面的例子，我们可以发现一些规律，并推导出更一般的性质。
- 性质 1：如果 p 是一个素数，则 φ(p) = p - 1。
  这正是例子 2 (n=7) 的情况。因为素数 p 的定义是只有 1 和它本身两个正因数。所以，所有小于 p 的正整数（从 1 到 p-1）都与 p 互质。总共有 p-1 个这样的数。
- 性质 2：如果 p 是素数，k 是正整数，则 φ(p^k) = p^k - p^(k-1) = p^(k-1) * (p - 1)。
  解释：考虑小于等于 p^k 的数。哪些数与 p^k 不互质呢？如果一个数与 p^k 不互质，那么它必须含有质因数 p。也就是说，这些数是 p 的倍数，即 p, 2p, 3p, ..., p^k (也就是 p^(k-1) * p)。
  总共有 p^(k-1) 个这样的数。
  所以，在 p^k 个数中，去掉这 p^(k-1) 个不与 p^k 互质的数，剩下的就是互质的数。
  因此，φ(p^k) = p^k - p^(k-1) = p^(k-1) * (p - 1)。
  - 例子： n = 8 = 2^3。根据公式，φ(8) = 2^(3-1) * (2-1) = 4 * 1 = 4。我们验证一下：小于等于 8 且与 8 互质的数是 1, 3, 5, 7。确实有 4 个。
- 性质 3（积性）：如果两个正整数 m 和 n 互质（即 gcd(m, n) = 1），那么 φ(m * n) = φ(m) * φ(n)。
  这是一个非常强大且重要的性质。它意味着欧拉函数是一个“积性函数”。
  - 例子： n = 12。12 可以分解为 4 和 3，即 12 = 4 * 3，且 gcd(4, 3) = 1。
    我们知道 φ(4) = 2 (与4互质的数：1, 3)，φ(3) = 2 (与3互质的数：1, 2)。
    根据积性，φ(12) 应该等于 φ(4) * φ(3) = 2 * 2 = 4。
    我们直接计算 φ(12) 来验证：小于等于 12 且与 12 互质的数是 1, 5, 7, 11。确实是 4 个。
第四步：计算任意正整数 n 的欧拉函数的一般公式
利用上面的性质 2 和性质 3，我们可以得到一个通用的计算公式。
任何一个大于 1 的正整数 n 都可以进行质因数分解：n = p1^k1 * p2^k2 * ... * pr^kr。
由于不同的质数幂 p1^k1, p2^k2, ... 之间是两两互质的，我们可以应用积性性质：

φ(n) = φ(p1^k1) * φ(p2^k2) * ... * φ(pr^kr)

再对每一项应用性质 2 的公式 φ(p^k) = p^(k-1) * (p - 1)：

通用公式： φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pr)
- 例子：计算 φ(100)
  首先对 100 进行质因数分解：100 = 2^2 * 5^2。
  应用通用公式：
  φ(100) = 100 * (1 - 1/2) * (1 - 1/5)
  = 100 * (1/2) * (4/5)
  = 100 * (4/10)
  = 100 * (2/5)
  = 40.
  所以，小于等于 100 的正整数中，有 40 个数与 100 互质。
第五步：欧拉函数的一个核心应用——欧拉定理
欧拉函数最著名的应用之一是欧拉定理，它是费马小定理的推广。
欧拉定理：如果正整数 a 与 n 互质（即 gcd(a, n) = 1），那么有 a^φ(n) ≡ 1 (mod n)。
- 与费马小定理的联系：当 n 为素数 p 时，φ(p) = p-1。于是欧拉定理变为：如果 gcd(a, p) = 1，则 a^(p-1) ≡ 1 (mod p)。这正是费马小定理。
- 意义：欧拉定理在密码学（如 RSA 加密算法）、计算模幂等方面有基础性的重要作用。它揭示了在模 n 的世界里，与 n 互质的数构成的集合中，元素的“阶”一定是 φ(n) 的约数。

好的，这次我们讲解一个在数论中非常基本且重要的概念。欧拉函数第一步：定义与基本含义欧拉函数，通常记作 φ(n)，是一个定义在正整数集合上的函数。对于任意一个正整数 n，φ(n) 的值等于“小于等于 n 的正整数中，与 n 互质的数的个数”。关键概念解释：互质：两个正整数 a 和 b 互质，意味着它们的最大公约数 (gcd) 为 1，即 gcd(a, b) = 1。除了 1 以外，它们没有其他的公共质因数。小于等于 n ：这个范围包含了 n 本身。但请注意，gcd(n, n) = n，所以只有当 n=1 时，n 才与自身互质（因为 gcd(1,1)=1）。第二步：通过具体例子理解计算让我们计算几个小数值的 φ(n)，来直观感受它。例子 1： n = 6 小于等于 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, 2, 3, 4, 5, 6 中，与 6 互质的数是 1 和 5。因此， φ(6) = 2 。例子 2： n = 7 （7是一个素数）小于等于 7 的正整数有：1, 2, 3, 4, 5, 6, 7。因为 7 是素数，所以所有小于 7 的数（1到6）都与 7 互质。同时，我们需要检查 7 本身：gcd(7, 7) = 7 ≠ 1，所以 7 不与自身互质。因此，与 7 互质的数是 1, 2, 3, 4, 5, 6。所以， φ(7) = 6 。例子 3： n = 1 小于等于 1 的正整数只有 1 本身。根据定义，gcd(1, 1) = 1，所以 1 与 1 互质。因此， φ(1) = 1 。（这是一个特例）第三步：欧拉函数的关键性质通过观察上面的例子，我们可以发现一些规律，并推导出更一般的性质。性质 1：如果 p 是一个素数，则 φ(p) = p - 1。这正是例子 2 (n=7) 的情况。因为素数 p 的定义是只有 1 和它本身两个正因数。所以，所有小于 p 的正整数（从 1 到 p-1）都与 p 互质。总共有 p-1 个这样的数。性质 2：如果 p 是素数，k 是正整数，则 φ(p^k) = p^k - p^(k-1) = p^(k-1) * (p - 1)。解释：考虑小于等于 p^k 的数。哪些数与 p^k 不互质呢？如果一个数与 p^k 不互质，那么它必须含有质因数 p。也就是说，这些数是 p 的倍数，即 p, 2p, 3p, ..., p^k (也就是 p^(k-1) * p)。总共有 p^(k-1) 个这样的数。所以，在 p^k 个数中，去掉这 p^(k-1) 个不与 p^k 互质的数，剩下的就是互质的数。因此，φ(p^k) = p^k - p^(k-1) = p^(k-1) * (p - 1)。例子： n = 8 = 2^3。根据公式，φ(8) = 2^(3-1) * (2-1) = 4 * 1 = 4。我们验证一下：小于等于 8 且与 8 互质的数是 1, 3, 5, 7。确实有 4 个。性质 3（积性）：如果两个正整数 m 和 n 互质（即 gcd(m, n) = 1），那么 φ(m * n) = φ(m) * φ(n)。这是一个非常强大且重要的性质。它意味着欧拉函数是一个“积性函数”。例子： n = 12。12 可以分解为 4 和 3，即 12 = 4 * 3，且 gcd(4, 3) = 1。我们知道 φ(4) = 2 (与4互质的数：1, 3)，φ(3) = 2 (与3互质的数：1, 2)。根据积性，φ(12) 应该等于 φ(4) * φ(3) = 2 * 2 = 4。我们直接计算 φ(12) 来验证：小于等于 12 且与 12 互质的数是 1, 5, 7, 11。确实是 4 个。第四步：计算任意正整数 n 的欧拉函数的一般公式利用上面的性质 2 和性质 3，我们可以得到一个通用的计算公式。任何一个大于 1 的正整数 n 都可以进行质因数分解：n = p1^k1 * p2^k2 * ... * pr^kr。由于不同的质数幂 p1^k1, p2^k2, ... 之间是两两互质的，我们可以应用积性性质： φ(n) = φ(p1^k1) * φ(p2^k2) * ... * φ(pr^kr) 再对每一项应用性质 2 的公式 φ(p^k) = p^(k-1) * (p - 1)：通用公式： φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pr) 例子：计算 φ(100) 首先对 100 进行质因数分解：100 = 2^2 * 5^2。应用通用公式： φ(100) = 100 * (1 - 1/2) * (1 - 1/5) = 100 * (1/2) * (4/5) = 100 * (4/10) = 100 * (2/5) = 40. 所以，小于等于 100 的正整数中，有 40 个数与 100 互质。第五步：欧拉函数的一个核心应用——欧拉定理欧拉函数最著名的应用之一是欧拉定理，它是费马小定理的推广。欧拉定理：如果正整数 a 与 n 互质（即 gcd(a, n) = 1），那么有 a^φ(n) ≡ 1 (mod n)。与费马小定理的联系：当 n 为素数 p 时，φ(p) = p-1。于是欧拉定理变为：如果 gcd(a, p) = 1，则 a^(p-1) ≡ 1 (mod p)。这正是费马小定理。意义：欧拉定理在密码学（如 RSA 加密算法）、计算模幂等方面有基础性的重要作用。它揭示了在模 n 的世界里，与 n 互质的数构成的集合中，元素的“阶”一定是 φ(n) 的约数。