费马小定理的两个证明

费马小定理的两个证明

费马小定理：p为素数，a为任意自然数，则 $a^{p} \equiv a \left ( mod \enspace p \right )$

证明1：使用数学归纳法。

当a=1, 显然等式左右都是1，成立。

设当a=k时，p|（ $k^{p} - k$ ）,考虑a=K+1的情况

$(k+1)^{p} - (k+1)$

前面可以用二项式定理展开与后面相减，

二项式展开第一项为1，最后一项为 $k^{p}$ .上面的差值=

$\sum_{i=1}^{p-1}C_{p}^{i}k^{i} + (k^{p} - k)$

前面一项能整除p，后面一项根据前提假设也能整除p，故

p| $(k+1)^{p} - (k+1)$

根据数学归纳法，对任意自然数a， p| $a^{p} - a$ 都成立，

证毕。

证明2：

引理1

若a，b，c为任意3个整数,m为正整数，且(m,c)=1，则当a·c≡b·c(mod m)时，有a≡b(mod m)。

证明：a·c≡b·c(mod m)可得ac–bc≡0(mod m)可得(a-b)·c≡0(mod m)。因为(m,c)=1即m,c互质，c可以约去，a– b≡0(mod m)可得a≡b(mod m)。

引理2

设m是一个整数且m>1，b是一个整数且(m,b)=1。如果a[1],a[2],a[3],a[4],…a[m]是模m的一个完全剩余系，则b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]也构成模m的一个完全剩余系。

证明：若存在2个整数b·a[i]和b·a[j]同余即b·a[i]≡b·a[j](mod m)..(i>=1 && j>=1)，根据引理1则有a[i]≡a[j](mod m)。根据完全剩余系的定义可知这是不可能的，因此不存在2个整数b·a[i]和b·a[j]同余。所以b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]构成模m的一个完全剩余系。

构造素数p 的完全剩余系 $P=\left \{ 1,2,3,..., p-1 \right \}$

因为a,p 互质，由引理2可得

$A=\left \{ a,2a, 3a, ..., (p-1)a \right \}$

也是p的一个完全剩余系。由完全剩余系的性质，

即

$\left ( p-1 \right )!\ast a^{p-1} = \left ( p-1 \right )!\(mod\enspace p)$

易知，两边可约去(p-1)!，得到

$a^{p-1}\equiv 1(mod \enspace p)$

证毕。

参考链接：

费马小定理（Fermat's Little Theorem） - 知乎 (zhihu.com)

费马小定理_百度百科 (baidu.com)
相关阅读:
[每周一更]-(第13期)：灰度测试的解释说明
 Vue入门教学——编写第一个页面
 神经网络参数量和计算量,神经网络是参数模型吗
 零基础学python：错误与异常
 【无标题】
CVPR2023 RIFormer, 无需TokenMixer也能达成SOTA性能的极简ViT架构
 做软件测试一定要注意的细节
 css中BFC外边距塌陷解决办法
 每日练习------定义一个N*N二维数组，从键盘上输入值，找出每行中最大值组成一个一维数组并输出；
Linux查看文件大小的几种方法
原文地址：https://blog.csdn.net/zkmrobot/article/details/127604799

引理1

引理2