用组合计数原理证明威尔逊定理

橘子网 3,648 0

由于数论知识在我们普通的学校应试教育中属于空白领域,因此哪怕读者朋友学过高等数学知识,看这部分内容依旧会很费劲,甚至一脸茫然。

所以,各位读者朋友们,请大家对自己的孩子们多点耐心,不要对着孩子大吼大叫,因为用不了多久连你们自己也会啥都看不懂了。下图就是真实的写照,请大家对号入座,哈哈!

用组合计数原理证明威尔逊定理

好了,言归正传,今天继续上次的文章,用组合数学的角度解释数论中另一个重要的定理“威尔逊定理”。

在初等数论中,威尔逊定理(Wilson's Theorem)给出了判定一个自然数是否为素数的充分必要条件,即:当且仅当p为素数时,有(p1)!≡-1(mod p)

用组合计数原理证明威尔逊定理

威尔逊定理是以英格兰数学家爱德华·华林(Edward Waring)的学生约翰·威尔逊(John Wilson)命名的,不过这对师生都未能给出证明。华林于1770年提出该定理,1773年由拉格朗日首次证明。不过有证据显示,德国数学家莱布尼茨在华林和威尔逊出生之前(大约一百年前)就已经知道有这么个定理了,只是没有公开发表。又是莱布尼茨,还让不让人活了啊!

用组合计数原理证明威尔逊定理

威尔逊定理有很多证明方法,读者朋友可以找相关的数论著作和教科书来看,一般都有介绍。这里我依旧想给大家介绍一种组合数学的视角来理解这个定理。证明如下:

威尔逊定理相当于要证明等价表达式p|[(p-1)!+1]成立,即质数p可以整除(p-1)!+1。当p=2或者3时,2|(1!+1)或3|(2!+1),显然成立;现在假设p≥5。

用组合计数原理证明威尔逊定理

假如在一个圆上,均匀地分布着5(p)个点,请问可以构造出多少个5角星(stellated p-gons)?根据组合数学的知识,我们可以先从这5(p)个点中选一个,然后从剩下的4(p-1)个点中选一个,再从剩下3(p-2)个点中选一个,……;因此,全部的可能性就是5!(p!)种。

然而,在所有这些可能性中,我们发现存在着重复。我们可以从这5(p)个点中的任何一点出发,最后回到这一点;我们也可以从第一条线段的另外一点出发,再回到那一点;因此,每一种可能的五角星其实有5×2(2p)种重复。所以,最后我们可以得到不同的五角星数量为:5!/(2×5)=(5-1)!/2=12,即p!/2p=(p-1)!/2。

如下图所示:

用组合计数原理证明威尔逊定理

在所有这些五角星中,我们又发现,存在着2个正的五角星,如上图的(a)部分所示。

当p=11时,存在5个正的11角星:

用组合计数原理证明威尔逊定理

当p=13时,存在6个正的13角星:

用组合计数原理证明威尔逊定理

很容易证明,这种正p角星数量为(p-1)/2

于是,我们得到全部的非正的五角星数量为(5-1)!/2-(5-1)/2种,即(p-1)!/2-(p-1)/2。而在这些非正的五角星中,每一个都可以通过旋转(360/p)°而得到5(p)个完全一样的形状。如:

用组合计数原理证明威尔逊定理

于是,我们可以得到[(p-1)!/2-(p-1)]/2p是一个整数,即p可以整除(p-1)!-p+1,也即p|[(p-1)!-p+1]。进一步推出,p|[(p-1)!+1]。证明完毕。

整个推理有一点烧脑,但明白之后会发现世界很精彩,简单即是美!

上一篇:

下一篇:

相关阅读

分享