欧拉定理（Euler's theorem）内容如下：
若 gcd(a,m)=1\gcd(a, m) = 1，则
aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}
证明
实际上这个证明过程跟费马小定理的证明过程是非常相似的：构造一个与 mm 互质的数列，再进行操作。
设 r1,r2,⋯ ,rφ(m)r_1, r_2, \cdots, r_{\varphi(m)} 为模 mm 意义下的一个简化剩余系，则 ar1,ar2,⋯ ,arφ(m)ar_1, ar_2, \cdots, ar_{\varphi(m)} 也为模 mm 意义下的一个简化剩余系。所以 r1r2⋯rφ(m)≡ar1⋅ar2⋯arφ(m)≡aφ(m)r1r2⋯rφ(m)(modm)r_1r_2 \cdots r_{\varphi(m)} \equiv ar_1 \cdot ar_2 \cdots ar_{\varphi(m)} \equiv a^{\varphi(m)}r_1r_2 \cdots r_{\varphi(m)} \pmod{m}，可约去 r1r2⋯rφ(m)r_1r_2 \cdots r_{\varphi(m)}，即得 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1 \pmod{m}。