費馬小定理與歐拉定理 原理與證明

一、歐拉定理

1、定義

若a與n互質，則 a φ ( n ) ≡ 1 a^{\varphi (n)} \equiv 1 aφ(n)≡1 (mod n)。

其中 φ ( n ) \varphi (n) φ(n)指歐拉函數：小于n的正整數中與n互質的個數。

2、證明

我們假設n的質因子分别是： p 1 , p 2 , . . . , p φ ( n ) p_1,p_2,...,p_{\varphi(n)} p1​,p2​,...,pφ(n)​，記為序列1。

若給每一項都乘a，得序列2： a p 1 , a p 2 , . . . , a p φ ( n ) ap_1,ap_2,...,ap_{\varphi(n)} ap1​,ap2​,...,apφ(n)​。

因為 a a a與n互質，且 p i p_i pi​與n互質，是以 a p i ap_i api​也與n互質。且 a p i ap_i api​ % n各不相同。這個可以用反證法證得：若假設 a p i ≡ a p j ap_i \equiv ap_j api​≡apj​ (mod n)，則兩邊同除以a，得 p i ≡ p j p_i \equiv p_j pi​≡pj​，又因為 p i p_i pi​和 p j p_j pj​是n的質因子，其互不相同，則原假設不成立。

則可得序列2對n取餘所得餘數就是序列1，小于n的正整數且與n互質的數有且隻有 φ ( n ) \varphi (n) φ(n)個，就是這個序列1。

是以将序列2模n後累乘起來和序列1累乘起來的結果是相同的（模n等同于同餘n），即可得： a φ ( n ) ⋅ ( a 1 ⋅ a 2 ⋅ . . . ⋅ a φ ( n ) ) ≡ a 1 ⋅ a 2 ⋅ . . . ⋅ a φ ( n ) a^{\varphi(n)} \cdot (a_1\cdot a_2\cdot ... \cdot a_{\varphi(n)}) \equiv a_1\cdot a_2\cdot ... \cdot a_{\varphi(n)} aφ(n)⋅(a1​⋅a2​⋅...⋅aφ(n)​)≡a1​⋅a2​⋅...⋅aφ(n)​ (mod n)

兩邊同時除以 a 1 ⋅ a 2 ⋅ . . . ⋅ a φ ( n ) a_1\cdot a_2\cdot ... \cdot a_{\varphi(n)} a1​⋅a2​⋅...⋅aφ(n)​可得 a φ ( n ) ≡ 1 a^{\varphi(n)} \equiv 1 aφ(n)≡1 (mod n)。

二、費馬小定理

1、定義

若a與n互質，且n為質數，則 a n − 1 ≡ 1 a^{n-1}\equiv1 an−1≡1 (mod n)。

2、證明

費馬小定理其實就是歐拉定理的一個特殊情況，當n是質數時，小于n的正整數都和n互質，是以他的歐拉函數就等于 a n − 1 a^{n-1} an−1，即 a φ ( n ) = a n − 1 a^{\varphi(n)}= a^{n-1} aφ(n)=an−1，則根據歐拉定理，費馬小定理成立。