费马小定理
數學定理
费马小定理(英語:Fermat's little theorem)是数论中的一个定理。假如是一个整数,是一个質数,那么是的倍数,可以表示为
如果不是的倍数,这个定理也可以写成更加常用的一种形式
費馬小定理的逆敘述不成立,即假如是的倍数,不一定是一个質数。例如是的倍数,但,不是質数。滿足費馬小定理的合數被稱為费马伪素数。
历史编辑
皮埃爾·德·費馬于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)。因此
即
在这里 ,且 ,因此将整个公式除以 即得到:
- [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的倍數。
推广编辑
欧拉定理编辑
费马小定理是欧拉定理的一个特殊情况:如果 ,那么
这里 是欧拉函数。欧拉函数的值是所有小于或等于 的正整数中与 互質的数的个数。假如 是一个素数,则 ,即费马小定理。
- 证明
上面证明费马小定理的群论方法,可以同理地证明欧拉定理。
考虑所有与 互素的数,这些数模 的余数所构成的集合,记为 ,并将群乘法定义为相乘后模 的同余。显然 是一个群,因为它对群乘法封闭(若 和 则 ),含幺元(即“1”),且任何一个元素 的逆元素也在集合中(因为若 则由群乘法封闭性任何 的幂次都在 中,所以 是 这个有限集的子集)。根据定义, 的阶是 ,于是根据拉格朗日定理, 中任何一个元素的阶必整除 。证毕。
卡邁克爾函數编辑
卡邁克爾函數比欧拉函数更小。费马小定理也是它的特殊情况。
多项式除法编辑
因為
所以由 的結果可以得出 的結果
用多項式除法可以得出 除以 的次數少於 的餘式
例如 ,由多項式除法得到 ,則
這個餘式的一般結果是:
(除式)
- 求
注释编辑
参见编辑
參考编辑
- ^ 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).