一求素数及其幂的分拆——无穷递降法的问题 倪则均，2015年7月9日。

n123zj3

（西汉杨雄的《太玄经》上说：“夫物不因不生，不革不成。
故知因而不知革，物失其则；知革而不知因，物失其均。”）
1，费马的核心猜想。
1640年底，费马在给梅森的信中讲：形如p=4k+1的素数，可以唯一的表示为两个数的平方和。他说他能用无穷递降法予以证明，并且在1659年把这个证明的要点告诉了卡尔卡维。同时他断言，形如p=4k+3的素数，b1n6 不能表示为两个数的平方和。不仅如此，他还进行了推广：p=4k+1形素数的平方，也只能以一种方式表示为两个数的平方和，但这种素数的三次方或四次方就能以两种方式，表示为两个数的平方和。其五次方或六次方就能以三种方式，表示为两个数的平方和，如此类推。
费马从一般素数的分拆，进而研究四平方和问题，四平方和问题是数论中，第一个一般性的重要问题。巴歇在他出版的丢番图的《算术》中评注说，丢番图曾多次猜想到：每个正整数都能表示为四个数的平方和，但是巴歇不能证明这个问题。据说笛卡尔也研究过这个问题，然而，他不得不承认这个问题太难了。费马在巴歇的译本中说，他已经证明了一个一般的定理，由此可以推出四平方和猜想，他多次许诺发表证明细节，好象从未真正兑现过他的诺言。
实际上，在1638年左右，费马已在他的那本书上，提出了更为一般的重要定理：每个正整数或者本身是一个三角形数，或者是两个或三个三角形数之和；每个正整数或者本身是一个正方形数，或者是两个、三个或四个正方形数之和；每个正整数或者本身是一个五边形数，或者是两个、三个、四个或五个五边形数之和，如此等等。费马声称，他用无穷递降法证明了它们，很可能是言过其实。
后来，费马在1654年写给帕斯卡的一封信中谈到，为了证明这个一般性的定理，必须证明下面几个命题：①每个形如4k+1的素数等于两个整数的平方之和；②给定形如4k+1的素数，能找到一个普遍的方法求出两个整数，使其平方和等于该素数；③每个形如3k+1的素数均具有x2+3y2的形式；④每个形如8k+1或8k+3的素数均具有x2+2y2的形式；⑤不存在边长为有理数的直角三角形，使得其面积为完全平方数。
显然，命题①是一个存在性的问题，命题②是一个可算性的问题，既然你已经找到一个普遍的算法，可以将一个给定的4k+1形素数，分拆成为两个整数的平方和，那么其存在性还用再作证明吗？如果你非要再作存在性证明，那就是傻子买鞋了。一个傻子到鞋店里去试穿了一双新鞋，尽管十分合脚，但是他还是要将这双新鞋，与他原来的那双破鞋比较一下，尺寸大小只要稍有差别，他就决不敢买下这双十分合脚新鞋了。
其实，费马在此信中将他的核心猜想分成了两个命题，说明他根本没有真的证明了这些命题，因为只要解决了第二个命题，也就立即证明了第一个命题，根本不用再多费什么口舌。若是你花了九牛二虎之力，首先证明了第一个命题，那么你还得花更大的力气去解决第二个命题。由此可见，这种将核心猜想分成了两个命题的做法，实际上就是一种误导。有人说欧拉证明了费马这个核心猜想的逆命题，其实，上述这个核心猜想的逆命题应该是，如果两个数的平方和，可以唯一表示为一个非平方数，那么这个非平方数必定是一个p=4k+1形素数。
2，欧拉逆向证明的错误。
冯克勤写了一本《平方和》，对于表素数为二平方和的问题，此书一开始就抬出了高斯来吓人。他说是高斯首先确认了，欧拉对于下面的欧拉定理：素数p是二平方和的充分必要条件为p=2或p≡1（mod4）。（换句话说：素数p不为二平方和←→p≡3（mod4））的证明完全正确。然而，下面欧拉的证明却是完全错误，这个完全错误的证明，我们采用斜体抄录如下：
证明：“必要性的证明是容易的，由于2=1^2+1^2，以下设p是奇素数，如果p是二平方和，即p=x^2+y^2，其中x和y是整数，则x^2+y^2≡0（mod p），即x^2≡-y^2（mod p），易知y不整除p，于是同余式两边可同时除以y^2，得到(x/y)^2≡-1（mod p）。这意味着--1是模p的二次剩余，因此p≡1（mod 4），这就证明了必要性。
充分性的证明就困难多了，我们要证明当p≡1（mod4）时，p是二平方和。首先，由p≡1（mod4）知，-1为模p的二次剩余，即有整数a使得a≡-1（mod p），a所属模p同余类中每个整数均有这个性质，而这个同余类中总有一个整数的绝对值小于p/2，从而我们不妨假设│a│＜p/2。于是p│a^2+1，即a^2+1=mp，其中m为正整数，并且mp= a^2+1＜（p/2）^2+1＜p2，从而1≤m≤p-1。至此，我们证明了一个初步结果：在1，2，…，p-1当中存在整数m，使得mp为二平方和。
现在我们以m0表示使得m0p为平方和的最小正整数，由上面所证可知m0是存在的，并且1≤m0≤p-1。我们的目的显然要证m0=1（从而p为二平方和），证明用反证法：如果m0≥2，而m0p=x1^2+y1^2，其中x1和y1为整数，在x1和y1所属的模m0同余类中总可以分别取整数x0和y0，使得│x0│和│y0│均不超过m0/2（为什么可以这样做？），即x0≡x1，y0≡y1（mod m0），│x0│，│y0│≤m0/2。
如果x0=y0=0，则导致m0│p，但这与1≤m0≤p-1矛盾，因此x0和y0不全为零，即0＜x0^2+y0^2≤（m0/2）^2+（m0/2）^2=(m0^2)/2。由于x0^2+y0^2≡x1^2+y1^2=m0p≡0（mod m0），可知x0^2+y0^2=m＇m0，其中m＇为整数，并且由0＜x0^2+y0^2= m＇m0可知1≤m＇≤m0/2＜m0。再由恒等式得出m＇m0p=（x0^2+y0^2）（x1^2+y1^2）=（x0x1+y0y1）^2+（x0y1-y0x1）^2，但是x0x1+y0y1≡x1^2+y1^2≡0（mod m0），x0y1-y0x1≡x1y1-y1x1≡0（mod m0），因此A=（x0x1+y0y1）/m0和B=（x0y1-y0x1）/m0均是整数，并且A2+B2=m＇p，即m＇p也是二平方和，但是1≤m＇＜m0，这便与m0的最小性相矛盾。唯一的可能性便是m0=1，即p为二平方和，这就完成了定理的证明。”
3，这是费马的无穷递降法吗？
冯克勤接着指出：“上述证明的后一部分,采用的是费马首创的‘无穷递降法’，因为它的证明实质是：如果m0p为二平方和并且m0≥2，则求出另一正整数m1（=m＇），使得m1p也为二平方和。如果仍旧m1≥2，则按同样办法又找到正整数m2＜m1，使得m2p也为二平方和。……于是我们得到递降的正整数序列m0＞m1＞m2＞…。但它们均是正整数，从而不能无穷递降下去，所以必须经过有限步达到值1。我们以后在研究四平方和问题时还要用到这个方法。”
这个所谓的无穷递降法，不知是冯克勤，还是欧拉或高斯强加给费马的？当然这是一个完全错误的算法。因为对于xi^2+yi^2=mp（p为4k+1形素数）来说，其中的xi或yi可以是Φp素数群里的任何一个元素，这是由于如果将Φp素数群里的任何一个元素a，运用其原根表示为a≡g^r时，那么它的平方为a^2≡g^2r，则有a^2+g^（2r+2k）≡g^2r+g^（2r+2k）≡g^2r（1+g^2k）≡g^2r（1-1）≡0（mod p）。
然而其中的m应该是一个小于2（p-2）的4k+1形素数或2的幂，以及它们的积。这是由于p-1和p-2是Φp素数群里，最大和次大的二个元素，那么它们的平方和则为：（p-1）^2+（p-2）^2=2p^2-4p+5＜2p（p-2）。至于为什么m应该是一个4k+1形素数或2的幂，以及它们的积？我们只要反过来看，就会变得十分清晰明了。这也就是要知道当m是为什么数的时候，合数mp才能分拆成为二个数的平方和，这是我们以后要深入研究的问题，在此我们不妨先给出，这个m应该是一个4k+1形素数或2的幂，以及它们的积。下面我们不妨通过一个实例予以具体说明，对于Φ13素数群来说，则有
1^2+5^2=2×13，1^2+8^2=5×13，12^2+5^2=13×13，12^2+8^2=16×13，
2^2+3^2=1×13，2^2+10^2=8×13，11^2+3^2=10×13，11^2+10^2=17×13，
4^2+6^2=4×13，4^2+7^2=5×13，9^2+6^2=9×13，9^2+7^2=10×13。