费马小定理

费马小定理（英语：Fermat's little theorem）是数论中的一个定理。假如$a$是一个整数，$p$是一个质数，那么$a^{p}-a$是$p$的倍数，可以表示为

$a^{p}\equiv a{\pmod {p}}$

如果$a$不是$p$的倍数，这个定理也可以写成更加常用的一种形式

$a^{p-1}\equiv 1{\pmod {p}}$

注：如果$a$是$p$的倍数，则

$a^{p-1}\equiv 0{\pmod {p}}$

费马小定理的逆叙述不成立，即假如$a^{p}-a$是$p$的倍数，$p$不一定是一个质数。例如$2^{341}-2$是$341$的倍数，但$341=11\times 31$，不是质数。满足费马小定理的合数被称为费马伪素数。

历史

皮埃尔·德·费马

皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求。

1736年，欧拉出版了一本名为“一些与素数有关的定理的证明”（拉丁文：Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio）”的论文集，其中第一次给出了证明。但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。

有些数学家独立提出相关的假说（有时也被错误地称为中国猜想），当$2^{p}\equiv 2{\pmod {p}}$成立时，p是素数。这是费马小定理的一个特殊情况。然而，这一假说的前设是错的：例如，$2^{341}\equiv 2{\pmod {341}}$，而$341=11\times 31$是一个伪素数。所有的伪素数都是此假说的反例。

卡迈克尔数

主条目：卡迈克尔数

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

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

证明

方法一

（i）若$a$是整数，$p$是素数，且$\gcd(a,p)=1$。若$p$不能整除$x-y$，则$p$不能整除$a(x-y)$。取整数集$A$为所有小于$p$的正整数集合（$A$构成$p$的完全剩余系，即$A$中不存在两个数同余$p$），$B$是$A$中所有的元素乘以$a$组成的集合。因为$A$中的任何两个元素之差都不能被$p$整除，所以$B$中的任何两个元素之差也不能被$p$整除。

换句话说，$\gcd(a,p)=1$，考虑$1\times a,2\times a,3\times a,....(p-1)\times a$共$(p-1)$个数，将它们分别除以$p$，余数分别为$r_{1},r_{2},r_{3},....,r_{p-1}$，则集合$\{r_{1},r_{2},r_{3},....,r_{p-1}\}$为集合$\{1,2,3,\ldots ,(p-1)\}$的重新排列，即$1,2,3,\ldots ,(p-1)$在余数中恰好各出现一次；这是因为对于任两个相异$k*a$而言（$k=1,2,3,\ldots ,(p-1)$），其差不是$p$的倍数（所以不会有相同余数），且任一个$k*a$亦不为$p$的倍数（所以余数不为0）。因此

$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}},$

即

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

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

$a^{p-1}\equiv 1{\pmod {p}}$

也即 $a^{p}\equiv a{\pmod {p}}$

（ii）若$p$整除$a$，则显然有$p$整除$a^{p}$，即$a^{p}\equiv a\equiv 0{\pmod {p}}$。

方法二

参见：中一新生之梦

若$p$为素数，$n$为整数，且$p\geq n$。考虑二项式系数${\tbinom {p}{n}}={\tfrac {p!}{n!(p-n)!}}$，并限定$n$不为$p$或$0$，则由于分子有素数$p$，但分母不含$p$，故分子的$p$能保留，不被约分而除去，即${\tbinom {p}{n}}$恒为$p$的倍数。

再考虑$(b+1)^{p}$的二项式展开，模$p$，则

$(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}}$

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

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

因此

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

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

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

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

$\dots$

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

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

令$a=b+1$，即得$a^{p}\equiv a{\pmod {p}}$。

方法三

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

应用

• 计算$2^{100}$除以13的余数

$2^{100}\equiv 2^{12\times 8+4}{\pmod {13}}$

$\equiv (2^{12})^{8}\cdot 2^{4}{\pmod {13}}$

$\equiv 1^{8}\cdot 16{\pmod {13}}$

$\equiv 16{\pmod {13}}$

$\equiv 3{\pmod {13}}$

故余数为3。

• 证明对于任意整数a而言，$a^{13}-a$恒为2730的倍数。
  • 易由$a^{p-1}\equiv 1{\pmod {p}}$推得$a^{n(p-1)+1}\equiv 1^{n}\cdot a\equiv a{\pmod {p}}$，其中$n$为正整数。
  • 故对指数13操作如下：13减1为12，12的正约数有1, 2, 3, 4, 6, 12，分别加1，为2, 3, 4, 5, 7, 13，其中2, 3, 5, 7, 13为素数，根据定理的延伸表达式，$a^{13}-a$为2的倍数、为3的倍数、为5的倍数、为7的倍数、为13的倍数，即2*3*5*7*13=2730的倍数。

• 证明对于任意整数a而言，$a^{22}-a^{2}$恒为3300的倍数。

证明

• $a^{22}-a^{2}$为132的倍数。
  1. 模仿前述操作，11减1为10，10的正约数有1, 2, 5, 10，分别加1，为2, 3, 6, 11，其中2, 3, 11为素数，因此$a^{11}-a$为2, 3, 11的最小公倍数的倍数，即66的倍数。
  2. 考虑$a^{11}+a$，因为奇数的11次方仍为奇数，且奇数与奇数之和为偶数，故当a为奇数时，$a^{11}+a$为偶数；同理可知当a为偶数时，$a^{11}+a$仍为偶数。因此当a为任意整数时，$a^{11}+a$为偶数。
  3. 因此$a^{22}-a^{2}=(a^{11}-a)(a^{11}+a)=66$的倍数$\times 2$的倍数$=132$的倍数。
• $a^{22}-a^{2}$为25的倍数。
  • 由后文的欧拉定理可知$a^{20}\equiv 1{\pmod {25}}$（当a与25互素时），即$a^{21}\equiv a{\pmod {25}}$（当a为任意整数时）。因此$a^{22}-a^{2}=a(a^{21}-a)$为25的倍数。
• 因此$a^{22}-a^{2}$为132与25的的最小公倍数的倍数，即3300的倍数。

推广

欧拉定理

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

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

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

证明

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

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

卡迈克尔函数

主条目：卡迈克尔函数

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

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

多项式除法

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

所以由$x^{N}{\pmod {(x^{p}-x)^{k}}}$的结果可以得出$x^{N}{\pmod {p^{k}}}$的结果

用多项式除法可以得出$x^{N}$除以$(x^{p}-x)^{k}$的次数少于$p^{k}$的余式

例如$3\mid x^{3}-x$，由多项式除法得到$x^{5}=(x^{2}+1)(x^{3}-x)+x$，则$x^{5}\equiv x{\pmod {3}}$

这个余式的一般结果是：

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

$\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时为除式，用数学归纳法证明余式。

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

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

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

参见

• 费马大定理
• 拉格朗日定理