今天讲一讲费马小定理

定理内容:

若存在整数$a,p$,满足$GCD(a,p)=1$,即$a,p$互质,那么$a^{p-1}≡1 (mod p)$,即在上述条件下,$a^{p-1}$%$p=1$

证明前需要知道一些性质

性质1:若存在三个整数$a,b,c,$以及一个和$c$互质的整数$m$,那么如果$a \ast c≡b \ast c (mod m)$,那么$a≡b (mod m)$

证明1:若$a \ast c ≡ b \ast c (mod m)$,则$a \ast c$%$m = b \ast c$%$m$,那么$(a \ast c - b \ast c )$%$m=0$,那么$(a-b) \ast c≡0 (mod m)$,因为$m$和$c$互质,所以$(a-b)$%$m=0$,则$a≡b (mod m)$

性质2:若两个整数$m,b$互质,{$a_i$}为模$m$的一个完全剩余系,(完全剩余系就是$0~m-1$),那么$b \ast ${$a_i$}在模$m$意义下,也是$m$的一个完全剩余系

证明2:若$b \ast ${$a_i$}在模$m$的意义下,不是一个$m$的完全剩余系,那么一定存在$b \ast a_i≡b \ast a_j (mod m)$,因为$m,b$互质,所以由上面的性质$1$可得上述等式成立的条件为$a_i=a_j$,但因为$a_i$和$a_j$为$m$剩余系中的两个值,所以$a_i$和$a_j$一定不相等,所以可得$b \ast ${$a_i$}在模$m$的意义下为$m$的一个剩余系

证明定理过程:

现在回到费马小定理的证明,$p$是一个质数,$a$和$p$互质,那么构造$p$的完全剩余系(将0先视为没有)$b_i=${$1,2,…,p-1$},再构造$a \ast b_i=${$a \ast 1,a \ast 2 ,…, a \ast (p-1)$},将$b_i$累乘得到$b_1 \ast b_2 \ast … \ast b_{p-1}$,把$a * b_i$累乘得到$a \ast b_1 \ast a \ast b_2 \ast … \ast a \ast b_{p-1}$,发现第二个式子因为是$p-1$个式子的连乘,所以一共有$p-1$个$a$,所以把$a$提出来的到$a^{p-1}$,将$b_i$的连乘化简得到$(p-1)!$,$a \ast b_i$就变成了$a^{p-1} \ast (p-1)!$,由模意义下的乘法不影响取模运算结果可知,$(p-1)!≡(p-1)! \ast a^{p-1} (mod p)$,两边约去$(p-1)!$,那么可得$a^{p-1}≡1 (mod p)$

备注:

费马小定理是欧拉定理一个特殊情况下的形式,欧拉定理的证明我会在后面的博文中给出,这篇证明若有不当请联系作者指正,谢谢