素数的判别与合数的分解问题 倪则均2015年9月26日（2014年7月3日投火花被压至今）

n123zj3

1，素数的生成，特性与分类。
在整个自然数里，偶素数只有一个2，奇素数却有无限之多。其实，所有的奇素数，它们全部都是由这个唯一的偶素数2所生成。显然，二项式2^n-1（n为全体的自然数）的全体素因子，就是整个自然数里的全部的奇素数，由于n无限，所以全体奇素数的数量也无限。或许这就是老子所说的：“道生一，一生二，二生三，三生万物”的道理。道为0，是唯一的一个无量数，由这个无量数生成最小的有量数1，由这个最小的有量数1生成唯一的偶素数2，由这个唯一的偶素数2生成最小的奇素数3，由全体素数生成整个自然数。
如果将奇素数表示为p，由于小于p的p-1个数都与p互素，它们构成一个循环群，专门称之为素数群表示为Φp。p-1必定是一个含有素因子2的合数，其p-1个全体剩余则构成一个素数环Hp-1。若是以Φp素数群里的p-1个元素作为底数，以Hp-1素数环里的p-1个数作为乘法幂次，那么它们的全体剩余则形成一个方阵。只要通过这个剩余方阵，即可证明Φp素数群与Hp-1素数环之间，具有多重形式的同构关系。例如Φp素数群里的φ（p-1）个原根，对应着Hp-1素数环里的φ（p-1）个欧拉数。
由于在所有的奇素数群里，2都是它们的一个次小的元素，因此，我们可以根据2在这些奇素数里的周期，而对全体的奇素数作出分类。第1类是2的周期为奇数的奇素数，它们是二项式2^u-1（u为奇数）的素因子，这是一些2j+1（j为4k-1形奇数）形素数；第2类是2的周期为单偶数的奇素数，它们是二项式2^u+1（u为奇数）的素因子，这是一些2j+1（j为4k+1形奇数）形素数；第3类是2的周期为双偶数的奇素数，它们是二项式22u+1（u为奇数）的素因子，这是一些4j+1形素数；…；第n+2类是2的周期为（2^2n）k偶数（k为奇数）的奇素数。
费马曾将全体奇素数划分成4k+1形素数，和4k-1形素数二个大类，这样的划分实在太粗，只能对于自然数作出一点比较简单的研究，例如关于平方和的研究。然而，如果我们要研究高次幂和的问题，就得按照上面的分类才能逐步予以深入。对于上述分类来说，由于2的指数里的u，可以取任意一个奇数，因此上述各类素数里的素数，它们的数量全部都有无限之多。由于2的周期里的2的指数里的n，可以取任意一个自然数，因此上述各类奇素数的类别也是无限之多。
2，合数环的分类，分析与分解。
在整个自然数里，合数的数量远比素数的数量多得多。但是，数量如此庞大的合数，却可以仅仅通过不多的几个合数环去予以认识。显然，上面我们所定义的Hp-1素数环，是一个极其重要的合数环，它是我们揭开素数神秘面纱的唯一的一个工具。由p1=2所开始的连续素数的乘积m=p1p2…pn所构成的合数环，称为规则合数环。这个规则合数环，则是我们认识自然数的重要工具。
由几个不同素数的乘积所构成的合数环，称为基本合数环，例如m=pq，p和q是两个不同的素数，则Hm合数环，就是一个最基本的合数环。而HM（M=psqt）合数环，则是这个最基本的Hm合数环的扩张环。各类的基本合数环只有一个，然而其扩张环却是数量无限的。对于这个最基本的Hm合数环来说，它实际上可以表示为Hp分环和Hm分环的笛卡尔乘积。Hm合数环里的pq个元素，与由Hp和Hm两个分环，所组成的pq个同余式组之间，是一种一一等同的关系。
Hm最基本的合数环里的元素a，它的同余式组式为a=〈a1，a2〉，即有a≡a1（mod p）和a≡a2（mod q），a1称为第一分量，a2称为第二分量。如果a1是φp素数群里的一个原根，a2是φq素数群里的一个原根，那么a=〈a1，a2〉必定是Hm最基本的合数环里的最大周期元素，其周期为p-1和q-1的最小公倍数。如果r1是Hp分环里2的周期，r2是Hq分环里2的周期，那么，Hm最基本的合数环里的2的周期r，为r1和r2的最小公倍数，即r=[ r1，r2]。
对于一个十分庞大的合数来说，我们首先应该运用下面传统的由大化小方法，将它分解成较小的奇合数m。如果2在这个Hm合数环里的周期为r，即2r≡1（mod m），那么，在 （ri是r的因子数）的因子数中，至少一个是可以整除m的，它们大都为素因子。但是，也可能还存在着一些2的同周期合数，需要予以判别再作进一步的彻底分解。

上面这个传统的由大化小的方法，是由许多不知名的数学家，他们默默探索整数分解的结晶，尽管没有什么高深的理论，但是，恰是非常行之有效。对于一个大数A=10x+y来说，我们只要观察其末位数，或截取其末位数来判断，即可知道它能否被下表里的P整除。如果A含有Pk，那么就要连续作k次判别，连续作k次去除，务必将这些素因子全部去除干净，得到一个不含这些素因子的奇合数。
3，2的同周期素数的判别及其合数的分解。
对于全体自然数来说，除了0，1，6三个数之外，其它所有的数都至少可以是一个奇素数的2的周期。0和1不能是任何奇素数的2的周期，是显而易见的事情，因为在最小奇素数3里，由于22≡1（mod 3），因此在最小奇素数3里，2的周期是2，不可能存在着大于3的奇素数，它们的2的周期会比2还小。
对于2^6-1=（2^3-1）（2^3+1）=32×7来说，由于在奇素数7里，2的周期是3，因此6不可能是任何奇素数里的2的周期，这是一个十分奇特的怪事，笔者不知应该如何予以解释。对于任意自然数n来说，二项式2^n-1的素因子之中，必定存在着2的周期为n的奇素数。从而证明，除了0，1，6三个数之外的所有的自然数，都至少可以是一个奇素数的2的周期。
如果p是一个素数，q=2p+1也是一个素数，那么2^p-1就必定是一个2的同周期的梅森合数，因此估计上述第1类奇素数里，2的同周期合数的数量无限。我们根据在整个自然数里，费马素数只有n＜5时的5个，可以估计到在上述各类奇素数里，都会有2的同周期合数存在。我们根据2^113-1=3391×23279×65993×1868569×1066818132868207，不难估计到2的同周期素数的数量也会有无限之多。
如果Y是n个2的同周期奇素数的乘积，那么在其HY合数环里，就会有2^n个元素的二次剩余为1，它们的同余式组里的n个分量不是1就是-1。因此，它们都是按照其大小而对称分布的，如果a^2≡1（mod Y），必定也有（Y-a）^2≡1（mod Y）。于是a-1与Y-a+1之间的一个最大公约数，跟a+1与Y-a-1之间的一个最大公约数，构成对于Y的一种分解。尽管1与Y-1的二次剩余也都为1，但是1-1=0，y-1+1=y，它们之间没有最大公约数，1+1=2，y-1-1=y-2仍为奇数，还是没有最大公约数，所以不能取1与Y-1作上述分解。显然我们只要作n-1次上述那样分解，即可将整个Y予以彻底的分解开来。
下面再介绍一种更为简洁的判别和分解的方法，如果2在因子数Y里的周期为ri，那么不管Y是素是合，Y-1总是可以被2ri整除，但是却不能被（2ri）^2整除。如果（Y-1）/2ri除以2ri的商为c，余数为b，那么，若是b^2-4c是一个平方数，则Y是一个合数，否则Y就是一个素数。如果Y是一个合数则可以分解为：
Y={ri[b-√(b^2-4c）]+1}{ ri[b+√(b^2-4c）]+1}。
这样的分解同样也只要作n-1次，也能将Y予以彻底的分解。