费马小定理

费马小定理是数论中的一个定理：假如a是一个整数，p是一个質数，那么$a^p - a$是p的倍数，可以表示为

$a^p \equiv a \pmod{p}$

如果a不是p的倍数，这个定理也可以写成

$a^{p-1} \equiv 1 \pmod{p}$

这个书写方式更加常用。（符号的应用请参见同餘。）

历史

皮埃爾·德·費馬于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求。

1736年，歐拉出版了一本名為“一些與素數有關的定理的證明”(拉丁文：Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio)”的論文中第一次提出證明，但從萊布尼茨未發表的手稿中發現他在1683年以前已經得到幾乎是相同的證明。

有些數學家獨立製作相關的假說（有時也被錯誤地稱為中國的假說），當$2^{p} \equiv 2 \pmod{p}$成立時，p是素數。這是費馬小定理的一個特殊情況。然而，這一假說的前設是錯的：例如，$2^{341} \equiv 2 \pmod{341}$341 ，而341= 11×31是一個偽素數。所有的偽素數都是此假說的反例。

证明

若n不能整除a - b，x>0，(x,n)=1，則n也不能整除x(a-b)。取整數集A为所有小於p的集（A构成p的完全剩余系,即A中不存在两个数同余p），B是A中所有的元素乘以a组成的集合。因为A中的任何两个元素之差都不能被p整除，所以B中的任何两个元素之差也不能被p整除。因此

$1 \cdot 2 \cdot 3 \cdot \dots \cdot (p-1) \equiv (1 \cdot a)\cdot(2 \cdot a)\cdot\dots\cdot ((p-1) \cdot a) \pmod{ p},$

即

$W \equiv W\cdot a^{p-1} \pmod{p},$

在这里W=1·2·3·...·(p-1)，且(W, p) = 1，因此将整个公式除以W即得到：

$a^{p-1} \equiv 1 \pmod{p}$

广义

费马小定理是欧拉定理的一个特殊情况：如果n和a的最大公约数是1，那么

$a^{\varphi (n)} \equiv 1 \pmod{n}$

这里φ(n)是欧拉商数。欧拉商数的值是所有小于n的自然数中与n没有公约数的数的个数。假如n是一个素数，则φ(n) = n-1，即费马小定理。

在费马小定理的基础上，费马提出了一种测试素数的算法；尽管它是錯誤。

卡邁克爾數

如上所述，中国猜测仅有一半是正确的。符合中国猜测但不是素数的数被称为伪素数。

更极端的反例是卡邁克爾数：

假設a與561互质，則a^560被561除都余1。这样的数被称为卡邁克爾數数，561是最小的卡邁克爾数。Korselt在1899年就给出了卡邁克爾數的等价定义，但直到1910年才由卡邁克爾(Robert Daniel Carmichael)发现第一个卡邁克爾数:561。1994年William Alford 、 Andrew Granville 及 Carl Pomerance证明了卡邁克爾数有无穷多个。

外部链接

• 神奇的费马小定理——从实验、观察、发现到猜想和证明

参见

• 费马大定理