氢原子百科 
费马小定理（英文：Fermat small theorem），简称费马定理，是初等数论的重要定理。[1]该定理表述为：若p是个素数，a是不能被p整除的整数，则p整除ap-1-1。[7]此外，从同余的角度也能对该定理进行表述。[8]
1637年，法国数学家皮埃尔·德·费马（Pierre de Fermat）在阅读古希腊数学家丢番图（Diophantus）所著的《算术》译本过程中，对素数和整数的可除性问题进行了研究工作，后于1640年10月18日，费马在一封写给德·贝西（B.F.de Bessy）的信中给出了费马小定理，但并未作出相关证明。[2]德国数学家莱布尼茨（G.W.Leibniz）[12]在1683年未发表的一篇手稿中，给出了费马小定理的早期证明。[13]1736年，瑞士数学家欧拉（L.Euler）正式发表了费马小定理的第一个证明，并于1760年对它进行了推广。[3]后来，德国数学家高斯（C.F.Gauss）在1801年发表的著作《算术研究》一书中，给出了同余的符号，并用同余式简捷地证明了费马小定理。[1][4]在东方，中国清代数学家李善兰在1872年著成的《考数根法》一书中也证明了费马小定理，并指出它的逆命题不真。[5]20世纪，费马小定理出现在亨塞尔（K.Hensel）的书中，与有限群有关。[6]
费马小定理可由多种方法证明，如数学归纳法[8]、欧拉定理证法[10]、周期点证法。[11]由费马小定理可得出伪素数的概念，[10]它还可用于判断数的整除性[14]和求解不定方程。[15]此外，费马小定理在现实世界中具有广泛的应用价值，如密码学中，RSA公开密钥算法的基础理论就是依据数论中的费马小定理来对大数进行质因数分解。[16]
定理内容
费马小定理：若是个素数，为整数，若，则整除。[7]
同余角度的解释：设为素数，为整数，若，则，或在同余号两边同乘，可得。[8]
早期起源
数论有着悠久的发展历史，早在公元前3世纪的古希腊时代，数学家欧几里得（Euclid）所著《几何原本》一书中就记载了对素数无限性的证明、整数的因数分解、求两个正整数最大公因数的辗转相除法等相关理论。[1]1637年，法国数学家皮埃尔·德·费马（Pierre de Fermat）在阅读古希腊数学家丢番图（Diophantus）所著的《算术》译本过程中对于素数和整数的可除性问题给出了许多论断。后来，1640年10月18日，费马在一封写给德·贝西（B.F.de Bessy）的信中给出了费马小定理：若是个素数而与互素，则能为整除。但费马并未作出相关证明。[2]
后续发展
早在1683年，德国数学家莱布尼茨（G.W.Leibniz）[12]未发表的一篇手稿中记载了关于费马小定理的一个证明。[13]后来，瑞士数学家欧拉（L.Euler）在1736年正式发表了关于费马小定理的第一个证明，并于1760年引进了欧拉函数，推广了费马小定理：如果与互素，则可以被整除。该定理被称为欧拉定理，费马小定理是它的一个特例。[3]1801年，德国数学家高斯（C.F.Gauss）在发表的著作《算术研究》一书中，定义了有理整数模一个自然数同余的概念，给出了同余的符号，并用同余式简捷地证明了费马小定理。[1][4]在东方，中国清代数学家李善兰在1872年著成的《考数根法》中也证明了费马小定理，并指出它的逆命题不真。[5]此外，在1913年德国数学家亨塞尔（K.Hensel）出版的著作《数论》[注1]一书中，费马小定理还与有限群相关。[6]
几何意义
如图1，当时，费马小定理的几何意义为：为素数时，函数与的图形的个交点中含与图形的个交点，交点个数之差是的整数倍。[11]
数学归纳法
证明：对用数学归纳法，时显然成立，设成立，考察，是整数，是的倍数（分子的不可能被分母消去，因），故，证毕。[8]
欧拉定理证法
证明：设是欧拉函数，于是，由于是一个素数，所以，又，故。那么，在欧拉定理中，取，就有，证毕。[10]
周期点证法
证明：考虑在度量空间上，根据移位映射与不动点的定义可知有个点满足，其中有个是的不动点。而是素数，故这个点中除有个不动点外没有其他周期小于的周期点，即是素数时，有个周期点，它们构成条周期轨，所以为一整数，证毕。[11]
伪素数
通常，费马小定理的逆定理不一定成立，即时，不一定是素数。但对于特殊情形，逆定理是可成立的。[10]
定理：若，且对于的任一真因数，有，则是素数，被称为伪素数。[10]
伪素数：一般地，把满足的合数称为伪素数。[10]
绝对伪素数：如果为合数且对任何与互素的整数都有，则称为绝对伪素数（或者卡迈克尔伪素数）。[17]
例如，是一个伪素数，但不是绝对伪素数；是最小的绝对伪素数。[10][17]
米勒-拉宾素性检验
米勒-拉宾算法是基于概率的素数测试算法，它的理论基础是费马小定理，可表述为：如果是一个奇素数，将表示成的形式（是奇数），是和互素的任何整数，那么或者对某个等式成立。[18]
方法
设待检测的整数为，米勒-拉宾算法包括如下步骤：[19]
（1) 计算整除的次数（即是能整除的的最大幂），然后计算，使得；
（2）选择一个小于的随机数；
（3）设，计算；
（4）如果或，那么通过测试，可能是素数；
（5）如果且，那么是合数；
（6）令，如果且，设，然后返回到（5），如果，那么通过测试，可能是素数；
（7）如果且，那么为合数。[19]
周期点数计数公式
周期点定义：如果，则称为的一个阶周期点，与这个点的集合称为的一个阶轨道。[20]
用表示有限集合的元素个数，则有：设是的素数幂分解式，若的阶周期点的个数有限，则
。[20]
推广：设是的素数幂分解式，则对任何自然数，
有，
当为素数时，，那么式为，即是费马小定理的欧拉形式。[20]
进一步地，在时，则有充分必要。换言之，若，则，其中，则费马-欧拉定理成立。[20]
判断数的整除性
例题 证明可被整除。[14]
证明：应用费马小定理有：
，
，因不是素数，应用牛顿二项式定理，有
（1）由首尾等距结合分组，共分组，可证明有因子。[14]
（2），将单独计算，再二次分组，采用首尾结合，可证明中必有因子。
（3），一次分组，除过后，二次分组，首尾结合各数可证明必含因子。
（4）偶数的次方必可被除尽，其余奇数项共有项。个奇数次幂之和必然可被整除。与各偶数次幂的和必可被整除。
（5）除过外，首尾结合与与与与其次幂应用公式可证得中必有因子，从而证毕。[14]
求解不定方程
例题 求证：有的解时，中必有一成立。[15]
证明：假设，则。
所以，。
则，与已知条件矛盾，即原命题成立。[15]
高级加密标准
在高级加密标准中，盒算法是一个非线性的字节代替变换，是整个高级加密标准加解密硬件实现的关键模块。基于费马小定理的正逆盒算法原理及运算特点，可设计一种小规模、快速的可逆盒运算电路，它能实现盒的正逆运算，加速盒运算的过程，并且有效减小解密电路的规模，对高级加密标准算法的硬件实现具有实际价值。[9]
公钥密码算法
参考资料 21
- 参考 1
- 参考 2
- 参考 3
- 参考 4
- 参考 5
- 参考 6
- 参考 7
- 参考 8
- 参考 9
- 参考 10
- 参考 11
- 参考 12
- 参考 13
- 参考 14
- 参考 15
- 参考 16
- 参考 17
- 参考 18
- 参考 19
- 参考 20
- 参考 21
注释
- 德语：Zahlentheorie