费马小定理的证明
邓布利多6
·
·
个人记录
费马小定理 ： 若 (a,p)=1 , 则 a^{\,p-1} \equiv 1\,(mod \,\,p) .
- 步骤 1 : 证明二项式定理 : (x+y)^n=\sum_{i=0}^{n} \binom{n}{i} \,\,x ^i \, y^{n-i}
证明：(x+y)^n 的展开中的第 i+1 项： x^{n-i}\, y^{i} .
所以有 $\binom{n}{i}$ 种不同的选择方法，得证。
------------
- 步骤 $2$ : 当 $1<i<p$ 时，$p\,|\,\binom{p}{i}
证明: \binom{p}{i}=\frac{p×(p-1)×…×(p-i+1)}{1×2×…×i}
令 a=p×(p-1)×…×(p-i+1) , b=1×2×…×i，则\binom{p}{i}=\frac{a}{b} .
显然 p\;|\;a , 而 1<i<p，所以 p∤1,p∤2,…,p∤i, 所以，p∤b。
由于 \frac{a}{b}∈Z, 若 p∤\frac{a}{b}，再由 p∤b 得知 p∤a, 矛盾。
所以：p\,|\binom{p}{i}，得证。
-
当 a=1 时，a^p=1\equiv a(mod \;p)，成立；
-
假设对正整数 a , 我们有：a^p \equiv a(mod \;p) , 则：
由二项式定理： (a+1)^p= \sum_{i=0}^{p} \binom{p}{i} a^i=1+\sum_{i=1}^{p-1} \binom{p}{i} a^i+a^p
由于 1<i<p 时，p\;|\,\binom{p}{i}，所以两边模 p 取余数有：
(a+1)^p=1+a^p (mod \;p)
由归纳假设得：(a+1)^p=1+a(mod \; p)。
综合 1 , 2，得证。