費馬小定理

維基百科,自由的百科全書
前往: 導覽搜尋

費馬小定理數論中的一個定理:假如a是一個整數p是一個質數,那麼是p的倍數,可以表示為

如果a不是p的倍數,這個定理也可以寫成

[1]

這個書寫方式更加常用。(符號的應用請參見同餘。)

歷史[編輯]

皮埃爾·德·費馬

皮埃爾·德·費馬於1636年發現了這個定理。在一封1640年10月18日的信中他第一次使用了上面的書寫方式。在他的信中費馬還提出a是一個素數(質數)的要求。

1736年,歐拉出版了一本名為「一些與素數(質數)有關的定理的證明」(拉丁文:Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio)」[2]的論文集,其中第一次給出了證明。但從萊布尼茨未發表的手稿中發現他在1683年以前已經得到幾乎是相同的證明。

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

卡邁克爾數[編輯]

所述,中國猜測僅有一半是正確的。符合中國猜測但不是素數(質數)的數被稱為偽素數(質數)。

更極端的反例是卡邁克爾數: 假設與561互質,則被561除都餘1。這樣的數被稱為卡邁克爾數,561是最小的卡邁克爾數。Korselt在1899年就給出了卡邁克爾數的等價定義,但直到1910年才由卡邁克爾(Robert Daniel Carmichael)發現第一個卡邁克爾數:561。1994年William Alford、Andrew Granville及Carl Pomerance證明了卡邁克爾數有無窮多個。

證明[編輯]

方法一[編輯]

若n不能整除,則n也不能整除。取整數集為所有小於構成的完全剩餘系,即中不存在兩個數同餘),中所有的元素乘以a組成的集合。因為中的任何兩個元素之差都不能被p整除,所以B中的任何兩個元素之差也不能被p整除。

換句話說,,考慮個數,將它們分別除以p,餘數分別為,則集合{r1,r2,r3,...,rp-1}為集合{1,2,3,...,(p-1)}的重新排列,即1,2,3,....,(p-1)在餘數中恰好各出現一次;這是因為對於任兩個相異k*a而言(k=1,2,3....(p-1)),其差不是p的倍數(所以不會有相同餘數),且任一個k*a亦不為p的倍數(所以餘數不為0)。因此

在這裡W=1·2·3·...·(p-1),且(W, p) = 1,因此將整個公式除以W即得到:

[3]

方法二[編輯]

考慮二項式係數,n不為p或0,由於分子有質數p,但分母不含p,故分子的p能保留,不被約分而除去,即恆為p的倍數。

再考慮(b+1)p的二項式展開,模p,則

因此

令b=a-1,即得[3]

應用[編輯]

  • 計算除以13的餘數

故餘數為3。

  • 證明對於任意整數a而言,恆為2730的倍數。13減1為12,12的正因數有1, 2, 3, 4, 6, 12,分別加1,為2, 3, 4, 5, 7, 13,其中2, 3, 5, 7, 13為質數,根據定理,為2的倍數、為3的倍數、為5的倍數、為7的倍數、為13的倍數,即2*3*5*7*13=2730的倍數。

推廣[編輯]

歐拉定理[編輯]

費馬小定理是歐拉定理的一個特殊情況:如果na的最大公因數是1,那麼

這裡φ(n)是歐拉函數。歐拉函數的值是所有小於或等於n的正整數中與n互質的數的個數。假如n是一個素數(質數),則φ(n) = n-1,即費馬小定理。

卡邁克爾函數[編輯]

卡邁克爾函數比歐拉函數更小。費馬小定理也是它的特殊情況。

多項式除法[編輯]

除式:

餘式:

n=0時為除式,用數學歸納法證明餘式。[4]

Python程式碼[編輯]

 1 >>> n =221
 2 >>>a = 38
 3 >>>pow(a ,n -1,n)
 4 1
 5 
 6 """221 may be a prime number."""
 7 
 8 import random
 9 def isprime(n,k=128):
10     if n<2:
11         return False
12     for _ in range(k):
13         a = random.randrange(1,n)
14         if pow(a,n-1,n)!=1:
15             return False
16     return True

參見[編輯]

參考[編輯]

  1. ^ Fermat's Little Theorem.WolframMathWorld.(英文)
  2. ^ A proof of certain theorems regarding prime numbers
  3. ^ 3.0 3.1 許介彥. 費馬小定理 (PDF). 科學教育月刊 (私立大葉大學電機工程學系). 2006年10月, (第293期): 37–44. (原始內容 (PDF)存檔於2015-04-18). 
  4. ^ 黃嘉威. 多項式除法解高次同餘. 數學學習與研究. 2015, (9): 第104頁.