歐拉定理 費馬小定理

歐拉定理：

若 gcd(a,m)=1 g c d ( a , m ) = 1 ，則 aφ(m)≡1(modm) a φ ( m ) ≡ 1 ( mod m ) 。

其中 φ(m) φ ( m ) 是歐拉函數，它表示在不超過m的正整數中與m互質的數的個數。

例如: φ(1)=1,φ(2)=1,φ(3)=2,φ(4)=2,φ(5)=4,φ(6)=2, φ ( 1 ) = 1 , φ ( 2 ) = 1 , φ ( 3 ) = 2 , φ ( 4 ) = 2 , φ ( 5 ) = 4 , φ ( 6 ) = 2 , 等等。

費馬小定理:

假如p是質數，且 gcd(a,p)=1 g c d ( a , p ) = 1 ，那麼 ap−1≡1(modp) a p − 1 ≡ 1 ( mod p ) 。

其實可以認為是歐拉定理的一個特例，因為當p為質數時， φ(p)=p−1 φ ( p ) = p − 1 。