费马小定理与欧拉定理原理与证明

悠悠 2022-09-04 15:53 168阅读 0赞

### 一、欧拉定理 ###

#### 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，则根据欧拉定理，费马小定理成立。