欧拉定理是数论中的一个重要定理，由瑞士数学家莱昂哈德·欧拉提出。这个定理指出，如果两个正整数a和n互质，那么a的φ(n)次幂除以n的余数等于1。这里φ(n)是欧拉函数，表示小于n且与n互质的正整数的个数。欧拉定理在现代密码学中有广泛应用，特别是在RSA加密算法中。
欧拉函数φ(n)是欧拉定理中的核心概念。它表示小于或等于n且与n互质的正整数的个数。两个数互质意味着它们的最大公约数是1。例如，φ(6)等于2，因为在1到6之间，只有1和5与6互质。φ(8)等于4，因为1,3,5,7都与8互质。φ(12)也等于4，因为1,5,7,11与12互质。在图中，我们可以看到一个圆上标记了从1到12的数字，其中红色点表示与12互质的数。
现在我们来看欧拉定理的证明思路。首先，考虑集合S，它包含所有小于n且与n互质的数，这些数的个数是φ(n)。然后，考虑新集合T，它是将集合S中的每个元素乘以a后再对n取模得到的结果。可以证明，集合S和集合T包含相同的元素，只是顺序可能不同。因此，两个集合中所有元素的乘积在模n的意义下是相等的。这意味着r₁·r₂·...·rₖ与a^k·r₁·r₂·...·rₖ模n同余。约去相同项，我们得到1与a^φ(n)模n同余，这就是欧拉定理。以n=7为例，φ(7)=6，集合S是{1,2,3,4,5,6}，当a=2时，集合T是{2,4,6,1,3,5}，可以验证2^6≡1(mod 7)。
欧拉定理在现代密码学和计算机科学中有广泛应用。最著名的应用是RSA加密算法，这是一种公钥加密系统。在RSA中，加密过程是计算m^e mod n，其中m是消息，e是公钥，n是两个大质数的乘积。解密则是计算c^d mod n，其中c是密文，d是私钥。私钥d和公钥e满足ed ≡ 1 (mod φ(n))。欧拉定理还用于模运算优化，当计算大数的模幂时，可以利用a^b mod n = a^(b mod φ(n)) mod n来提高效率。此外，当n是质数p时，欧拉定理简化为费马小定理：a^(p-1) ≡ 1 (mod p)。在我们的RSA示例中，选择p=5，q=11，计算n=55，φ(n)=40，公钥e=7，私钥d=23，可以验证加密和解密过程。
总结一下，欧拉定理是数论中的一个基本定理，它指出：如果a与n互质，那么a的φ(n)次幂除以n的余数等于1。欧拉函数φ(n)表示小于等于n且与n互质的正整数的个数。这个定理的证明基于一个重要性质：将所有与n互质的数分别乘以a后再对n取模，得到的集合与原集合包含相同的元素。欧拉定理在现代密码学中有广泛应用，特别是在RSA加密算法中。此外，它还用于模运算优化，可以大大提高大数模幂运算的效率。当n是质数p时，欧拉定理简化为费马小定理：a^(p-1) ≡ 1 (mod p)。欧拉定理是连接数论与现代密码学的重要桥梁。