費馬小定理：

如果p是一個素數，而a是任何不能被p整除的整數，那麼p能除aᵖ⁻¹ - 1。

這個由皮埃爾·德·費馬在1640年發現的數字性質，本質上是說，取任意素數p和任意不能被該素數整除的數a，假設p = 7, a = 20。通過費馬小定理，我們發現：

我們不太關心這個計算結果的實際數字。這個定理告訴我們，我們不需要做任何計算就能知道一個整數必須由它得出。

介紹

在17世紀皮埃爾·德·費馬與世界各地數學家的許多通信中，與法國鑄币局官員伯納德·弗雷尼卡·德·貝西（1605-1675）的通信對數論影響最大。據說，德·貝西在法國以計算大數的天賦而聞名。

當他聽說費馬提出了一個尋找立方數的問題，這個立方數的因數加起來就是平方數，就像7³ (1 7 7²)= 20²一樣，貝西立即給出了四個不同的解，第二天又給出了六個。——節選，《初等數論》

德•貝西本人後來最為人所知的是他的著作《尋找等效于魔法格的正方形》（Finding the square equivalent of magic tables），這是他死後于1693年出版的一篇關于魔方格的專著，他在書中提供了880個4階的魔方格。魔方格是一個n × n的格子，格子裡填滿了不同的正整數，每個格子裡包含一個不同的整數，并且每一行、每一列和每對角線上的整數的和都是相同的。

作為數學家，費馬在很多方面都無法與貝西相提并論，但談到數論家，沒有一個同時代的人能挑戰費馬。費馬和貝西在17世紀中期的合作導緻了數論中一些最驚人的發現，包括數字1729的立方屬性。

然而，兩人最引人注目的通信是費馬在1640年10月18日的一封信中提出了後來被稱為費馬小定理的定理。

證明

将近一百年後的1736年，歐拉在聖彼得堡學院學報上發表了一篇題為《關于素數的某些定理的證明》的論文，成為第一個證明費馬小定理的人。然而，後來人們發現，萊布尼茨在1683年之前的某個時候，在一份未發表的手稿中給出了幾乎相同的證明，但歐拉不可能知道。

今天，這個定理的許多證明已經為人所知。證明一般依賴于兩種簡化，首先，假設a在0≤a≤p−1範圍内。第二，證明費馬小定理在1≤a≤p−1範圍内成立是充分的。

用二項式定理證明

歐拉的第一個證明是多項式定理的一個非常簡單的應用：

• 多項式定理

這個求和是通過kₐ得到的所有非負整數索引k₁的序列，這樣所有kᵢ的和就是n，如果我們把a表示為1的p次方的和(1 1 1 …1ₐ)ᵖ，我們得到：

如果p是質數，對于任意j，kⱼ不等于p，我們有：

如果p是質數，對于某個j，kⱼ=p，我們有：

因為正好有一個元素使kⱼ= p，所以定理成立。

作為歐拉定理的一個推論的證明

這個定理的另一個證明是，歐拉定理是費馬小定理的推廣。歐拉定理指出，若n，a為正整數，且n和a互質，則：

其中φ(n)是歐拉函數，它計算從1到n之間的素數。如果n是素數，則得出費馬小定理，即φ(n) = n−1。費馬小定理的證明可以從歐拉定理的證明中得到，歐拉定理的證明通常是用群論來完成的。

模算法證明

下面的證明，使用模運算，最初是由James Ivory在1806年發現的，後來被Dirichlet在1828年重新發現。

費馬小定理的證明

我們首先考慮整數a，2a，3a，…（p - 1）a。這些數都不等于p對其他數的模，也不等于0。如果這樣，那麼有：

r × a ≡ s × a （mod p），1 ≤ r < s ≤ p - 1

那麼，兩邊消去a将得到r≡s (mod p)，這是不可能的，因為r和s都在1和p - 1之間。因此，前一組整數必須同餘模p到1，2，…p - 1。把這些同餘相乘，你會發現：

a × 2a × 3a × ... × (p - 1) × a ≡ 1 × 2 × 3 × ... × (p - 1)(mod p)

意味着

aᵖ⁻¹ × （p - 1）! ≡ （p - 1）!（mod p）。

從這個表達式的兩邊消去（p - 1）!，我們得到：

aᵖ⁻¹ ≡ 1 (mod p)。

用群論證明

用群論證明費馬小定理，考慮到集合G ={1，2，…，p−1}用乘法運算形成一個群。在四個群公理中，唯一需要驗證的是第四個公理，即G中的元素是可逆的。想了解詳細 内容可以看這篇文章：由淺入深，輕松理解抽象代數的重要分支——群論

如果我們假設G中的每個元素都是可逆的，假設a在1≤a≤p−1的範圍内，也就是說，假設a是G的一個元素。設k是a的階數，即使aᵏ≡1 (mod p)為真時的最小正整數。然後數字1，a，a²，…，aᵏ⁻¹ 約模p，形成G的一個序為k的子群，根據拉格朗日定理，k能整除G的階數，即p−1。對于正整數m，有p−1 = km，并且：

為了證明G與p互質的每個元素b都是可逆的，這個恒等式可以幫助我們如下。因為b和p是素數，貝祖恒等式保證了有整數c和d使得bc pd = 1。對p取模，這意味着c是b的逆，因為bc≡1（mod p）。因為b是可逆的，所以G中的其他元素也是可逆的，所以G必須是一個群。

應用，素性測試

費馬小定理将成為費馬質數檢驗的基礎，這是一種确定一個數是否為質數的概率方法。例如，如果我們想知道n = 19是否為素數，随機取 1 < a < 19，假設a = 2。計算n−1 = 18，及其因子是9和6。我們通過計算2¹⁸ ≡ 1 （mod 19）， 2⁹ ≡ 18（mod 19）和 2⁶ ≡ 7 （mod 19）來檢驗，最後發現19必須是素數。

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部