跳至內容

費馬小定理

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

費馬小定理(英語:Fermat's little theorem)是數論中的一個定理。假如是一個整數是一個質數,那麼的倍數,可以表示為

如果不是倍數,這個定理也可以寫成更加常用的一種形式

[1][註 1]

註:如果倍數,則

費馬小定理的逆敘述不成立,即假如的倍數,不一定是一個質數。例如的倍數,但,不是質數。滿足費馬小定理的合數被稱為費馬偽質數

歷史

皮埃爾·德·費馬

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

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

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

卡邁克爾數

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

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

證明

方法一

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

換句話說,,考慮個數,將它們分別除以,餘數分別為,則集合為集合的重新排列,即在餘數中恰好各出現一次;這是因為對於任兩個相異而言(),其差不是的倍數(所以不會有相同餘數),且任一個亦不為的倍數(所以餘數不為0)。因此

在這裏,且,因此將整個公式除以即得到:

[3]
也即

(ii)若整除,則顯然有整除,即

方法二

為質數,為整數,且。考慮二項式系數,並限定不為,則由於分子有質數,但分母不含,故分子的能保留,不被約分而除去,即恆為的倍數[4]

再考慮的二項式展開,模,則

因此

,即得[3]

方法三

抽象代數教科書中,費馬小定理常作為教授拉格朗日定理時的一個簡單例子[5]。顯然只需考慮 情形。此時模 所有非零的餘數,在同餘意義下對乘法構成一個群,這個群的階是 。考慮群中的任何一個元素 ,根據拉格朗日定理, 的階必整除群的階。證畢。

應用

  • 計算除以13的餘數

故餘數為3。

  • 證明對於任意整數a而言,恆為2730的倍數。
    • 易由推得,其中為正整數。
    • 故對指數13操作如下: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的倍數。
  • 證明對於任意整數a而言,恆為3300的倍數。
證明
  • 為132的倍數。
    1. 模仿前述操作,11減1為10,10的正因數有1, 2, 5, 10,分別加1,為2, 3, 6, 11,其中2, 3, 11為質數,因此為2, 3, 11的最小公倍數的倍數,即66的倍數。
    2. 考慮,因為奇數的11次方仍為奇數,且奇數與奇數之和為偶數,故當a為奇數時,為偶數;同理可知當a為偶數時,仍為偶數。因此當a為任意整數時,為偶數。
    3. 因此的倍數的倍數的倍數。
  • 為25的倍數。
    • 由後文的歐拉定理可知(當a與25互質時),即(當a為任意整數時)。因此為25的倍數。
  • 因此為132與25的的最小公倍數的倍數,即3300的倍數。

推廣

歐拉定理

費馬小定理是歐拉定理的一個特殊情況:如果 ,那麼

這裏 歐拉函數。歐拉函數的值是所有小於或等於 的正整數中與 互質的數的個數。假如 是一個質數,則 ,即費馬小定理。

證明

上面證明費馬小定理的群論方法,可以同理地證明歐拉定理。

考慮所有與 互質的數,這些數模 的餘數所構成的集合,記為 ,並將群乘法定義為相乘後模 的同餘。顯然 是一個群,因為它對群乘法封閉(若 ),含單位元素(即「1」),且任何一個元素 的反元素也在集合中(因為若 則由群乘法封閉性任何 的冪次都在 中,所以 這個有限集的子集)。根據定義, 的階是 ,於是根據拉格朗日定理, 中任何一個元素的階必整除 。證畢。

卡邁克爾函數

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

多項式除法

因為

所以由的結果可以得出的結果

多項式除法可以得出除以的次數少於的餘式

例如,由多項式除法得到,則

這個餘式的一般結果是:

(除式)

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

註釋

  1. ^ 符號的應用請參見同餘模算數

參見

參考

  1. ^ Fermat's Little Theorem頁面存檔備份,存於互聯網檔案館).WolframMathWorld.(英文)
  2. ^ A proof of certain theorems regarding prime numbers. [2012-12-11]. (原始內容存檔於2015-06-16). 
  3. ^ 3.0 3.1 許介彥. 費馬小定理 (PDF). 科學教育月刊 (私立大葉大學電機工程學系). 2006年10月, (第293期): 37–44 [2015-04-18]. (原始內容 (PDF)存檔於2015-04-18). 
  4. ^ How is (x+y)^p≡x^p+y^p mod p for any prime number p. Mathematics Stack Exchange. 2018-09-27 [2021-04-26]. (原始內容存檔於2022-03-25) (英語). 
  5. ^ 聶靈沼; 丁石孫. 代数学引论 第二版. 北京: 高等教育出版社. 2000: 第33頁. ISBN 7-04-008893-2. 
  6. ^ 黃嘉威. 多项式除法解高次同余. 數學學習與研究. 2015, (9): 第104頁 [2015-07-19]. (原始內容存檔於2020-10-20).