欧拉定理oula dingli

费尔马定理的一个推广.若m是大于1的整数，(a,m)=1，则a^φ(m) ≡ 1(modm)，这就是著名的欧拉定理.
当m=p为质数时，则由欧拉定理可得a^p-1 ≡ 1(modp)，即费尔马定理.证明：设r¹,r²，…，r^φ(m)，是模m的一个简化剩余系，因为(a,m)=1，故ar₁,ar₂，…，a r_{φ (m)}，也是模m的一个简化剩余系. 因此

(ar₁) (ar₂)…(ar_φ(m)) ≡ r₁r₂…r_φ(m)(modm)

即a^φ(m)r₁r₂…rφ(_m)≡r₁r₂…r_φ(m) (modm)
但(r_i,m)=1,i=1,2，…φ(m)，故(r₁r₂…r_φ(m),m)=1.于是a^φ(m)≡1(modm).
欧拉定理的应用很广，如，可以用来简化求余数
的计算，例如，求1777¹⁸⁵⁰被45除的余数. 因为
φ (45) = φ (3²·5) =24,(1 777,45)=1，及1 850=24×77+2，故由欧拉定理可得

1777¹⁸⁵⁰ =(1777²⁴)⁷⁷ ·1777² ≡ 17772 ≡ 22²≡ 484≡34(mod45)

即余数为34.
利用欧拉定理还可以解一元一次同余式 (参见“一次同余式的解法”)