费马小定理(Fermat's little theorem)是数论中的一个重要定理，在1636年提出。如果p是一个质数，而整数a不是p的倍数，则有a^（p-1）≡1（mod p）。

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

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

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

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

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

若a，b，c为任意3个整数,m为正整数，且(m,c)=1，则当a·c≡b·c(mod m)时，有a≡b(mod m)。

证明：a·c≡b·c(mod m)可得ac–bc≡0(mod m)可得(a-b)·c≡0(mod m)。因为(m,c)=1即m,c互质，c可以约去，a– b≡0(mod m)可得a≡b(mod m)。

设m是一个整数且m>1，b是一个整数且(m,b)=1。如果a[1],a[2],a[3],a[4],…a[m]是模m的一个完全剩余系，则b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]也构成模m的一个完全剩余系。

证明：若存在2个整数b·a[i]和b·a[j]同余即b·a[i]≡b·a[j](mod m)..(i>=1 && j>=1)，根据引理1则有a[i]≡a[j](mod m)。根据完全剩余系的定义可知这是不可能的，因此不存在2个整数b·a[i]和b·a[j]同余。

所以b·a[1],b·a[2],b·a[3],b·a[4],…b·a[m]构成模m的一个完全剩余系。

构造素数 的完全剩余系

因为 ，由引理2可得

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

即

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

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

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

计算 除以13的余数

故余数为3。

证明对于任意整数而言，a13-a恒为2730的倍数。

由定理：a13-a为13的倍数，又a13-a=a(a12-1)=a[(a6)2-1]=a(a6+1)(a6-1)

所以a13-a为7的倍数，

同理：a13-a也为2的倍数、为3的倍数、为5的倍数。

因为2, 3, 5, 7, 13为质数，a13-a所以为2*3*5*7*13=2730的倍数。

>>> n =221

>>>a = 38

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

1

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