费马小定理

如上所述，中国猜测仅有一半是正确的。符合中国猜测但不是素数的数被称为伪素数。

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

若n不能整除${\displaystyle a-b}$，${\displaystyle x>0}$，${\displaystyle (x,n)=1}$，則n也不能整除${\displaystyle x(a-b)}$。取整數集${\displaystyle A}$为所有小於${\displaystyle p}$的集（${\displaystyle A}$构成${\displaystyle p}$的完全剩余系，即${\displaystyle A}$中不存在两个数同余${\displaystyle p}$），${\displaystyle B}$是${\displaystyle A}$中所有的元素乘以a组成的集合。因为${\displaystyle A}$中的任何两个元素之差都不能被p整除，所以B中的任何两个元素之差也不能被p整除。

換句話說，${\displaystyle \gcd(a,p)=1}$，考慮${\displaystyle 1\times a,2\times a,3\times a,....(p-1)\times a}$共${\displaystyle (p-1)}$個數，將它們分別除以p，餘數分別為${\displaystyle r_{1},r_{2},r_{3},....,r_{p-1}}$，則集合{r₁,r₂,r₃,...,r_p-1}為集合{1,2,3,...,(p-1)}的重新排列，即1,2,3,....,(p-1)在餘數中恰好各出現一次；這是因為對於任兩個相異k*a而言（k=1,2,3....(p-1)），其差不是p的倍數（所以不會有相同餘數），且任一個k*a亦不為p的倍數（所以餘數不為0）。因此

${\displaystyle 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}},}$

即

${\displaystyle W\equiv W\cdot a^{p-1}{\pmod {p}},}$

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

${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$[3]

考慮二項式係數${\displaystyle {\tbinom {p}{n}}={\tfrac {p!}{n!(p-n)!}}}$，並限定n不為p或0，則由於分子有質數p，但分母不含p，故分子的p能保留，不被約分而除去，即${\displaystyle {\tbinom {p}{n}}}$恆為p的倍數。

再考慮(b+1)^p的二項式展開，模p，則

${\displaystyle (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}}}$

${\displaystyle \equiv {\dbinom {p}{p}}b^{p}+{\dbinom {p}{0}}b^{0}{\pmod {p}}}$

${\displaystyle \equiv b^{p}+1{\pmod {p}}}$

因此

${\displaystyle (b+1)^{p}\equiv b^{p}+1{\pmod {p}}}$

${\displaystyle \equiv (b-1)^{p}+1+1{\pmod {p}}}$

${\displaystyle \equiv (b-2)^{p}+1+1+1{\pmod {p}}}$

${\displaystyle \equiv (b-3)^{p}+1+1+1+1{\pmod {p}}}$

${\displaystyle \dots }$

${\displaystyle \equiv {\begin{matrix}\underbrace {1+1+\dots +1+1} \\b+1\end{matrix}}{\pmod {p}}}$

${\displaystyle \equiv b+1{\pmod {p}}}$

令b=a-1，即得${\displaystyle a^{p}\equiv a{\pmod {p}}}$。[3]

在抽象代数教科书中，费马小定理常作为教授拉格朗日定理时的一个简单例子[4]。显然只需考虑 ${\displaystyle (a,p)=1}$ 情形。此时模 ${\displaystyle p}$ 所有非零的余数，在同余意义下对乘法构成一个群，这个群的阶是 ${\displaystyle p-1}$。考虑群中的任何一个元素 ${\displaystyle b}$，根据拉格朗日定理，${\displaystyle b}$ 的阶必整除群的阶。证毕。

费马小定理是欧拉定理的一个特殊情况：如果 ${\displaystyle (a,n)=1}$ ，那么

${\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}$

这里 ${\displaystyle \varphi (n)}$ 是欧拉函数。欧拉函数的值是所有小于或等于 ${\displaystyle n}$ 的正整数中与 ${\displaystyle n}$ 互質的数的个数。假如 ${\displaystyle n}$ 是一个素数，则 ${\displaystyle \varphi (n)=n-1}$ ，即费马小定理。

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

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

${\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}$

${\displaystyle p|x^{p}-x\Rightarrow p^{k}|(x^{p}-x)^{k}}$

除式：${\displaystyle \displaystyle x^{pk}\equiv \sum _{i=1}^{k}(-1)^{i-1}{\binom {k}{i}}x^{pk-(p-1)i}{\pmod {p^{k}}}}$

余式：${\displaystyle \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}}}}$

n=0时为除式，用数学归纳法证明余式。[5]

求${\displaystyle x^{1000}{\pmod {5^{2}}}}$

${\displaystyle x^{10+4n}\equiv (n+2)x^{6}-(n+1)x^{2}{\pmod {5^{2}}}}$

${\displaystyle x^{1000}\equiv 249x^{8}-248x^{4}\equiv 24x^{8}-23x^{4}{\pmod {5^{2}}}}$