费马小定理

费马小定理

设p为素数，a是任意整数，且，则

证明

先来说明一个引理

引理

设p是素数，a是任何整数，且，则数列

于数列

相同（忽略次序）。

引理证明

数列，含有 个数字。

任取两个数和，假设它们同余：

则，又因为，所以。

而，则 ，仅有时，。

所以，模p不同余。

p-1个数模p不同余，这p-1个余数一定就是。得证。

证明费马小定理

引理中的两个数列连乘得：

即

又有与互素，两边消掉得

得证。

利用费马小定理简单判断一个数是不是质数

a可以随便取，比如取2，只要计算出，那就说明m不是质数。 比如

当时，，所以不是质数。

注意，若 ，m不一定是质数