费马小定理

數學定理

费马小定理(英語:Fermat's little theorem)是数论中的一个定理。假如是一个整数是一个質数,那么的倍数,可以表示为

如果不是倍数,这个定理也可以写成更加常用的一种形式

[1][註 1]

費馬小定理的逆敘述不成立,即假如的倍数,不一定是一个質数。例如的倍数,但,不是質数。滿足費馬小定理的合數被稱為费马伪素数

历史编辑

 
皮埃爾·德·費馬

皮埃爾·德·費馬于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)若 是整数, 是质数,且 。若 不能整除 ,则 不能整除 。取整數集 为所有小於 的正整数集合 构成 的完全剩余系,即 中不存在两个数同余 ),  中所有的元素乘以 组成的集合。因为 中的任何两个元素之差都不能被 整除,所以B中的任何两个元素之差也不能被 整除。

換句話說, ,考慮  個數,將它們分別除以p,餘數分別為 ,則集合{r1,r2,r3,...,rp-1}為集合{1,2,3,...,(p-1)}的重新排列,即1,2,3,....,(p-1)在餘數中恰好各出現一次;這是因為對於任兩個相異k*a而言(k=1,2,3....(p-1)),其差不是p的倍數(所以不會有相同餘數),且任一個k*a亦不為p的倍數(所以餘數不為0)。因此

 

 

在这里W=1·2·3·...·(p-1),且(W, p) = 1,因此将整个公式除以W即得到:

 [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”),且任何一个元素   的逆元素也在集合中(因为若   则由群乘法封闭性任何  的幂次都在   中,所以    这个有限集的子集)。根据定义,   的阶是  ,于是根据拉格朗日定理,   中任何一个元素的阶必整除  。证毕。

卡邁克爾函數编辑

卡邁克爾函數比欧拉函数更小。费马小定理也是它的特殊情况。

 

多项式除法编辑

因為 

所以由 的結果可以得出 的結果

多項式除法可以得出 除以 的次數少於 的餘式

例如 ,由多項式除法得到 ,則 

這個餘式的一般結果是:

 (除式)

 

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).