欧拉定理
设\(a,m\)是正整数,且\(\gcd(a,m)=1\),那么\(a^{\varphi (m)}\equiv 1(\bmod m)\)
欧拉定理的推论:
设\(a,m\)是正整数,且\(\gcd(a,m)=1\),那么\(a^b\equiv a^{b\bmod \varphi (m)}(\bmod m)\)
关于费马小定理:
我们知道,若\(m\)为质数,则\(\varphi (m)=m-1\)
就有\(a^{m-1}\equiv 1(\bmod m)\),这就是费马小定理
扩展欧拉定理
若\(b>= \varphi(m)\),则\(a^b \equiv a^{b\bmod \varphi(m)+\varphi(m)} (\bmod m)\)