欧拉定理和密码学
在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。 Ative o JavaScript para ver esta figura interativa.
余数为 3、9、1 和 7:相同的四个数字,只是打乱了。所以他们的产品是 相同: