費馬小定理(英語:Fermat's little theorem)是數論中的一個定理。假如
是一個整數,
是一個質數,那麼
是
的倍數,可以表示為
![{\displaystyle a^{p}\equiv a{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ff656f721894b9a50a2b1d18538463a6a4ec15f)
如果
不是
的倍數,這個定理也可以寫成更加常用的一種形式
[1][註 1]
註:如果
是
的倍數,則
![{\displaystyle a^{p-1}\equiv 0{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c34a977d62179acf61c6935a2ec6e07ffd669f5)
費馬小定理的逆敘述不成立,即假如
是
的倍數,
不一定是一個質數。例如
是
的倍數,但
,不是質數。滿足費馬小定理的合數被稱為費馬偽質數。
歷史
皮埃爾·德·費馬
皮埃爾·德·費馬於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證明了卡邁克爾數有無窮多個。
證明
方法一
(i)若
是整數,
是質數,且
。若
不能整除
,則
不能整除
。取整數集
為所有小於
的正整數集合(
構成
的完全剩餘系,即
中不存在兩個數同餘
),
是
中所有的元素乘以
組成的集合。因為
中的任何兩個元素之差都不能被
整除,所以
中的任何兩個元素之差也不能被
整除。
換句話說,
,考慮
共
個數,將它們分別除以
,餘數分別為
,則集合
為集合
的重新排列,即
在餘數中恰好各出現一次;這是因為對於任兩個相異
而言(
),其差不是
的倍數(所以不會有相同餘數),且任一個
亦不為
的倍數(所以餘數不為0)。因此
![{\displaystyle 1\cdot 2\cdot 3\cdot \dots \cdot (p-1)\equiv (1\cdot a)\cdot (2\cdot a)\cdot \dots \cdot ((p-1)\cdot a){\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dfbb68e559cc60d5ee0f7519544472d06b2224ba)
即
![{\displaystyle W\equiv W\cdot a^{p-1}{\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be677beeb9026d6c3ecde22c1abcd1d0cfec5308)
在這裏
,且
,因此將整個公式除以
即得到:
[3]
- 也即
![{\displaystyle a^{p}\equiv a{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ff656f721894b9a50a2b1d18538463a6a4ec15f)
(ii)若
整除
,則顯然有
整除
,即
。
方法二
若
為質數,
為整數,且
。考慮二項式系數
,並限定
不為
或
,則由於分子有質數
,但分母不含
,故分子的
能保留,不被約分而除去,即
恆為
的倍數[4]。
再考慮
的二項式展開,模
,則
![{\displaystyle (b+1)^{p}\equiv {\dbinom {p}{p}}b^{p}+{\dbinom {p}{p-1}}b^{p-1}+{\dbinom {p}{p-2}}b^{p-2}+\dots +{\dbinom {p}{2}}b^{2}+{\dbinom {p}{1}}b^{1}+{\dbinom {p}{0}}b^{0}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6ac8532934492357eadfe3c236cf777c8fa3754)
![{\displaystyle \equiv {\dbinom {p}{p}}b^{p}+{\dbinom {p}{0}}b^{0}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c4a9ddcad074ce4a393fcc177f3f4242538b680)
![{\displaystyle \equiv b^{p}+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ec6f74cdd9a357b60669629e1fb7bc5fb94bd52)
因此
![{\displaystyle (b+1)^{p}\equiv b^{p}+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a31482c11fab2e81e2594d81496bf86ef35443c7)
![{\displaystyle \equiv (b-1)^{p}+1+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/404c1d92ff2d3ed99878070d7b32fcea16e1300d)
![{\displaystyle \equiv (b-2)^{p}+1+1+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38fb1f386fc0658b396c378c92263d27830652b2)
![{\displaystyle \equiv (b-3)^{p}+1+1+1+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d526ae063c7a09ab1cd51e30d612e0af70504b4)
![{\displaystyle \dots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/5411a9d9722322917df8faecb6e01b72e3ecede4)
![{\displaystyle \equiv {\begin{matrix}\underbrace {1+1+\dots +1+1} \\b+1\end{matrix}}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7717984d57085b276b171b2d9401ae787933a6fc)
![{\displaystyle \equiv b+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/822bb0f8e64619037bec9d816800c78621a156b8)
令
,即得
。[3]
方法三
在抽象代數教科書中,費馬小定理常作為教授拉格朗日定理時的一個簡單例子[5]。顯然只需考慮
情形。此時模
所有非零的餘數,在同餘意義下對乘法構成一個群,這個群的階是
。考慮群中的任何一個元素
,根據拉格朗日定理,
的階必整除群的階。證畢。
應用
- 計算
除以13的餘數
![{\displaystyle 2^{100}\equiv 2^{12\times 8+4}{\pmod {13}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3190d6a070f03e1042e4496b32bb80059682c99e)
![{\displaystyle \equiv (2^{12})^{8}\cdot 2^{4}{\pmod {13}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d2350fd981e412bb55c1a31ee553f0c4d721218)
![{\displaystyle \equiv 1^{8}\cdot 16{\pmod {13}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/780be17c9a2750122321487d8c8ebbf4dacfc740)
![{\displaystyle \equiv 16{\pmod {13}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9598173429d851e085c58566885ea6de6239afd3)
![{\displaystyle \equiv 3{\pmod {13}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75da65577ca8c5dfeda46defe1b607dd9bd8739a)
故餘數為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的倍數。
- 模仿前述操作,11減1為10,10的正因數有1, 2, 5, 10,分別加1,為2, 3, 6, 11,其中2, 3, 11為質數,因此
為2, 3, 11的最小公倍數的倍數,即66的倍數。
- 考慮
,因為奇數的11次方仍為奇數,且奇數與奇數之和為偶數,故當a為奇數時,
為偶數;同理可知當a為偶數時,
仍為偶數。因此當a為任意整數時,
為偶數。
- 因此
的倍數
的倍數
的倍數。
為25的倍數。
- 由後文的歐拉定理可知
(當a與25互質時),即
(當a為任意整數時)。因此
為25的倍數。
- 因此
為132與25的的最小公倍數的倍數,即3300的倍數。
推廣
歐拉定理
費馬小定理是歐拉定理的一個特殊情況:如果
,那麼
![{\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e818f3f88d3e71e569f171dd86f31e1903fdc55)
這裏
是歐拉函數。歐拉函數的值是所有小於或等於
的正整數中與
互質的數的個數。假如
是一個質數,則
,即費馬小定理。
- 證明
上面證明費馬小定理的群論方法,可以同理地證明歐拉定理。
考慮所有與
互質的數,這些數模
的餘數所構成的集合,記為
,並將群乘法定義為相乘後模
的同餘。顯然
是一個群,因為它對群乘法封閉(若
和
則
),含單位元素(即「1」),且任何一個元素
的反元素也在集合中(因為若
則由群乘法封閉性任何
的冪次都在
中,所以
是
這個有限集的子集)。根據定義,
的階是
,於是根據拉格朗日定理,
中任何一個元素的階必整除
。證畢。
卡邁克爾函數
卡邁克爾函數比歐拉函數更小。費馬小定理也是它的特殊情況。
![{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e475506bcb72caae57599e0ccafa7efe023be9c)
多項式除法
因為
所以由
的結果可以得出
的結果
用多項式除法可以得出
除以
的次數少於
的餘式
例如
,由多項式除法得到
,則
這個餘式的一般結果是:
(除式)
n=0時為除式,用數學歸納法證明餘式。[6]
- 求
![{\displaystyle x^{1000}{\pmod {5^{2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e44c3e08ec5f102bad983edfb5da19d1de7c527a)
註釋
參見
參考
- ^ Fermat's Little Theorem (頁面存檔備份,存於互聯網檔案館).WolframMathWorld.(英文)
- ^ A proof of certain theorems regarding prime numbers. [2012-12-11]. (原始內容存檔於2015-06-16).
- ^ 3.0 3.1 許介彥. 費馬小定理 (PDF). 科學教育月刊 (私立大葉大學電機工程學系). 2006年10月, (第293期): 37–44 [2015-04-18]. (原始內容 (PDF)存檔於2015-04-18).
- ^ 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) (英語).
- ^ 聶靈沼; 丁石孫. 代数学引论 第二版. 北京: 高等教育出版社. 2000: 第33頁. ISBN 7-04-008893-2.
- ^ 黃嘉威. 多项式除法解高次同余. 數學學習與研究. 2015, (9): 第104頁 [2015-07-19]. (原始內容存檔於2020-10-20).