費馬小定理於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即得證費馬小定理。