费马小定理

跳转到：导航, 搜索

费马小定理是数论中的一个定理：假如a是一个整数，p是一个素数，那么

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

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

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

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

[编辑] 历史

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

与费马小定理相关的有一个猜想。这个猜想是中国数学家提出来的。其内容为：当且仅当2^p = 2(mod p)成立时p是一个素数。

也就是说，如果p是一个素数的话，则2^p = 2(mod p)成立（这是费马小定理的一个特殊情况）。这个结论是对的。但反过来，假如2^p = 2(mod p)成立则p是一个素数的结论是错的（例如，341符合上述条件，但它不是一个素数：341=11x31。）。因此，整个说来，这个猜想是不成立的。

一般认为，中国数学家比费马大约早2000年左右就已经知道中国猜想了。但也有人认为，实际上这个中国猜想是于1872年提出的。

若n不能整除a - b，x>0，(x,n)=1，則n也能不整除x(a-b)。取整數A为所有小於p的集（p不能整除A），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，即费马小定理。

在费马小定理的基础上，费马提出了一种测试素数的算法；尽管它并不实用。

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

如果所有符合1 < b < p的b p都满足下列条件的话：

$b^{p} \equiv b \mod p$

则p必定是一个素数。

实际上，没有必要测试所有的小于p的自然数，而仅需测试所有的小于p的素数即可。

这个算法的缺点是运算速度非常慢。