费马小定理的两个证明

费马小定理的两个证明

费马小定理：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)
相关阅读:
字符函数和字符串函数(下)
IC front-end design engineer
【Linux】进程概念与进程状态
 Python中的三个基本知识点
 变量使用volatile和不使用volatile的区别
 Python自动化框架【pytest 框架介绍】
内核将驱动编译成模块报函数或者变量undefined的错误
 外骨骼机器人混战：程天科技做“深”，傅利叶智能做“广”
20221206英语学习
 SpringCloud的服务发现框架 — Eureka — Eureka集群构建流程
原文地址：https://blog.csdn.net/zkmrobot/article/details/127604799

引理1

引理2