欧拉定理
字数 2081 2025-11-23 07:53:45

欧拉定理

欧拉定理是数论中关于模运算的一个基本定理，它描述了在模正整数 \(m\) 下，与 \(m\) 互质的整数的一个幂等性质。具体来说，若整数 \(a\) 与正整数 \(m\) 互质（即 \(\gcd(a, m) = 1\)），则：

\[a^{\phi(m)} \equiv 1 \pmod{m} \]

其中 \(\phi(m)\) 是欧拉函数，表示不超过 \(m\) 且与 \(m\) 互质的正整数的个数。

1. 欧拉函数的定义与计算
欧拉函数 \(\phi(m)\) 是数论中的一个重要算术函数。对于任意正整数 \(m\)，\(\phi(m)\) 等于集合 \(\{1, 2, \dots, m\}\) 中与 \(m\) 互质的元素个数。例如：

  • \(\phi(1) = 1\)，因为 1 与自身互质。
  • \(\phi(9) = 6\)，因为与 9 互质的数有 1, 2, 4, 5, 7, 8。
    若 \(m\) 有标准素数分解 \(m = p_1^{k_1} p_2^{k_2} \cdots p_r^{k_r}\)，则：

\[\phi(m) = m \left(1 - \frac{1}{p_1}\right) \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_r}\right) \]

例如，\(m = 12 = 2^2 \cdot 3\)，则：

\[\phi(12) = 12 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4 \]

实际验证：与 12 互质的数有 1, 5, 7, 11，共 4 个。

2. 简化剩余系与乘法群
模 \(m\) 的简化剩余系是指模 \(m\) 的一个完全剩余系中所有与 \(m\) 互质的数构成的集合。例如，模 9 的简化剩余系为 \(\{1, 2, 4, 5, 7, 8\}\)，其元素个数正好是 \(\phi(9) = 6\)。这些数在模 \(m\) 乘法下构成一个群，称为模 \(m\) 的乘法群，记作 \((\mathbb{Z}/m\mathbb{Z})^\times\)。该群的阶即为 \(\phi(m)\)。

3. 欧拉定理的证明思路
欧拉定理的证明基于群论中的拉格朗日定理：有限群的阶必是其子群阶的倍数。具体步骤为：

  • 考虑模 \(m\) 的乘法群 \((\mathbb{Z}/m\mathbb{Z})^\times\)，其阶为 \(\phi(m)\)。
  • 对任意 \(a\) 满足 \(\gcd(a, m) = 1\)，\(a\) 在群中对应的元素生成一个循环子群。
  • 由拉格朗日定理，子群的阶（即 \(a\) 的阶）必整除群的阶 \(\phi(m)\)，故 \(a^{\phi(m)} \equiv 1 \pmod{m}\)。

4. 欧拉定理与费马小定理的关系
费马小定理是欧拉定理在 \(m\) 为素数时的特例。若 \(m = p\) 为素数，则 \(\phi(p) = p - 1\)，欧拉定理变为：

\[a^{p-1} \equiv 1 \pmod{p} \]

这正是费马小定理的表述。因此，欧拉定理可视为费马小定理在模数为合数时的推广。

5. 欧拉定理的应用实例
欧拉定理在计算大数幂的模运算中非常有用。例如，计算 \(7^{100} \bmod 9\)：

  • 由于 \(\gcd(7, 9) = 1\) 且 \(\phi(9) = 6\)，由欧拉定理：

\[ 7^6 \equiv 1 \pmod{9} \]

  • 将 \(100\) 除以 \(6\) 得余数 \(4\)，因为 \(100 = 6 \cdot 16 + 4\)，故：

\[ 7^{100} = (7^6)^{16} \cdot 7^4 \equiv 1^{16} \cdot 7^4 \pmod{9} \]

  • 计算 \(7^4 = 2401\)，且 \(2401 \div 9 = 266 \cdot 9 + 7\)，所以：

\[ 7^{100} \equiv 7 \pmod{9} \]

因此，\(7^{100} \bmod 9 = 7\)。

6. 欧拉定理的推广与限制
欧拉定理要求 \(a\) 与 \(m\) 互质。若不互质，结论不一定成立。例如，取 \(a = 2, m = 4\)，则 \(\phi(4) = 2\)，但 \(2^2 = 4 \equiv 0 \not\equiv 1 \pmod{4}\)。此外，欧拉定理可推广到卡迈克尔函数的情形，用于处理更一般的模数。

最终，欧拉定理的结果可总结为：

\[\boxed{a^{\phi(m)} \equiv 1 \pmod{m} \quad \text{当} \quad \gcd(a, m) = 1} \]

欧拉定理 欧拉定理是数论中关于模运算的一个基本定理，它描述了在模正整数 \(m\) 下，与 \(m\) 互质的整数的一个幂等性质。具体来说，若整数 \(a\) 与正整数 \(m\) 互质（即 \(\gcd(a, m) = 1\)），则： \[ a^{\phi(m)} \equiv 1 \pmod{m} \] 其中 \(\phi(m)\) 是欧拉函数，表示不超过 \(m\) 且与 \(m\) 互质的正整数的个数。 1. 欧拉函数的定义与计算 欧拉函数 \(\phi(m)\) 是数论中的一个重要算术函数。对于任意正整数 \(m\)，\(\phi(m)\) 等于集合 \(\{1, 2, \dots, m\}\) 中与 \(m\) 互质的元素个数。例如： \(\phi(1) = 1\)，因为 1 与自身互质。 \(\phi(9) = 6\)，因为与 9 互质的数有 1, 2, 4, 5, 7, 8。 若 \(m\) 有标准素数分解 \(m = p_ 1^{k_ 1} p_ 2^{k_ 2} \cdots p_ r^{k_ r}\)，则： \[ \phi(m) = m \left(1 - \frac{1}{p_ 1}\right) \left(1 - \frac{1}{p_ 2}\right) \cdots \left(1 - \frac{1}{p_ r}\right) \] 例如，\(m = 12 = 2^2 \cdot 3\)，则： \[ \phi(12) = 12 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 12 \cdot \frac{1}{2} \cdot \frac{2}{3} = 4 \] 实际验证：与 12 互质的数有 1, 5, 7, 11，共 4 个。 2. 简化剩余系与乘法群 模 \(m\) 的简化剩余系是指模 \(m\) 的一个完全剩余系中所有与 \(m\) 互质的数构成的集合。例如，模 9 的简化剩余系为 \(\{1, 2, 4, 5, 7, 8\}\)，其元素个数正好是 \(\phi(9) = 6\)。这些数在模 \(m\) 乘法下构成一个群，称为模 \(m\) 的乘法群，记作 \((\mathbb{Z}/m\mathbb{Z})^\times\)。该群的阶即为 \(\phi(m)\)。 3. 欧拉定理的证明思路 欧拉定理的证明基于群论中的拉格朗日定理：有限群的阶必是其子群阶的倍数。具体步骤为： 考虑模 \(m\) 的乘法群 \((\mathbb{Z}/m\mathbb{Z})^\times\)，其阶为 \(\phi(m)\)。 对任意 \(a\) 满足 \(\gcd(a, m) = 1\)，\(a\) 在群中对应的元素生成一个循环子群。 由拉格朗日定理，子群的阶（即 \(a\) 的阶）必整除群的阶 \(\phi(m)\)，故 \(a^{\phi(m)} \equiv 1 \pmod{m}\)。 4. 欧拉定理与费马小定理的关系 费马小定理是欧拉定理在 \(m\) 为素数时的特例。若 \(m = p\) 为素数，则 \(\phi(p) = p - 1\)，欧拉定理变为： \[ a^{p-1} \equiv 1 \pmod{p} \] 这正是费马小定理的表述。因此，欧拉定理可视为费马小定理在模数为合数时的推广。 5. 欧拉定理的应用实例 欧拉定理在计算大数幂的模运算中非常有用。例如，计算 \(7^{100} \bmod 9\)： 由于 \(\gcd(7, 9) = 1\) 且 \(\phi(9) = 6\)，由欧拉定理： \[ 7^6 \equiv 1 \pmod{9} \] 将 \(100\) 除以 \(6\) 得余数 \(4\)，因为 \(100 = 6 \cdot 16 + 4\)，故： \[ 7^{100} = (7^6)^{16} \cdot 7^4 \equiv 1^{16} \cdot 7^4 \pmod{9} \] 计算 \(7^4 = 2401\)，且 \(2401 \div 9 = 266 \cdot 9 + 7\)，所以： \[ 7^{100} \equiv 7 \pmod{9} \] 因此，\(7^{100} \bmod 9 = 7\)。 6. 欧拉定理的推广与限制 欧拉定理要求 \(a\) 与 \(m\) 互质。若不互质，结论不一定成立。例如，取 \(a = 2, m = 4\)，则 \(\phi(4) = 2\)，但 \(2^2 = 4 \equiv 0 \not\equiv 1 \pmod{4}\)。此外，欧拉定理可推广到卡迈克尔函数的情形，用于处理更一般的模数。 最终，欧拉定理的结果可总结为： \[ \boxed{a^{\phi(m)} \equiv 1 \pmod{m} \quad \text{当} \quad \gcd(a, m) = 1} \]