费马小定理

费马小定理

费马小定理

定义：若 p p p为素数， g c d ( a , p ) = 1 gcd(a,p)=1 gcd(a,p)=1，则 a p − 1 ≡ 1 ( m o d   p ) a^{p-1}\equiv1(mod\:p) ap−1≡1(modp)。
另一个形式： a p ≡ a ( m o d   p ) a^p\equiv a(mod\:p) ap≡a(modp)。

费马小定理降幂： a m ≡ a m % p ( m o d   p ) ， g c d ( a , p ) = 1 a^m\equiv a^{m\%p}(mod\:p)，gcd(a,p)=1 am≡am%p(modp)，gcd(a,p)=1。

证明：

方法一：数学归纳法

1. 当 a = 0 a=0 a=0时，显然成立。
2. 当 a p ≡ a ( m o d   p ) a^p\equiv a(mod\:p) ap≡a(modp)成立时： ( a + 1 ) p = a p + C p 1 a p − 1 + ⋯ + C p p − 1 a + 1 (a+1)^p=a^p+C^1_pa^{p-1}+\dots+C^{p-1}_pa+1 (a+1)p=ap+Cp1​ap−1+⋯+Cpp−1​a+1。我们发现 p ∣ C p i ( i = 1 , 2 , … , p − 1 ) p|C^i_p(i=1,2,\dots,p-1) p∣Cpi​(i=1,2,…,p−1)，那么 ( a + 1 ) p ≡ a p + 1 ( m o d   p ) (a+1)^p\equiv a^p+1(mod\:p) (a+1)p≡ap+1(modp)，因为我们已知 a p ≡ a ( m o d   p ) a^p\equiv a(mod\:p) ap≡a(modp)，所以 ( a + 1 ) p ≡ a p + 1 ≡ a + 1 ( m o d   p ) (a+1)^p\equiv a^p+1\equiv a+1(mod\:p) (a+1)p≡ap+1≡a+1(modp)。证毕。

方法二：欧拉定理证明

其实费马小定理就是欧拉定理的特殊情况。

已知欧拉定理 a φ ( p ) ≡ 1 ( m o d   p ) a^{\varphi(p)}\equiv1(mod\:p) aφ(p)≡1(modp)，当 p p p是素数时， φ ( p ) = p − 1 \varphi(p)=p-1 φ(p)=p−1。证毕。