blackwolf/content/math/欧拉余数定理.md

title	date	math	categories	tags	format
欧拉余数定理	2024-01-05	true	奥数 余数	余数定理 欧拉定理 素数	hugo-md

欧拉余数定理

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

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

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

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

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

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

其中，p 是素数。

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