欧拉定理和欧拉函数 - NOI提高级教程

📖 欧拉函数性质与定理

欧拉函数 (Euler's Totient Function)，记作 $\phi(n)$，表示在 $[1, n]$ 中与 $n$ 互质（$\gcd(i, n) = 1$）的正整数个数。它是数论的核心工具之一，广泛应用于 RSA 加密及同余幂降幂操作。

根据唯一分解定理，任何大于 1 的整数 $n$ 可表示为 $n = p_1^{c_1} p_2^{c_2} \cdots p_k^{c_k}$。其欧拉函数的通式为：

$\phi(n) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right) = n \times \frac{p_1 - 1}{p_1} \times \frac{p_2 - 1}{p_2} \cdots \frac{p_k - 1}{p_k}$

当 $p$ 为质数时，$\phi(p) = p - 1$。由于欧拉函数是积性函数，若 $\gcd(a, b) = 1$，则 $\phi(a \cdot b) = \phi(a) \cdot \phi(b)$。

欧拉定理 (Euler's Theorem)：若正整数 $a$ 和 $n$ 互质（即 $\gcd(a, n) = 1$），则：

$a^{\phi(n)} \equiv 1 \pmod n$

当 $n$ 为质数 $p$ 时，$\phi(p) = p - 1$，定理退化为费马小定理 $a^{p-1} \equiv 1 \pmod p$。

数值 N:

调节上方参数，选择对应的模式。点击“开始演示”可以逐步观察算法细节。

当前状态就绪

已找出质因子 -

互质元素集合 -

欧拉函数值 φ(N) -

📋 求解推导历史步骤