剩余类个数过半定理全覆盖定理

白新岭

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        占        占        占        m
1        1        2        3        4        占        占        占        m+1
2        2        3        4        5        占        占        占        m+2
3        3        4        5        6        占        占        占        m+3
占        占        占        占        占        占        占        占        占
占        占        占        占        占        占        占        占        占
占        占        占        占        占        占        占        占        占
m        m        m+1        m+2        m+3        占        占        占        2m
从这个二维图形对角线证明看，更是直观逼真，从左上角，到右下角，合成结果正好从0到2m（右上角到左下角的斜线方向上的合成结果一致，即余数相同）。
        如果把某一个剩余类i（0≤i≤m）换成j=i+m会如何呢？能覆盖所有剩余类吗？依法炮制，替换2，替换3，替换m个（能替换m+1个吗？答案是否定的，这也是这个定理的关键点，为什么？）。

白新岭

二维图形证明

白新岭

幺半群
幺半群，是指在抽象代数此一数学分支中，幺半群是指一个带有可结合二元运算和单位元的代数结构。

幺半群在许多的数学分支中都会出现。在几何学中，幺半群捉取了函数复合的概念。
定义
折叠综述
幺半群是一个带有二元运算*:M×M→M的集合M，其符合下列公理:结合律:对任何在M内的a、b、c，(a*b)*c=a*(b*c)。

单位元:存在一在M内的元素e，使得任一于M内的a都会符合a*e=e*a=a。

通常也会多加上另一个公理:

封闭性:对任何在M内的a、b，a*b也会在M内。

但这不是必要的，因为在二元运算中即内含了此一公理。

另外，幺半群也可以说是带有单位元的半群。

幺半群除了没有逆元素之外，满足其他所有群的公理。因此，一个带有逆元素的幺半群和群是一样的。

生成元和子幺半群

幺半群 M 的 子幺半群是指一个在 M 内包含着单位元且具封闭性(即若x,y∈N ，则 x*y∈N)的子集 N。很明显地， N 自身会是个幺半群，在导自 M 的二元运算之下。等价地说，子幺半群是一个子集 N ，其中 N=N ，且上标 * 为克莱尼星号。对任一于 M 内的子集 N 而言，子幺半群 N 会是包含着 N 的最小幺半群。

可交换幺半群

运算为可交换的幺半群称之为可交换幺半群(或较少地，称之为阿贝尔幺半群)。可交换幺半群经常会将运算写成加号。每个可交换幺半群都自然会有一个它自身的代数预序 ≤ ，定义为下:x ≤ y 当且仅当存在 z 使得 x+z=y。可交换幺半群 M 的序单位是一个在 M 内的元素 u ，其中对任一在 M 内的元素 x 而言，总会存在一个正整数 n 使得 x ≤ nu。这经常用在 M 是偏序阿贝尔群G 的正锥体的情况，在这种情况下我们称 u 是 G 的序-单位。有接受任何交换幺半群，并把它变成全资格阿贝尔群的代数构造;这个构造叫做格罗滕迪克群。

部分可交换幺半群

运算只对某些元素而不是所有元素是交换性的的幺半群是迹幺半群;迹幺半群通常出现在并发计算理论中。

折叠编辑本段性质
在一幺半群内，可以定义一元素x的正整数幂:x=x 及 x=x*...*x (乘上n次)，其中n>1。幂的规则x=x*x则是很明显的。

由定义可以证明其单位元e是唯一的。然后，对任一x，可以设x为e，则其幂的规则在非负幂中依然会是成立的。

逆元素:一元素x称为可逆，若存在一元素y，使得x*y = e且y*x = e。此一元素y便称做x的逆元素。结合律使得其逆元素(若存在)是唯一的。

若 y是x的逆元素，则可以定义x的负幂，以x=y及 x=y*...*y (乘上n次)，其中n>1。如此幂的规则在所有整数就都成立了，这也是为什么x的逆元素通常会写做x。所有在幺半群M内的可逆元素，和其自身的运算可组成一个群。在这意思之下，每个幺半群都含有一个群。

但并不是每个幺半群都包含在一个群内的。例如，绝对可能有一个幺半群，其两个元素a和b会有a*b=a的关系，即使b不是单位元。如此的幺半群是不可能包含于一个群内的， 因为在群里，两边一同乘a的逆元素，就会得到b = e的结果，但这不是真的。一个幺半群(M,*)若具有消去性，即表示对任何在M内的a、b、c，a*b = a*c永远意指b = c且b*a = c*a也永远意指b = c。一具有消去性的可交换幺半群总是可以包含于一个群内。这是为什么整数(加法运算下的群)可以由自然数(具有消去性的加法运算下的可交换幺半群)建立。但一具有消去性的不可交换幺半群则一定不可能包含于一个群之中。

若一幺半群有消去性且是有限的，它会是一个群。

一可逆幺半群为一幺半群，其任一在M内的a，总存在一唯一在M内的a，使得a=aaa且a=aaa。

一幺半群G的子幺半群是G的子集H，其包含有单位元，且若x、y属于H，则xy属于H。很清楚地，H本身也是个幺半群，在G的二元运算之下。

折叠编辑本段同余和商幺半群
幺半群同余是相容于幺半群乘积的等价关系。就是说它是子集

使得它是自反的、对称的和传递的(如同所有等价关系必须的那样)，还要有如果 且 对于所有 M 中的 x,y,u 和 v，则有 的性质。

幺半群同余引发同余类

而幺半群运算 * 引发在同余类上的二元运算 :

它是幺半群同态。它明显的也是结合的，所以所有同余类的集合也是幺半群。这个幺半群叫做商幺半群，可以写为

一些额外的符号是公用的。给定子集 ，写

对于引发自 L 的同余类的集合。在这个表示法中，明显的。但是一般的说， 不是幺半群。走相反的方向，如果 是商幺半群的子集，写

当然这只是 X 的成员的并集。一般的说， 不是幺半群。

明显的有 且。

折叠编辑本段同态
两个幺半群(M,*)和(M′，@)之间的同态是一个函数f : M → M′，会有如下两个性质:

f(x*y) = f(x)@f(y) 对所有在M内的x和yf(e) = e′ 其中e和e′分别是M和M′的单位元。

不是每一个群胚同态都会是个幺半群同态，因为它不一定会维持单位元。和上述不同，群同态的情况则会成立:群论的公理确保每一两群之间的群胚同态都会维持住单位元。对于幺半群，这不是永远成立的，而必须有另外的要求。

双射幺半群同态称做幺半群同构。

白新岭

实际上群的定义和性质是制约了它的发展，特别是封闭性上（组成的元素，经映射（或二元运算）必须在它之内），这样就把子集的好多特性就给抹杀了。还有单位元的要求，也是把不具有单位元的子集特性给抹杀在摇篮之中，束缚了群论在线性不定方程正整数解组数上的发展。

独舟星海

人们很少从排列组合，群论，二元运算上下功夫，所以，始终找不到“哥德巴赫猜想”的实质。

白新岭

在合成方法论中最重要的东西就是：剩余类个数与合成方法数的关系恒等式，找到此关系恒等式，就等于解决了此问题，所以，关键是通过二元运算，通过统计，获得：剩余类个数与合成方法数的关系恒等式

白新岭

设素数P≥3，当构成它的剩余类个数大于等于\({(P+1)}\over 2\)时，则二元合成能覆盖它的所有剩余类。
证明：设a1,a2，a3，.....，aj是它的剩余类j≥\({(P+1)}\over 2\)，我们取a1与每个元素作二元合成，则根据数论上定理，当遍历aj时，其运算结果也遍历j个不同的剩余类（经过数论简单推理可得），当与a2与每个元素进行二元合成时，同理遍历它j个不同剩余类，此时考虑a1与a2不是同一元素，则a1与a2二元合成结果必不完全相同，至少有一个不相同（合成结果中），同理用a3对其进行合成，会出现同样的结果。当aj也参与二元合成后，所合成不同元素最少是j+（j-1）=2j-1，第一个j表示由a1参与运算所得到的结果，（j-1）表示剩余元素（除了a1）参与运算时与a1合成的结果的最少能合成的元素个数，总共有j个元素与那个集合进行二元合成，用去1个元素后，还剩余（j-1）个元素要与那个集合中的元素进行二元合成，所以，当j个元素与j个元素合成时，最少能合成j+（j-1）种结果，此时j+（j-1）=2j-1，而j≥\({(P+1)}\over 2\)，带入后得到，最少能合成P个剩余类。
       定理得证，即当参与二元运算的元素个数大于等于（素数+1）的一半数量时，能合成它的所有剩余类，即合成结果全部覆盖它的完全剩余系。