費馬小定理於1636年提出,此時距明朝滅亡還有8年。
它的描述是:
p是質數,a是與p互質的任意整數,則
a^{p-1}≡1\pmod p
數學符號的意義:
- a≡b\pmod m
a-b能被m整除,或說a與b對m求模時同餘。比如15≡3\pmod 6,等同於說15-3=12是6的倍數。
- a\mod b=m
a除以b餘m,或說a對b求模。比如15\mod 6=3,等同於說15除以6,餘數是3。
- a|b
b能被a整除,等價於b≡0\pmod a。如12|24,即24能被12整除。
- (a,b)=m
a跟b的最大公約數是m。如(24,36)=12,即24跟36的最大公約數是12。
證明一(完全剩餘系)
本證明利用「完全剩餘系」的性質。
設p是質數,a是跟p互質的整數。
A=\{x|x<p,x\in N_+\},x_m\in A。
B=\{1,2,\cdots,(p-1)\},y_n\in B。
則在B裏面一定能找到一個數y_n,與a\cdot x_m對p求模時同餘,即a\cdot x_m≡y_n\pmod p
這樣我們把A的每一項都乘以a之後,對p求模,一定能與B中的每一項同餘:
a\cdot x_1≡1\pmod p\\a\cdot x_2≡2\pmod p\\a\cdot x_3≡3\pmod p\\ \vdots\\a\cdot x_{p-1}≡p-1\pmod p這裏需要用反證法來證明,假設y_k跟a\cdot x_i對p求模時同餘,同時它跟a\cdot x_j對p求模時也同餘,x_i>x_j,即
\begin{cases}a\cdot x_i≡y_k\pmod p\\a\cdot x_j≡y_k\pmod p\end{cases}則根據同餘性質,得:
a\cdot x_i≡a\cdot x_j\pmod p移項,得:
a(x_i- x_j)≡0\pmod p而由於p是質數,a與p互質,(x_i-x_j)是比p小的正整數,因此a(x_i- x_j)不可能被p整除。
則假設不成立,反證原命題成立,即「A中的每一項與a的積,對p求模,都能與B中的每一項同餘」成立。此乃「完全剩餘系」的性質。
將上面連續的式子左右相乘,得:
a^{p-1}(x_1\cdot x_2\cdot ...\cdot x_{p-1})≡(p-1)!\pmod p因為(x_1\cdot x_2\cdot ...\cdot x_{p-1})=(p-1)!,且此值與p互質,因此上式可簡化為:
a^{p-1}≡1\pmod p即得證費馬小定理。
證明二(帕斯卡三角和數學歸納法)
設p為質數,則帕斯卡三角的第p行削頭去尾之後,其餘項都是p的倍數。
因此,如果m,n為任意整數,p為質數,則可以有:
(m+n)^{p}≡m^p+n^p\pmod p下面用數學歸納法證明a^{p}≡a\pmod p。
-
令m=0,n=1,則:
(0+1)^{p}≡0^p+1^p\pmod p命題成立。
-
設k^{p}≡k\pmod p成立。令m=k,n=1,則:
(k+1)^{p}≡k^p+1^p\pmod p根據同餘性質,兩式左右相加,
(k+1)^{p}+k^{p}≡k+k^p+1^p\pmod p化簡,得:
(k+1)^{p}≡k+1\pmod p命題成立。若令n=-1,命題亦成立。
由上面(1)(2),根據數學歸納法,命題得證。
如果a是與p互質的整數,則左右兩邊除以a,得:
a^{p-1}≡1\pmod p即得證費馬小定理。