查看“︁费马小定理”︁的源代码

{{noteTA
|G1=math
}}
'''费马小定理'''（{{lang-en|Fermat's little theorem}}）是[[数论]]中的一个定理。假如<math>a</math>是一个[[整数]]，<math>p</math>是一个[[質数]]，那么<math>a^p - a </math>是<math>p</math>的倍数，可以表示为

:<math>a^p \equiv a \pmod{p}</math>

如果<math>a</math>不是<math>p</math>的[[倍数]]，這個定理也可以寫成更加常用的一種形式
:<math>a^{p-1} \equiv  1 \pmod{p}</math><ref>[http://mathworld.wolfram.com/FermatsLittleTheorem.html Fermat's Little Theorem] {{Wayback|url=http://mathworld.wolfram.com/FermatsLittleTheorem.html |date=20210507011105 }}.WolframMathWorld.{{en}}</ref>{{notetag|符号的应用请参见[[同餘]]和[[模算数]]。}}

註：如果<math>a</math>是<math>p</math>的[[倍数]]，則
:<math>a^{p-1} \equiv  0 \pmod{p}</math>

費馬小定理的逆敘述不成立，即假如<math>a^p - a </math>是<math>p</math>的倍数，<math>p</math>不一定是一个[[質数]]。例如<math>2^{341}-2</math>是<math>341</math>的倍数，但<math>341=11 \times 31</math>，不是[[質数]]。滿足費馬小定理的合數被稱為[[费马伪素数]]。

== 历史 ==
[[File:Pierre de Fermat.jpg|thumb|皮埃爾·德·費馬]]
[[皮埃爾·德·費馬]]于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求。

1736年，[[歐拉]]出版了一本名為“一些與素數有關的定理的證明”（拉丁文：Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio）”<ref>{{Cite web |url=http://www.math.dartmouth.edu/~euler/pages/E054.html |title=A proof of certain theorems regarding prime numbers  |access-date=2012-12-11 |archive-date=2015-06-16 |archive-url=https://web.archive.org/web/20150616005642/https://math.dartmouth.edu/~euler/pages/E054.html |dead-url=no }}</ref>的論文集，其中第一次给出了證明。但從[[萊布尼茨]]未發表的手稿中發現他在1683年以前已經得到幾乎是相同的證明。

{{anchor|中國猜想}}
有些數學家獨立提出相關的假說（有時也被錯誤地稱為[[中國猜想]]），當<math>2^{p} \equiv 2 \pmod{p}</math>成立時，p是質數。這是費馬小定理的一個特殊情況。然而，這一假說的前設是錯的：例如，<math>2^{341} \equiv 2 \pmod{341}</math>，而<math>341 = 11 \times 31</math>是一個[[偽素數]]。所有的偽素數都是此假說的反例。

===卡邁克爾數===
{{main|卡邁克爾數}}
如[[#中國猜想|上]]所述，中國猜想仅有一半是正确的。符合中國猜想但不是素数的数被称为伪素数。

更极端的反例是卡迈克尔数：
假設<math>a</math>與561互质，則<math>a^{560}</math>被561除都余1。这样的数被称为卡邁克爾數，561是最小的卡邁克爾数。Korselt在1899年就给出了卡邁克爾數的等价定义，但直到1910年才由[[羅伯特·丹尼·卡邁克爾|卡邁克爾]]（Robert Daniel Carmichael）发现第一个卡邁克爾数：561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡邁克爾数有无穷多个。

== 证明 ==
===方法一===
（i）若<math>a</math>是整数，<math>p</math>是质数，且<math>\gcd(a,p)=1</math>。若<math>p</math>不能整除<math>x-y</math>，则<math>p</math>不能整除<math>a(x-y)</math>。取整數集<math>A</math>为所有小於<math>p</math>的正整数[[集合 (数学)|集合]]（<math>A</math>构成<math>p</math>的完全剩余系，即<math>A</math>中不存在两个数同余<math>p</math>），<math>B</math>是<math>A</math>中所有的元素乘以<math>a</math>组成的集合。因为<math>A</math>中的任何两个元素之差都不能被<math>p</math>整除，所以<math>B</math>中的任何两个元素之差也不能被<math>p</math>整除。

換句話說，<math>\gcd(a,p)=1</math>，考慮<math>1\times a, 2\times a, 3\times a,....(p-1)\times a</math>共<math>(p-1)</math>個數，將它們分別除以<math>p</math>，餘數分別為<math>r_1,r_2,r_3,....,r_{p-1}</math>，則集合<math>\{r_1,r_2,r_3,....,r_{p-1}\}</math>為集合<math>\{ 1,2,3,\ldots,(p-1) \}</math>的重新排列，即<math>1,2,3,\ldots,(p-1) </math>在餘數中恰好各出現一次；這是因為對於任兩個相異<math>k*a</math>而言（<math>k=1,2,3,\ldots,(p-1) </math>），其差不是<math>p</math>的倍數（所以不會有相同餘數），且任一個<math>k*a</math>亦不為<math>p</math>的倍數（所以餘數不為0）。因此
:<math>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},</math> 
即 
:<math>W \equiv W\cdot a^{p-1} \pmod{p},</math> 
    
在这里<math>W=1\cdot 2\cdot 3\cdot \ldots\cdot (p-1)</math>，且<math>(W,p)=1</math>，因此将整个公式除以<math>W</math>即得到： 
    
:<math>a^{p-1} \equiv 1 \pmod{p}</math><ref name="大葉大學">{{cite journal|author=許介彥|title=費馬小定理|journal=科學教育月刊|issue=第293期|pages=37-44|publisher=私立大葉大學電機工程學系|url=http://www.sec.ntnu.edu.tw/Monthly/95(286-295)/293-pdf/04.pdf|archiveurl=https://web.archive.org/web/20150418111336/http://www.sec.ntnu.edu.tw/Monthly/95%28286-295%29/293-pdf/04.pdf|archivedate=2015-04-18|date=2006年10月|deadurl=yes|access-date=2015-04-18}}</ref> 
:也即 <math>a^p \equiv a \pmod{p}</math>
（ii）若<math>p</math>整除<math>a</math>，则显然有<math>p</math>整除<math>a^{p}</math>，即<math>a^p \equiv a\equiv 0 \pmod{p}</math>。

===方法二===
{{seealso|中一新生之夢}}
若<math>p</math>为质数，<math>n</math>为整数，且<math>p\geq n</math>。考慮[[二項式係數]]<math>\tbinom{p}{n}=\tfrac{p!}{n!(p-n)!}</math>，並限定<math>n</math>不為<math>p</math>或<math>0</math>，則由於分子有質數<math>p</math>，但分母不含<math>p</math>，故分子的<math>p</math>能保留，不被約分而除去，即<math>\tbinom{p}{n}</math>恆為<math>p</math>的倍數<ref>{{Cite web|title=How is (x+y)^p≡x^p+y^p mod p for any prime number p|url=https://math.stackexchange.com/questions/2932541/how-is-xyp-equiv-xp-yp-mod-p-for-any-prime-number-p|accessdate=2021-04-26|author=|date=2018-09-27|work=Mathematics Stack Exchange|language=en|archive-date=2022-03-25|archive-url=https://web.archive.org/web/20220325061225/https://math.stackexchange.com/questions/2932541/how-is-xyp-equiv-xp-yp-mod-p-for-any-prime-number-p}}</ref>。

再考慮<math>(b+1)^p</math>的二項式展開，模<math>p</math>，則
:<math>(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}</math>
:<math>\equiv \dbinom{p}{p}b^p+ \dbinom{p}{0}b^0 \pmod{p}</math>
:<math>\equiv b^p+1 \pmod{p}</math>

因此
:<math>(b+1)^p \equiv b^p+1 \pmod{p}</math>
:<math>\equiv (b-1)^p+1+1 \pmod{p}</math>
:<math>\equiv (b-2)^p+1+1+1 \pmod{p}</math>
:<math>\equiv (b-3)^p+1+1+1+1 \pmod{p}</math>
:<math>\dots</math>
:<math>\equiv \begin{matrix} \underbrace{1+1+\dots+1+1 } \\ b+1 \end{matrix} \pmod{p}</math>
:<math>\equiv b+1 \pmod{p}</math>
令<math>a=b+1</math>，即得<math>a^p \equiv a \pmod{p}</math>。<ref name="大葉大學"/>

===方法三===

在[[抽象代数]]教科书中，费马小定理常作为教授拉格朗日定理时的一个简单例子<ref>{{cite book |author1=聂灵沼 |author2=丁石孙 |title=代数学引论 |date=2000 |publisher=高等教育出版社 |location=北京 |isbn=7-04-008893-2 |page=第33页 |edition=第二版 |accessdate=2020-06-07}}</ref>。显然只需考虑 <math>(a,p)=1</math> 情形。此时模 <math>p</math> 所有非零的余数，在同余意义下对乘法构成一个群，这个群的阶是 <math>p-1</math>。考虑群中的任何一个元素 <math>b</math>，根据拉格朗日定理，<math>b</math> 的阶必整除群的阶。证毕。

==應用==
*計算<math>2^{100}</math>除以13的餘數
:<math>2^{100} \equiv 2^{12 \times 8+4} \pmod{13}</math>
:<math>\equiv (2^{12})^8 \cdot  2^4 \pmod{13}</math>
:<math>\equiv 1^8 \cdot  16 \pmod{13}</math>
:<math>\equiv 16 \pmod{13}</math>
:<math>\equiv 3 \pmod{13}</math>
故餘數為3。

*證明對於任意整數a而言，<math>a^{13}-a</math>恆為2730的倍數。
**易由<math>a^{p-1} \equiv  1 \pmod{p}</math>推得<math>a^{n(p-1)+1} \equiv 1^n \cdot a \equiv a \pmod{p}</math>，其中<math>n</math>為正整數。
**故對指數13操作如下：13減1為12，12的正因數有1, 2, 3, 4, 6, 12，分別加1，為2, 3, 4, 5, 7, 13，其中2, 3, 5, 7, 13為質數，根據定理的延伸表達式，<math>a^{13}-a</math>為2的倍數、為3的倍數、為5的倍數、為7的倍數、為13的倍數，即2*3*5*7*13=2730的倍數。

*證明對於任意整數a而言，<math>a^{22}-a^{2}</math>恆為3300的倍數。
{{hideH|證明}}
*<math>a^{22}-a^2</math>為132的倍數。
*#模仿前述操作，11減1為10，10的正因數有1, 2, 5, 10，分別加1，為2, 3, 6, 11，其中2, 3, 11為質數，因此<math>a^{11}-a</math>為2, 3, 11的最小公倍數的倍數，即66的倍數。
*#考慮<math>a^{11}+a</math>，因為奇數的11次方仍為奇數，且奇數與奇數之和為偶數，故當a為奇數時，<math>a^{11}+a</math>為偶數；同理可知當a為偶數時，<math>a^{11}+a</math>仍為偶數。因此當a為任意整數時，<math>a^{11}+a</math>為偶數。
*#因此<math>a^{22}-a^2=(a^{11}-a)(a^{11}+a)=66</math>的倍數<math> \times 2</math>的倍數<math>=132</math>的倍數。
*<math>a^{22}-a^2</math>為25的倍數。
**由後文的[[欧拉定理 (数论)|欧拉定理]]可知<math>a^{20} \equiv 1 \pmod {25}</math>（當a與25互質時），即<math>a^{21} \equiv a \pmod {25}</math>（當a為任意整數時）。因此<math>a^{22}-a^2=a(a^{21}-a)</math>為25的倍數。
*因此<math>a^{22}-a^2</math>為132與25的的最小公倍數的倍數，即3300的倍數。
{{hideF}}

==推广==
===欧拉定理===
费马小定理是[[欧拉定理 (数论)|欧拉定理]]的一个特殊情况：如果 <math>(a,n)=1</math> ，那么
:<math>a^{\varphi (n)} \equiv 1 \pmod{n}</math>
这里 <math>\varphi(n)</math> 是[[欧拉函数]]。欧拉函数的值是所有小于或等于 <math>n</math> 的正整数中与 <math>n</math> [[互質]]的数的个数。假如 <math>n</math> 是一个素数，则 <math>\varphi(n)=n-1</math> ，即费马小定理。

;证明
上面证明费马小定理的群论方法，可以同理地证明欧拉定理。

考虑所有与 <math>n</math> 互素的数，这些数模 <math>n</math> 的余数所构成的集合，记为 <math>{\cal S}</math>，并将群乘法定义为相乘后模 <math>n</math> 的同余。显然 <math>{\cal S}</math> 是一个群，因为它对群乘法封闭（若 <math>(a,n)=1</math> 和 <math>(b,n)=1</math> 则 <math>(ab,n)=1</math>），含幺元（即“1”），且任何一个元素 <math>a</math> 的逆元素也在集合中（因为若 <math>a\in{\cal S}</math> 则由群乘法封闭性任何<math>a</math> 的幂次都在 <math>{\cal S}</math> 中，所以 <math>\langle a\rangle</math> 是 <math>{\cal S}</math> 这个有限集的子集）。根据定义， <math>{\cal S}</math> 的阶是 <math>\varphi(n)</math>，于是根据拉格朗日定理， <math>{\cal S}</math> 中任何一个元素的阶必整除 <math>\varphi(n)</math>。证毕。

===卡邁克爾函數===
{{main|卡邁克爾函數}}
卡邁克爾函數比欧拉函数更小。费马小定理也是它的特殊情况。
:<math>a^{\lambda (n)} \equiv 1 \pmod{n}</math>

===多项式除法===
因為<math>p|x^p-x \Rightarrow p^k|(x^p-x)^k</math>

所以由<math>x^N\pmod{(x^p-x)^k}</math>的結果可以得出<math>x^N\pmod{p^k}</math>的結果

用[[多項式除法]]可以得出<math>x^N</math>除以<math>(x^p-x)^k</math>的次數少於<math>p^k</math>的餘式

例如<math>3 \mid x^3-x</math>，由多項式除法得到<math>x^5=(x^2+1)(x^3-x)+x</math>，則<math>x^5\equiv x\pmod{3}</math>

這個餘式的一般結果是：

<math>\displaystyle x^{pk} \equiv \sum_{i=1}^k(-1)^{i-1} \binom{k}{i} x^{pk-(p-1)i} \pmod {p^k}</math>（除式）

<math>\displaystyle x^{pk+(p-1)n} \equiv \sum_{i=1}^k(-1)^{i-1} \binom{n+i-1}{i-1} \binom{n+k}{k-i} x^{pk-(p-1)i} \pmod {p^k}</math>

n=0时为除式，用[[数学归纳法]]证明余式。<ref>{{cite journal|author=黄嘉威|year=2015|title=多项式除法解高次同余|journal=数学学习与研究|issue=9|pages=第104页|url=http://www.cnki.com.cn/Article/CJFDTOTAL-SXYG201509084.htm|access-date=2015-07-19|archive-date=2020-10-20|archive-url=https://web.archive.org/web/20201020225326/http://www.cnki.com.cn/Article/CJFDTOTAL-SXYG201509084.htm|dead-url=no}}</ref>

:求<math>x^{1000}\pmod{5^2}</math>

<math>x^{10+4n} \equiv(n+2)x^6 -(n+1)x^2 \pmod {5^2}</math>

<math>x^{1000} \equiv 249x^8 -248x^4 \equiv 24x^8 -23x^4 \pmod{5^2}</math>

==注释==
{{notefoot}}

== 参见 ==
*[[费马大定理]]
*[[拉格朗日定理 (群論)|拉格朗日定理]]

==參考==
<references/>

{{皮埃爾·德·費馬}}

[[Category:同余]]
[[Category:数学定理|F]]