费马小定理及其多种证明费马小定理证明过程 _生活百科

文章插图

费马小定理：
如果p是一个素数，而a是任何不能被p整除的整数，那么p能除a??1 - 1 。
这个由皮埃尔·德·费马在1640年发现的数字性质，本质上是说，取任意素数p和任意不能被该素数整除的数a，假设p = 7, a = 20 。通过费马小定理，我们发现：

文章插图
我们不太关心这个计算结果的实际数字。这个定理告诉我们，我们不需要做任何计算就能知道一个整数必须由它得出。
介绍在17世纪皮埃尔·德·费马与世界各地数学家的许多通信中，与法国铸币局官员伯纳德·弗雷尼卡·德·贝西（1605-1675）的通信对数论影响最大。据说，德·贝西在法国以计算大数的天赋而闻名。

文章插图
【费马小定理及其多种证明费马小定理证明过程】当他听说费马提出了一个寻找立方数的问题，这个立方数的因数加起来就是平方数，就像73+(1 + 7 + 72)= 202一样，贝西立即给出了四个不同的解，第二天又给出了六个。——节选，《初等数论》
德?贝西本人后来最为人所知的是他的著作《寻找等效于魔法格的正方形》（Finding the square equivalent of magic tables），这是他死后于1693年出版的一篇关于魔方格的专著，他在书中提供了880个4阶的魔方格。魔方格是一个n × n的格子，格子里填满了不同的正整数，每个格子里包含一个不同的整数，并且每一行、每一列和每对角线上的整数的和都是相同的。
作为数学家，费马在很多方面都无法与贝西相提并论，但谈到数论家，没有一个同时代的人能挑战费马。费马和贝西在17世纪中期的合作导致了数论中一些最惊人的发现，包括数字1729的立方属性。
然而，两人最引人注目的通信是费马在1640年10月18日的一封信中提出了后来被称为费马小定理的定理。
证明将近一百年后的1736年，欧拉在圣彼得堡学院学报上发表了一篇题为《关于素数的某些定理的证明》的论文，成为第一个证明费马小定理的人。然而，后来人们发现，莱布尼茨在1683年之前的某个时候，在一份未发表的手稿中给出了几乎相同的证明，但欧拉不可能知道。
今天，这个定理的许多证明已经为人所知。证明一般依赖于两种简化，首先，假设a在0≤a≤p?1范围内。第二，证明费马小定理在1≤a≤p?1范围内成立是充分的。
用二项式定理证明
欧拉的第一个证明是多项式定理的一个非常简单的应用：

文章插图
多项式定理这个求和是通过k?得到的所有非负整数索引k?的序列，这样所有k?的和就是n，如果我们把a表示为1的p次方的和(1 + 1+ 1+…1?)?，我们得到：

文章插图
如果p是质数，对于任意j，k?不等于p，我们有：

文章插图
如果p是质数，对于某个j，k?=p，我们有：

文章插图
因为正好有一个元素使k?= p，所以定理成立。
作为欧拉定理的一个推论的证明
这个定理的另一个证明是，欧拉定理是费马小定理的推广。欧拉定理指出，若n，a为正整数，且n和a互质，则：

文章插图
其中φ(n)是欧拉函数，它计算从1到n之间的素数。如果n是素数，则得出费马小定理，即φ(n) = n?1 。费马小定理的证明可以从欧拉定理的证明中得到，欧拉定理的证明通常是用群论来完成的。
模算法证明下面的证明，使用模运算，最初是由James Ivory在1806年发现的，后来被Dirichlet在1828年重新发现。
费马小定理的证明
我们首先考虑整数a，2a，3a，…（p - 1）a 。这些数都不等于p对其他数的模，也不等于0 。如果这样，那么有：
r × a ≡ s × a （mod p），1 ≤ r < s ≤ p - 1
那么，两边消去a将得到r≡s (mod p)，这是不可能的，因为r和s都在1和p - 1之间。因此，前一组整数必须同余模p到1，2，…p - 1 。把这些同余相乘，你会发现：
a × 2a × 3a × ... × (p - 1) × a ≡ 1 × 2 × 3 × ... × (p - 1)(mod p)
意味着
a??1 × （p - 1）! ≡ （p - 1）!（mod p）。
从这个表达式的两边消去（p - 1）!，我们得到：
a??1 ≡ 1 (mod p) 。
用群论证明
用群论证明费马小定理，考虑到集合G ={1，2，…，p?1}用乘法运算形成一个群。在四个群公理中，唯一需要验证的是第四个公理，即G中的元素是可逆的。想了解详细内容可以看这篇文章：由浅入深，轻松理解抽象代数的重要分支——群论
如果我们假设G中的每个元素都是可逆的，假设a在1≤a≤p?1的范围内，也就是说，假设a是G的一个元素。设k是a的阶数，即使a?≡1 (mod p)为真时的最小正整数。然后数字1，a，a2，…，a??1 约模p，形成G的一个序为k的子群，根据拉格朗日定理，k能整除G的阶数，即p?1 。对于正整数m，有p?1 = km，并且：

文章插图
为了证明G与p互质的每个元素b都是可逆的，这个恒等式可以帮助我们如下。因为b和p是素数，贝祖恒等式保证了有整数c和d使得bc + pd = 1 。对p取模，这意味着c是b的逆，因为bc≡1（mod p）。因为b是可逆的，所以G中的其他元素也是可逆的，所以G必须是一个群。
应用，素性测试费马小定理将成为费马质数检验的基础，这是一种确定一个数是否为质数的概率方法。例如，如果我们想知道n = 19是否为素数，随机取 1 < a < 19，假设a = 2 。计算n?1 = 18，及其因子是9和6 。我们通过计算21? ≡ 1 （mod 19），2? ≡ 18（mod 19）和 2? ≡ 7 （mod 19）来检验，最后发现19必须是素数。