费马小定理（数学定理）

费马小定理

数学定理

费马小定理（Fermat Theory）是数论中一个重要定理，内容为：假如p是质数，且，那么。即：假如是整数，是质数，且互质(即两者只有一个公约数1)，那么的次方除以的余数恒等于1。该定理是1636年皮埃尔·德·费马发现的。

发展简史

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

1736年，欧拉出版了一本名为“一些与素数有关的定理的证明”（拉丁文：Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio）的论文中第一次提出证明，但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。

有些学家独立制作相关的假说（有时也被错误地称为中国的假说），当成立时，是素数。这是费马小定理的一个特殊情况。然而，这一假说的前设是错的：例如，341，而341=11×31是一个伪素数。所有的伪素数都是此假说的反例。

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

更极端的反例是卡迈克尔数：假设与561互质，则560被561除都余1。这样的数被称为卡迈克尔数数，561是最小的卡迈克尔数。Korselt在1899年就给出了卡迈克尔数的等价定义，但直到1910年才由卡迈克尔（Robert Daniel Carmichael）发现第一个卡迈克尔数：561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡迈克尔数有无穷多个。

定理定义

简称费马定理.初等数论的重要定理之一.该定理断言:若为素数,则.该定理是数论中欧拉定理的一个特殊情况,因为在欧拉定理中当是素数时,就得到费马定理。

验证推导

引理1

若为任意3个整数为正整数，且，则当时，有。

证明：可得可得。因为即互质，可以约去，可得。

引理2

设是一个整数且是一个整数且。如果是模的一个完全剩余系，则也构成模的一个完全剩余系。

证明：若存在2个整数和同余即，根据引理1则有。根据完全剩余系的定义可知这是不可能的，因此不存在2个整数和同余。

所以构成模的一个完全剩余系。

构造素数的完全剩余系

因为，由引理2可得

也是的一个完全剩余系。由完全剩余系的性质，

即

易知，同余式两边可约去，得到

这样就证明了费马小定理。

定理意义

费马小定理是初等数论四大定理（威尔逊定理，欧拉定理（数论中的欧拉定理），中国剩余定理(又称孙子定理），费马小定理）之一，在初等数论中有着非常广泛和重要的应用。实际上，它是欧拉定理的一个特殊情况（即

Python程式码

>>> n =221

>>>a = 38

>>>pow(a ,n -1,n)

1

"""221 may be a prime number."""

import random

def isprime(n,k=128):

if n<2:

return False

for _ in range(k):

a = random.randrange(1,n)

if pow(a,n-1,n)!=1:

return False

return True

参考资料

1.·

2.·