在1763中，欧拉研究了函数$\varphi(n)$（符号$\varphi$后来出现，与高斯一起）：从1到$n$与$n$没有公因数的数字的个数。 例如，$\varphi(10) = 4$，因为从1到10只有1、3、7和9是合适的。他证明了如果$a$不 与 $n$ 有公因数，所以

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

请参阅 $n = 10$ 和 $a = 3$ 的想法。将数字 1、3、7 和 9 乘以 3：

$$3 \cdot 1 = 3, \quad 3 \cdot 3 = 9, \quad 3 \cdot 7 = 21 \equiv 1, \quad 3 \cdot 9 = 27 \equiv 7 \pmod{10}.$$
在10小时时钟上，乘以3、7或9只会打乱数字1、3、7和9。

余数为 3、9、1 和 7：相同的四个数字，只是打乱了。所以他们的产品是 相同：

$$(3 \cdot 1)(3 \cdot 3)(3 \cdot 7)(3 \cdot 9) \equiv 1 \cdot 3 \cdot 7 \cdot 9 \pmod{10}$$ $$3^4 \cdot (1 \cdot 3 \cdot 7 \cdot 9) \equiv 1 \cdot 3 \cdot 7 \cdot 9 \pmod{10}.$$

由于$1 \cdot 3 \cdot 7 \cdot 9$与10没有公因数，所以两边可以消去： $3^4 \equiv 1 \pmod{10}$。检查：$3^4 = 81$，除以10时留下余数1。一样的 参数适用于任何 $n$ 和任何与 $n$ 没有公因数的 $a$。

当$n$为素数时，$\varphi(n) = n - 1$和定理变成费马小定理。超过 200 年后，在 1977 年，欧拉定理成为 RSA 的基础，该加密系统 保护互联网购物和手机短信。

莱昂哈德·欧拉的所有主题 · ← 费马非素数 · 其他贡献和遗产 →

图片来源和来源.