费马小定理（数学定理）
2023-02-14 17:51:11未知 作者:无限魅力物联网
费马小定理（Fermat Theory）是数论中一个重要定理，内容为：假如p是质数，且，那么。即：假如是整数，是质数，且互质(即两者只有一个公约数1)，那么的次方除以的余数恒等于1。该定理是1636年皮埃尔·德·费马发现的。
中文名费马小定理
Fermat's little theorem
皮埃尔·德·费马
适用领域
数论
数学
发展简史
皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求，但是这个要求实际上是不必要的。[1]
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证明了卡迈克尔数有无穷多个。
定理定义
简称费马定理.初等数论的重要定理之一.该定理断言:若为素数,则.该定理是数论中欧拉定理的一个特殊情况,因为在欧拉定理中当是素数时[2],就得到费马定理。
验证推导
引理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
