跳至內容

費馬小定理

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

費馬小定理(英語: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).