证明费马小定理 学习笔记

· · 个人记录

证明一个定理首先要知道这个定理是什么。——沃·兹基硕德·斐桦

那么费马小定理是什么呢？

就是这个：a^{p-1}\equiv1(mod p)，其中a与p互素，p是质数。

那么怎么证呢？

先把这个定理丢掉，考虑这样一个东西。

(p-1)!

靠这是什么

p还是那个p，而(p-1)!就是1\times2\times3\times···\times(p-1)。

对于(p-1)!，有p\nmid(p-1)!（因为p是质数，而没有一个x_i(1≤x_i≤p-1)是p的倍数）。

**我们来做一些高兴的事情（大雾）。** 将这个集合中所有的元素都乘上a，得到一个新集合{a，2a，3a，···，(p-1)a}。 --- 而这个**集合中任意两个数在mod p意义下都不相同。** ### 证明 设$ax\equiv ay$(mod p)且**1≤x,y≤p−1，x,y均为整数，x≠y**,则$(x-y)a=tp$，$∴p\mid(x-y)a$。 又∵a与p互素，$∴p\mid(x-y)$，而这显然是不可能的$(1≤x,y≤p−1)$。 --- 又∵**这个集合中任意两个数在mod p意义下都不相同**，∴这个集合中所有元素的乘积和原集合这个集合中所有元素的乘积**在mod p意义下是等价的**。 也就是说$a^{p-1}\times(p-1)!\equiv (p-1)!$(mod p)。 整理一下这个式子（两边同时乘上$(p-1)!$的逆元），即得$a^{p-1}\equiv1$(mod p)，也就是一开始的费马小定理。