費馬小定理的介紹及證明

費馬小定理於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_ka\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

  1. 令m=0,n=1,則:

    (0+1)^{p}≡0^p+1^p\pmod p

    命題成立。

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

即得證費馬小定理。

Leave a Comment