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

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

就是这个：$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的倍数）。

$(p-1)!$可以表示为一个集合{1，2，3，···，p-1}中所有元素的乘积。

我们来做一些高兴的事情（大雾）。

将这个集合中所有的元素都乘上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)，也就是一开始的费马小定理。