费马小定理(英语:Fermat's little theorem)是数论中的一个定理。假如
是一个整数,
是一个质数,那么
是
的倍数,可以表示为
![{\displaystyle a^{p}\equiv a{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ff656f721894b9a50a2b1d18538463a6a4ec15f)
如果
不是
的倍数,这个定理也可以写成更加常用的一种形式
[1][注 1]
注:如果
是
的倍数,则
![{\displaystyle a^{p-1}\equiv 0{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4c34a977d62179acf61c6935a2ec6e07ffd669f5)
费马小定理的逆叙述不成立,即假如
是
的倍数,
不一定是一个质数。例如
是
的倍数,但
,不是质数。满足费马小定理的合数被称为费马伪素数。
皮埃尔·德·费马
皮埃尔·德·费马于1636年发现了这个定理。在一封1640年10月18日的信中他第一次使用了上面的书写方式。在他的信中费马还提出a是一个素数的要求。
1736年,欧拉出版了一本名为“一些与素数有关的定理的证明”(拉丁文:Theorematum Quorundam ad Numeros PRIMOS Spectantium Demonstratio)”[2]的论文集,其中第一次给出了证明。但从莱布尼茨未发表的手稿中发现他在1683年以前已经得到几乎是相同的证明。
有些数学家独立提出相关的假说(有时也被错误地称为中国猜想),当
成立时,p是素数。这是费马小定理的一个特殊情况。然而,这一假说的前设是错的:例如,
,而341=11×31是一个伪素数。所有的伪素数都是此假说的反例。
如上所述,中国猜想仅有一半是正确的。符合中国猜想但不是素数的数被称为伪素数。
更极端的反例是卡迈克尔数:
假设
与561互质,则
被561除都余1。这样的数被称为卡迈克尔数,561是最小的卡迈克尔数。Korselt在1899年就给出了卡迈克尔数的等价定义,但直到1910年才由卡迈克尔(Robert Daniel Carmichael)发现第一个卡迈克尔数:561。1994年William Alford、Andrew Granville及Carl Pomerance证明了卡迈克尔数有无穷多个。
(i)若
是整数,
是素数,且
。若
不能整除
,则
不能整除
。取整数集
为所有小于
的正整数集合(
构成
的完全剩余系,即
中不存在两个数同余
),
是
中所有的元素乘以
组成的集合。因为
中的任何两个元素之差都不能被
整除,所以
中的任何两个元素之差也不能被
整除。
换句话说,
,考虑
共
个数,将它们分别除以
,余数分别为
,则集合
为集合
的重新排列,即
在余数中恰好各出现一次;这是因为对于任两个相异
而言(
),其差不是
的倍数(所以不会有相同余数),且任一个
亦不为
的倍数(所以余数不为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}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/dfbb68e559cc60d5ee0f7519544472d06b2224ba)
即
![{\displaystyle W\equiv W\cdot a^{p-1}{\pmod {p}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be677beeb9026d6c3ecde22c1abcd1d0cfec5308)
在这里
,且
,因此将整个公式除以
即得到:
[3]
- 也即
![{\displaystyle a^{p}\equiv a{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7ff656f721894b9a50a2b1d18538463a6a4ec15f)
(ii)若
整除
,则显然有
整除
,即
。
若
为素数,
为整数,且
。考虑二项式系数
,并限定
不为
或
,则由于分子有素数
,但分母不含
,故分子的
能保留,不被约分而除去,即
恒为
的倍数[4]。
再考虑
的二项式展开,模
,则
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c6ac8532934492357eadfe3c236cf777c8fa3754)
![{\displaystyle \equiv {\dbinom {p}{p}}b^{p}+{\dbinom {p}{0}}b^{0}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c4a9ddcad074ce4a393fcc177f3f4242538b680)
![{\displaystyle \equiv b^{p}+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6ec6f74cdd9a357b60669629e1fb7bc5fb94bd52)
因此
![{\displaystyle (b+1)^{p}\equiv b^{p}+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a31482c11fab2e81e2594d81496bf86ef35443c7)
![{\displaystyle \equiv (b-1)^{p}+1+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/404c1d92ff2d3ed99878070d7b32fcea16e1300d)
![{\displaystyle \equiv (b-2)^{p}+1+1+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38fb1f386fc0658b396c378c92263d27830652b2)
![{\displaystyle \equiv (b-3)^{p}+1+1+1+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9d526ae063c7a09ab1cd51e30d612e0af70504b4)
![{\displaystyle \dots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/5411a9d9722322917df8faecb6e01b72e3ecede4)
![{\displaystyle \equiv {\begin{matrix}\underbrace {1+1+\dots +1+1} \\b+1\end{matrix}}{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7717984d57085b276b171b2d9401ae787933a6fc)
![{\displaystyle \equiv b+1{\pmod {p}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/822bb0f8e64619037bec9d816800c78621a156b8)
令
,即得
。[3]
在抽象代数教科书中,费马小定理常作为教授拉格朗日定理时的一个简单例子[5]。显然只需考虑
情形。此时模
所有非零的余数,在同余意义下对乘法构成一个群,这个群的阶是
。考虑群中的任何一个元素
,根据拉格朗日定理,
的阶必整除群的阶。证毕。
- 计算
除以13的余数
![{\displaystyle 2^{100}\equiv 2^{12\times 8+4}{\pmod {13}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3190d6a070f03e1042e4496b32bb80059682c99e)
![{\displaystyle \equiv (2^{12})^{8}\cdot 2^{4}{\pmod {13}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d2350fd981e412bb55c1a31ee553f0c4d721218)
![{\displaystyle \equiv 1^{8}\cdot 16{\pmod {13}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/780be17c9a2750122321487d8c8ebbf4dacfc740)
![{\displaystyle \equiv 16{\pmod {13}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9598173429d851e085c58566885ea6de6239afd3)
![{\displaystyle \equiv 3{\pmod {13}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/75da65577ca8c5dfeda46defe1b607dd9bd8739a)
故余数为3。
- 证明对于任意整数a而言,
恒为2730的倍数。
- 易由
推得
,其中
为正整数。
- 故对指数13操作如下:13减1为12,12的正约数有1, 2, 3, 4, 6, 12,分别加1,为2, 3, 4, 5, 7, 13,其中2, 3, 5, 7, 13为素数,根据定理的延伸表达式,
为2的倍数、为3的倍数、为5的倍数、为7的倍数、为13的倍数,即2*3*5*7*13=2730的倍数。
- 证明对于任意整数a而言,
恒为3300的倍数。
证明
为132的倍数。
- 模仿前述操作,11减1为10,10的正约数有1, 2, 5, 10,分别加1,为2, 3, 6, 11,其中2, 3, 11为素数,因此
为2, 3, 11的最小公倍数的倍数,即66的倍数。
- 考虑
,因为奇数的11次方仍为奇数,且奇数与奇数之和为偶数,故当a为奇数时,
为偶数;同理可知当a为偶数时,
仍为偶数。因此当a为任意整数时,
为偶数。
- 因此
的倍数
的倍数
的倍数。
为25的倍数。
- 由后文的欧拉定理可知
(当a与25互素时),即
(当a为任意整数时)。因此
为25的倍数。
- 因此
为132与25的的最小公倍数的倍数,即3300的倍数。
费马小定理是欧拉定理的一个特殊情况:如果
,那么
![{\displaystyle a^{\varphi (n)}\equiv 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e818f3f88d3e71e569f171dd86f31e1903fdc55)
这里
是欧拉函数。欧拉函数的值是所有小于或等于
的正整数中与
互素的数的个数。假如
是一个素数,则
,即费马小定理。
- 证明
上面证明费马小定理的群论方法,可以同理地证明欧拉定理。
考虑所有与
互素的数,这些数模
的余数所构成的集合,记为
,并将群乘法定义为相乘后模
的同余。显然
是一个群,因为它对群乘法封闭(若
和
则
),含幺元(即“1”),且任何一个元素
的逆元素也在集合中(因为若
则由群乘法封闭性任何
的幂次都在
中,所以
是
这个有限集的子集)。根据定义,
的阶是
,于是根据拉格朗日定理,
中任何一个元素的阶必整除
。证毕。
卡迈克尔函数比欧拉函数更小。费马小定理也是它的特殊情况。
![{\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2e475506bcb72caae57599e0ccafa7efe023be9c)
因为
所以由
的结果可以得出
的结果
用多项式除法可以得出
除以
的次数少于
的余式
例如
,由多项式除法得到
,则
这个余式的一般结果是:
(除式)
n=0时为除式,用数学归纳法证明余式。[6]
- 求
![{\displaystyle x^{1000}{\pmod {5^{2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e44c3e08ec5f102bad983edfb5da19d1de7c527a)
- ^ Fermat's Little Theorem (页面存档备份,存于互联网档案馆).WolframMathWorld.(英文)
- ^ A proof of certain theorems regarding prime numbers. [2012-12-11]. (原始内容存档于2015-06-16).
- ^ 3.0 3.1 许介彦. 費馬小定理 (PDF). 科学教育月刊 (私立大叶大学电机工程学系). 2006年10月, (第293期): 37–44 [2015-04-18]. (原始内容 (PDF)存档于2015-04-18).
- ^ 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) (英语).
- ^ 聂灵沼; 丁石孙. 代数学引论 第二版. 北京: 高等教育出版社. 2000: 第33页. ISBN 7-04-008893-2.
- ^ 黄嘉威. 多项式除法解高次同余. 数学学习与研究. 2015, (9): 第104页 [2015-07-19]. (原始内容存档于2020-10-20).