您当前的位置:首页 > 学习 > 阅览室

经典证明:一个数论定理的组合学证明

时间:12-04来源:作者:点击数:

Wilson定理指出,对于任一个质数p,都有(p-1)! ≡ -1 (mod p),换句话说(p-1)! + 1能被p整除。为了证明这一点,让我们来考虑一个圆周上的p等分点。顺次连接这p个点我们可以得到一个正p边形,让它随便旋转多少个360/p度所得到的图形都和原来一样。类似地,跳跃着连接起第1, 3, 5…个点,或者两个两个地跳开来(连接1, 4, 7…个点),你可以得到一个星形的广义正p边形,它们同样满足类似的旋转对称性质。由于跳过k个点和跳过p-k-2个点是一回事,因此这种类型的多边形一共有(p-1)/2个。注意像这种“k个点k个点地跳着连接”的连接方式一定会遍历所有的点最后回到出发点:假如连接d个点后你就提前回到出发点了(而没有遍历完所有点),那一定还有若干组大小为d的点集没被连过,这样的话总点数就是d的倍数,与p是质数就矛盾了。

除了这种旋转对称的“广义正p边形”以外,其它的多边形随便旋转多少都不能和原来全等。假设有图形最少只需要旋转d个点的位置(d>1)之后就与原图形重合,那么p一定是d的倍数,否则当到了k·d<p<(k+1)d时p-k·d就成了更小的与原图重合的旋转角度;然而p是d的倍数与p是质数矛盾。这告诉我们,非旋转对称的多边形总是p个p个的成组出现,因此它们的数目能被p整除。

另一方面,连接圆周上的各点所能形成的多边形总数为(p-1)!/2,这是因为规定了起始点后,多边形就由剩下的p-1个点的排列确定,但每个多边形都各算了两次(顺时针、逆时针遍历各一次)。而前面已经提到过,广义的正p边形有(p-1)/2个。这样的话,非旋转对称的多边形总数就等于

(p-1)!/2 – (p-1)/2 = 1/2 [(p-1)! + 1 – p]

这个数目能被p整除当且仅当(p-1)! + 1能被p整除。

来源:http://www.cut-the-knot.org/blue/GeometricWilson.shtml

有趣的是,“p是质数”这一条件也是必要的。假设一个合数p也能整除(p-1)! + 1,这意味着它的某个大于1的因子d也能整除(p-1)! + 1;但同时d还能整除(p-1)!,这显然是不可能的。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门
本栏推荐