取数字 2，不断提高它的幂次。把每个结果除以 7，记下余数： 幂 $2^1$ $2^2$ $2^3$ $2^4$ $2^5$ $2^6$ 值 2 4 8 16 32 64 除以 7 的余数 2 4 1 2 4 1 到 $2^6$，余数是 1。再试试 3 和质数 5：$3^4=81$，除以 5 余 1。再试 10 和质数 13：$10^{12}=1\,000\,000\,000\,000$，除以 13 也余 1。 是巧合吗？不是。这就是费马小定理。 定理内容 如果 $p$ 是质数，$a$ 是不被 $p$ 整除的整数，那么 $a^{p-1}$ 除以 $p$ 余 1。用高斯 1801 年创立的同余记号写作： $$a^{p-1}\equiv1\pmod p.$$“小”字只是为了与大定理区分。实际上，小定理要有用得多。 底数 a： 质数 p： 235711131719232931 选择底数和一个质数。当底数是该质数的倍数时，指数为 p − 1 的版本的前提条件不成立。 请启用 JavaScript 以使用控件。例子和证明也在正文中。
数学家们一直梦想找到一个只产生质数的公式。1640 年，费马以为自己找到了。 连续五个质数 费马研究了如下形式的数： $$F_n=2^{2^n}+1.$$指数是 2 的幂：$1,2,4,8,16,\ldots$ 算出前几个： $$F_0=3,\quad F_1=5,\quad F_2=17,\quad F_3=257,\quad F_4=65\,537.$$五个都是质数。用手检验 $65\,537$（试除到它的平方根）已经相当费力了。费马写信给弗雷尼克·德贝西说，他确信所有这种形式的数都是质数，尽管他承认自己没有证明。 一个太大的数 下一个数是 $$F_5=2^{32}+1=4\,294\,967\,297.$$这是一个十位数。要检验它是不是质数，需要在 17 世纪用手试除到大约 6.5 万。费马没有去算。 将近一百年后的 1732 年，年轻的莱昂哈德·欧拉算了。他发现： $$4\,294\,967\,297=641\times6\,700\,417.$$费马的猜想错了。要推翻一个关于所有数的命题，一个反例就够了。 为什么是 641？ 欧拉并不是随便试除。他知道 $F_5$ 的因数必须具有特殊形式 $64k+1$，这大大缩小了搜索范围。这种形式的第五个质数候选就是 641。 还有一种不做除法就能验证整除的巧妙方法。注意 641 可以写成两种形式： $$641=5\cdot2^7+1=5^4+2^4.$$模 641 时，第一种形式说明 $5\cdot2^7$ 余 $-1$。两边四次方，$5^4\cdot2^{28}$ 余 $1$。第二种形式说明 $5^4$ 与 $-2^4$ 余数相同。互相替换： $$-2^4\cdot2^{28}=-2^{32}\equiv1\pmod{641}.$$所以 $2^{32}+1$ 余 0：它是 641 的倍数。完整的计算见欧拉专题。 请启用 JavaScript 以使用这个交互图形。完整的推理见正文。 至今只有五个质数 借助计算机，人们已经知道从 $F_5$ 到 $F_{32}$ 的所有费马数都是合数。除了前五个，没有人找到过其他的费马质数。如今许多数学家怀疑，真相与费马的猜想正好相反：也许只存在这五个。 意想不到的用途：正十七边形 自希腊时代起，人们就知道如何用尺规作出正三角形和正五边形。两千年来，没有人能作出另一个边数为质数的正多边形。