費馬小定理

費馬小定理

費馬小定理（Fermat's Little Theorem）是數論中的一個重要定理，由法國數學家皮埃爾·德·費馬在17世紀提出。該定理給出了關於質數與整數之間關係的基本性質，是現代密碼學（特別是RSA加密算法）的理論基礎之一。

費馬小定理的標準表述為：

若p是一個質數，且a是一個與p互質的整數（即gcd(a,p)=1），則有：

a^(p-1) ≡ 1 (mod p)

或者等價地表述為：

a^p ≡ a (mod p)

舉例說明費馬小定理的應用：

1. 令p=5（質數），a=2（與5互質）：2^(5-1) = 2^4 = 16 ≡ 1 (mod 5)

2. 令p=7（質數），a=3（與7互質）：3^(7-1) = 3^6 = 729 ≡ 1 (mod 7)，因為729-1=728=7×104

費馬小定理有多種證明方法，最常見的包括：

數學歸納法證明

1. 基礎步驟：驗證a=1時定理成立

2. 歸納步驟：假設定理對a=k成立，證明對a=k+1也成立

群論證明

利用模p乘法群的概念，因為該群的階為p-1，根據拉格朗日定理，任何元素的p-1次冪等於單位元。

組合證明

通過考慮a種顏色的珠子穿成長度為p的環狀項鍊的排列數，利用質數性質證明定理。

費馬小定理有以下重要推廣：

歐拉定理

歐拉將費馬小定理推廣到任意正整數n的情況：若a與n互質，則a^φ(n) ≡ 1 (mod n)，其中φ(n)是歐拉函數。

卡邁克爾定理

進一步推廣歐拉定理，定義卡邁克爾函數λ(n)為使a^m ≡ 1 (mod n)對所有與n互質的a成立的最小正整數m。

費馬小定理在現代數學和計算機科學中有廣泛應用：

1. 質數測試：用於費馬質數性檢驗，雖然存在偽質數限制。

2. 密碼學：RSA加密算法的核心理論基礎之一。

3. 計算數論：用於快速計算大數的模冪運算。

4. 編碼理論：在糾錯碼設計中有重要應用。

費馬在1640年10月18日給朋友Frénicle de Bessy的信中首次提出這個定理，但沒有給出證明。第一個已知的證明由萊布尼茨在1683年的一篇未發表手稿中給出，後來歐拉在1736年發表了第一個正式的證明。

1. 費馬小定理的逆定理不成立，即存在滿足a^(n-1) ≡ 1 (mod n)的合數n（稱為費馬偽質數）。

2. 定理要求a與p互質，否則結論不成立。例如p=5,a=10時，10^4=10000 ≡ 0 (mod 5) ≠ 1。

3. 費馬小定理與費馬最後定理是不同的定理，後者更為著名但內容完全不同。

與費馬小定理相關的重要數學概念包括：

• 模運算

• 歐拉函數

• 原根

• 離散對數

• 中國剩餘定理

費馬小定理作為初等數論的基石之一，其簡潔優美的形式與深遠的應用價值，使其成為數學史上最重要的發現之一。