费马小定理之素数判定（费马小定理之素数判定）

我们还是惯例，先复习费马小定理。

我们可以得到这个推论：

证明不难：

说明：≡−1(mod p)的意思和≡p−1 (mod p)是一样的。

例如：1!≡−1 (mod 2)

2!=2≡−1(mod 3)

4!=24≡−1 (mod 5)

6!=720≡−1 (mod 7)

10!=3628800≡−1 (mod 11)

显然，推论写成：

都是等价的。

反过来，如果p不是素数呢？

如果p不是素数，不妨设p=m⋅n

则m、n是p的因子，也是(p−1)!的因子

所以，(p−1)!能被m、n整除

即(p−1)!能被mn=p整除

即(p−1)!≡0 (mod p)

于是，我们得到了一个惊世骇俗的结论：

现在我宣布，我解决了困扰数论届数百年的素数判定问题！

费马微微一笑：小子！想太美了，你知道阶乘的运算量有多大吗！你知道阶乘之后作求模运算量有多大吗！这性质能用来判定素数吗？压根没法用。

数学佬怂……

类似的推论还有：

证明更容易：

验证起来一点都不难，不在此处一一列举，朋友们可以代入2,3,5,7,11试试，再大就别试了，计算量实在不是人类干的。

反过来：

很遗憾，这个结论不如我们前面那个，这个猜想是错的，已经被数学家证明了。（偷偷告诉你，我不会证，也看不懂，丢人啊）反例至少有12000位！

想不想看看这个数学佬看不懂的证明长什么摸样？不是几百页啦，区区几行，抄录如下：