欧拉余数定理

欧拉余数定理是数论中的一个基本结果，它是费马小定理的推广。其陈述如下：

对于任意正整数 $a$ 和与 $a$ 互质的正整数 $n$，欧拉余数定理表述为：

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

其中，$\phi(n)$ 是欧拉函数，表示小于或等于 $n$ 且与 $n$ 互质的正整数的个数。

特别地，当 $n$ 是素数时，欧拉余数定理就变成了费马小定理：

$$a^{p-1} \equiv 1 \pmod{p}$$

其中，$p$ 是素数。

欧拉余数定理在各个领域有着广泛的应用，包括密码学，在 RSA 加密算法中有着显著的用途。