费马小定理&&欧拉定理

费马小定理是模数为质数的欧拉定理，也就是说，欧拉定理是强化版，可直接证明到费马小定理。

若p为质数，\(gcd(a,p)=1\)，则\(a^{p-1}\equiv1(mod\,p)\)

证明：

思路，用p的完全剩余系去乘a

设一个质数为p，我们取一个不为p倍数的数a，

构造一个序列：A={1，2，3，...，p-1}，

先证明这个\(\Pi_{i=1}^{p-1}A_i\equiv\Pi_{i=1}^{p-1}{A_i\times{a}}(mod\,p)\)

由于\((A_i,p)=1,(A_i\times{a},p)=1\)，

再加上\(A_i\times{a}(mod\,p)<p\),\(A_i\times{a}(mod\,p)\)又各不相同（假设相同会推出矛盾），

故引理成立

又因为\(\Pi_{i=1}^{p-1}A_i\)和p互质，所以两边约成\(a^{p-1}\equiv1(mod\,p)\)

接下来是欧拉定理的证明：

若\((a,m)=1\)，则\(a^{\varphi(m)}\equiv1(mod\,m)\)

证明：

思路，用m的简化剩余系去乘a

构造一个序列：\(r={r1,r2,r3,...,r_{\varphi_{(m)}}}\)

同样可以证明到：\(\Pi_{i=1}^{\varphi_{(m)}}r_i\equiv\Pi_{i=1}^{\varphi_{(m)}}{r_i\times{a}}(mod\,m)\)

同样可以化简到\(a^{\varphi(m)}\equiv1(mod\,m)\)

扩展欧拉定理

\(a^{b} \equiv\left\{\begin{array}{ll} a^{b \bmod \varphi(m)}, & \operatorname{gcd}(a, m)=1, \\ a^{b}, & \operatorname{gcd}(a, m) \neq 1, b<\varphi(m), \quad(\bmod m) \\ a^{(b \bmod \varphi(m))+\varphi(m)}, & \operatorname{gcd}(a, m) \neq 1, b \geq \varphi(m) . \end{array}\right.\)

俗称降幂公式