|
|
楼主 |
发表于 2022-8-12 21:15
|
显示全部楼层
2022年8月12日周五农历七月十五晚20:12分
今天证明的定理是：剩余类个数过半定理，它是针对一个大于等于3的奇数为模，当参与二元加法运算
时，如果参与运算的剩余类个数大于等于(P+1)/2时，则二元运算mod(a+b,P)能覆盖所有剩余类，即
合成结果为模P的完全剩余系。
现在为了简明扼要的证明此定理，我们不妨设P=2m+1，既然我们是证明当剩余类个数大于等于m+1时
成立，那么，我们就以最少量的剩余类个数作为起点，这里先证明m以内的剩余类参与的情况（过后
在用置换替代思想证明其他组合方式），参与剩余类二元运算的剩余类为：0,1,2,3，…，m，这时
正好(P+1)/2个剩余类，mod(a+b,P)式子中的a，b可以取遍剩余类0至m，我们把a作为被加数，先取
a=0，依次加完b，则合成结果为：0,1,2,3，…，m；第二次a取1，则合成结果为1,2,3，…，m+1；
第三次a取2，则合成结果为2,3,4,……,m+2;……；直到第m+1次a取m，则合成结果为m，m+1，m+2，
m+3，……，m+m。因为每次递增1，所以，每次都连续，但是起点向后移动1个剩余类（同时结尾的
剩余类比上一组的最大值（怎么说呢？安余数0,1,2,3……，是可以比较大小的），直到最后一次
相加，最大余数是m+m=2m，也是模P中的最大余数，中间过程，每次递增1且连续，所以m+1次的合成
结果正好覆盖模P的所有剩余类（即从余数0到余数2m，P=2m+1），好了，对于模P的余数0至m的二元
运算mod(a+b,P)能覆盖所有的剩余类（即合成结果为模P的完全剩余系）已经简单精炼的进行了证明。
其实，如果用二维图形进行对角线证明更直观易懂。
P=2m+1
P的余数 0 1 2 3 占 占 占 占 m
0 0 1 2 3 4 5 6 占 m
1 1 2 3 4 5 6 占 占 m+1
2 2 3 4 5 6 占 占 占 m+2
3 3 4 5 6 占 占 占 占 m+3
占 4 5 6 占 占 占 占 占 占
占 5 6 占 占 占 占 占 占 占
占 6 占 占 占 占 占 占 占 占
占 占 占 占 占 占 占 占 占 占
m m m+1 m+2 m+3 占 占 占 占 2m
|
|
[复制链接]
IP卡
狗仔卡
发表于 2022-8-10 20:27
显身卡