欧拉定理和函数的一些理解
欧拉定理，先放式子：
\[a^{\varphi(m)}\equiv 1\pmod{m} \]前提是 \(\gcd(a,m)=1\)。
证明：设 \(r_1,r_2,...r_{\varphi(m)}\) 为 \(\mod m\) 意义下的一个简化剩余系，那么 \(ar_1,ar_2,...ar_{\varphi(m)}\) 也为 \(\mod m\) 意义下的一个简化剩余系。
所以：
\[r_1r_2...r_{\varphi(m)}\equiv ar_1ar_2...ar_{\varphi(m)}\pmod{m} \]化简：
\[r_1r_2...r_{\varphi(m)}\equiv a^{\varphi(m)}r_1r_2...r_{\varphi(m)}\pmod{m} \]两边一消，则可得 \(a^{\varphi(m)}\equiv 1\pmod{m}\)。
扩展欧拉定理：
\[a^b\equiv \begin{cases} a^{b\mod \varphi(m)},&\gcd(a,m)=1\\ a^{b},&\gcd(a,m)\neq 1,b<\varphi(m)\\ a^{b\mod \varphi(m)+\varphi(m)},&\gcd(a,m)\neq 1,b\ge \varphi(m) \end{cases} \]证明还不会。
欧拉函数：
- 欧拉函数是一个奇性函数，\(\varphi(ab)=\varphi(a)\varphi(b)\)。