費馬小定理

皮耶·德·費馬於1636年發現了這個定理。在一封1640年10月18日的信中他第一次使用了上面的書寫方式。在他的信中費馬還提出a是一個素數的要求，但是這個要求實際上是不必要的。

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

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

如上所述，中國猜測僅有一半是正確的。符合中國猜測但不是素數的數被稱為偽素數。

更極端的反例是卡邁克爾數： 假設a與561互質，則 a⁵⁶⁰被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)。 ^[2] 

設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的一個完全剩餘系。由完全剩餘系的性質，

即

易知

，同餘式兩邊可約去

，得到

這樣就證明了費馬小定理。 ^[3] 

費馬小定理是初等數論四大定理（威爾遜定理，歐拉定理（數論中的歐拉定理），中國剩餘定理(又稱孫子定理），費馬小定理）之一，在初等數論中有着非常廣泛和重要的應用。實際上，它是歐拉定理的一個特殊情況（即

，見於詞條“歐拉函數”。

計算

除以13的餘數

故餘數為3。

證明對於任意整數而言，a¹³-a恆為2730的倍數。

由定理：a¹³-a為13的倍數，又a¹³-a=a(a¹²-1)=a[(a⁶)²-1]=a(a⁶+1)(a⁶-1)

所以a¹³-a為7的倍數，

同理：a¹³-a也為2的倍數、為3的倍數、為5的倍數。

因為2, 3, 5, 7, 13為質數，a¹³-a所以為2*3*5*7*13=2730的倍數。

>>> 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