欧拉定理（欧拉函数）：\(y=\varphi(n)\)
1. 欧拉定理陈述
在数论中，欧拉定理表述为：若\(n\)和\(a\)是互质的正整数，那么\(a^{\varphi(n)}\equiv1\pmod{n}\)，其中\(\varphi(n)\)是小于等于\(n\)且与\(n\)互质的正整数的个数，这个函数被称为欧拉函数。
例如，当\(n = 10\)时，与\(10\)互质的数有\(1\)、\(3\)、\(7\)、\(9\)，所以\(\varphi(10)=4\)。如果\(a = 3\)，那么\(3^{4}=81\)，\(81\div10 = 8\cdots\cdots1\)，即\(3^{4}\equiv1\pmod{10}\)，这就验证了欧拉定理。
2. 欧拉定理证明过程
设\(r_{1},r_{2},\cdots,r_{\varphi(n)}\)是小于等于\(n\)且与\(n\)互质的正整数。
因为\(a\)与\(n\)互质，所以\(ar_{1},ar_{2},\cdots,ar_{\varphi(n)}\)这\(\varphi(n)\)个数除以\(n\)所得的余数也都与\(n\)互质，并且这些余数两两不同。
假设\(ar_{i}\equiv ar_{j}\pmod{n}\)（\(i\neq j\)），那么\(n\mid a(r_{i}-r_{j})\)，由于\(a\)与\(n\)互质，所以\(n\mid(r_{i}-r_{j})\)，但\(0 <\vert r_{i}-r_{j}\vert < n\)，这是矛盾的，所以\(ar_{1},ar_{2},\cdots,ar_{\varphi(n)}\)除以\(n\)的余数是\(r_{1},r_{2},\cdots,r_{\varphi(n)}\)的一个排列。
所以\((ar_{1})(ar_{2})\cdots(ar_{\varphi(n)})\equiv r_{1}r_{2}\cdots r_{\varphi(n)}\pmod{n}\)，即\(a^{\varphi(n)}(r_{1}r_{2}\cdots r_{\varphi(n)})\equiv r_{1}r_{2}\cdots r_{\varphi(n)}\pmod{n}\)。
因为\((r_{1}r_{2}\cdots r_{\varphi(n)})\)与\(n\)互质，所以可以在两边同时约去\((r_{1}r_{2}\cdots r_{\varphi(n)})\)，得到\(a^{\varphi(n)}\equiv1\pmod{n}\)。
3. 欧拉定理与费马小定理的关系
费马小定理是欧拉定理的一个特殊情况。当\(n\)为质数\(p\)时，\(\varphi(p)=p - 1\)，此时欧拉定理就变成了费马小定理\(a^{p - 1}\equiv1\pmod{p}\)（\(a\)与\(p\)互质）。
4. 欧拉定理应用领域
密码学：在RSA公钥加密算法中，欧拉定理起到了关键作用。RSA算法的安全性基于两个大素数相乘容易，但对其乘积进行分解非常困难的原理。在加密和解密过程中，涉及到模幂运算，而欧拉定理为这种运算提供了理论依据，使得通过公钥加密的信息可以通过私钥有效地解密。
同余方程求解：在求解同余方程时，欧拉定理可以帮助判断方程是否有解以及求解的思路。例如，对于同余方程\(a^{x}\equiv b\pmod{n}\)（\(a\)与\(n\)互质），可以利用欧拉定理将指数\(x\)与\(\varphi(n)\)建立联系，从而找到可能的解。
数论其他问题的研究：在研究数的整除性、数的循环节等问题时，欧拉定理是一个重要的工具。例如，在研究分数\(\frac{1}{n}\)（\(n\)为整数）在不同进制下的循环节长度时，会用到欧拉函数和欧拉定理来进行分析。
