费马小定理从组合数学角度来理解

橘子网 1,103 0

在数论中,有两个以法国数学家皮埃尔·德·费马(Pierre de Fermat)命名的定理,一个叫做费马小定理(Fermat's little theorem),另一个叫做费马大定理(Fermat's Last Theorem,也叫费马最终定理)。今天我们要讲的是前者“费马小定理”,它在实际应用中非常广泛,为质数的检测奠定了理论基础。

费马小定理从组合数学角度来理解

费马于1640年在写给朋友Bessy的信中第一次提出了这个定理。费马认为:p是一个质数时,对于任意的整数a都有apamod p。当然,费马本人并没有给出数学证明。据考证,历史上第一个证明费马小定理的人是德国数学家莱布尼茨。费马作为“业余数学家之王”,总是干这种事情,费马大定理也是如此,足足让后人折腾了三百六十多年才最终由英国剑桥数学家安德鲁·怀尔斯(Andrew John Wiles)得到证明。

费马小定理从组合数学角度来理解

后来,由包括欧拉等人都给出了费马小定理的证明过程,这些证明在各种数论著作和教科书中都可以找到答案,我就不再赘述了。这里,我想通过组合数学的角度,来让读者朋友们直观地理解一些费马小定理的正确性,希望对大家学习数论有所启发和帮助。

废话少说,言归正传。让我先从最简单的圆桌座位和串珠问题开始说起。听过我讲组合数学的同学应该很熟悉,我经常以圆桌座位和串珠问题作为解释排列问题的经典例子。

问题:有一个圆桌,共有五个座位。五个人坐在这些座位上,共有几种入座方式?

费马小定理从组合数学角度来理解

很多同学第一眼看到这个问题时,都会想当然地回答:5!=5×4×3×2×1=120种。真的是这样吗?

要回答这个问题,就要先理解圆桌和长桌的座位有什么区别。假如现在不是圆桌,而是长桌。如下图所示:

费马小定理从组合数学角度来理解

假设现在有A、B、C、D、E这五个人入座,ABCDE是一种就座的顺序,EABCD也是一种顺序,DEABC又是一种顺序,……。之所以称为不同的就座顺序,是因为对于这里的每个人而言,他们左右的邻居或多或少都发生了一些变化。因此,就长桌而言,答案就是5!=5×4×3×2×1=120种。

那么圆桌呢?与长桌相比,又有什么变化呢?我们发现,下面这五种情况虽然在长桌上属于不同的情况,但在圆桌上其实是一种情况,因为对于这五人中的任何一位而言,无论怎么入座,他的左右领座都没有发生变化,所以属于同一种顺序。

费马小定理从组合数学角度来理解

因此,上述问题的答案就是5!/5=4!=24种,这里除以5是把五种相同的重复情况剔除掉。

那么,这个问题到底对费马小定理的理解有什么帮助呢?接下来,就让我们从这个问题出发,扩展到费马小定理的证明上去。

假设有3种(a)不同颜色的珠子,每种珠子都有无穷多颗。现在从这些珠子中挑出颜色不完全相同的5颗(p)珠子来串成项链,总共可以串出多少种不同的项链?

我们先从简单的情况考虑,只考虑将任意的5颗(p)珠子串成一长条的珠子串。如下图所示:

费马小定理从组合数学角度来理解

那么,对于每一个位置上的珠子而言,都有3种(a)颜色可供选择,也就是有3种可能性,那么5颗珠子就有35(ap)种可能性。在这些可能性里面,全部5颗珠子是一种颜色的有3种(a)可能性,不符合条件,要剔除。于是,剩下的全部可能性就是35-3种(ap-a)可能性。

然后,我们又发现,下面这5种长条的珠子串在接成项链的时候其实属于同一种情况,被重复计算了,需要剔除。如下图所示:

费马小定理从组合数学角度来理解

因此,满足条件的可能性就是(35-3)/5种可能性,即:(ap-a)/p。这个结果一定是一个整数。于是,我们可以得到p| ap-a,即ap≡a(mod p)。

最后我们还要解决一个问题,那就是:假如p不是一个质数,这个定理是不成立的。

现在假设项链需要6颗珠子(p=6),看看会发生什么情况?

费马小定理从组合数学角度来理解

我们发现,在上图中,每3种颜色的6颗珠子组合,最终其实对应的是同一条项链。这从直观上证明了当p为合数而非质数时,费马小定理是不成立的。证明完毕。

另外,费马小定理还有一个推论:假如p是一个质数,对于任何一个不能被p整除的整数a而言,都有ap-11mod p。这个推论很容易证明。根据前面的费马小定理,我们可知p| ap-a,进而可得到p| a(ap-1-1)。由于p不能整除a,那么p一定可以整除ap-1-1,即p| ap-1-1,于是可以得到ap-1≡1(mod p)。证明完毕。

同学们和读者朋友们,你们有么有觉得用组合数学的视角来证明费马小定理很有意思啊!这就是我为何特别喜欢给学生讲组合数学的一个原因,让你有不同的视角看同样的问题,得到很直观的答案。

费马小定理就讲解到这里,大家要继续努力学习哈!最美妙的学问需要大家努力去奋斗才会感受到,“无限风光在险峰”说的就是这个意思。加油吧!

上一篇:

下一篇:

相关文章

发表评论 取消回复
表情 图片 链接 代码

分享
微信
微博
QQ