费马小定理

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

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

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

卡迈克尔数

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

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

方法一

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

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

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

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

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

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

方法二

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

再考虑${\displaystyle (b+1)^{p}}$ 的二项式展开，模${\displaystyle 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}}}$ 

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

方法三

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

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

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

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

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

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

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

故余数为3。

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

欧拉定理

费马小定理是欧拉定理的一个特殊情况：如果 ${\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 x^{N}{\pmod {(x^{p}-x)^{k}}}}$ 的结果可以得出${\displaystyle x^{N}{\pmod {p^{k}}}}$ 的结果

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

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

这个余式的一般结果是：

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

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

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

1. ^ Fermat's Little Theorem （页面存档备份，存于互联网档案馆）.WolframMathWorld.（英文）
2. ^ A proof of certain theorems regarding prime numbers. [2012-12-11]. （原始内容存档于2015-06-16）. 
3. ^ ^{3.0 3.1} 许介彦. 費馬小定理 (PDF). 科学教育月刊 (私立大叶大学电机工程学系). 2006年10月, (第293期): 37–44 [2015-04-18]. （原始内容 (PDF)存档于2015-04-18）. 
4. ^ How is (x+y)^p≡x^p+y^p mod p for any prime number p. Mathematics Stack Exchange. 2018-09-27 [2021-04-26]. （原始内容存档于2022-03-25） （英语）. 
5. ^ 聂灵沼; 丁石孙. 代数学引论 第二版. 北京: 高等教育出版社. 2000: 第33页. ISBN 7-04-008893-2.  使用|accessdate=需要含有|url= (帮助)
6. ^ 黄嘉威. 多项式除法解高次同余. 数学学习与研究. 2015, (9): 第104页 [2015-07-19]. （原始内容存档于2020-10-20）.