费马平方和定理 拉格朗日四平方和定理
费马平方和定理 费马平方和定理:奇质数能表示为两个平方数之和的充分必要条件是该质数被4除余1。
第一步 “如果两个整数都能表示为两个平方数之和,
则它们的积也能表示为两个平方数之和。”
第一步的证明是婆罗摩笈多-斐波那契恒等式的一种:
而若将 与· 互换位置,即可得 。 第二步
“如果一个能表示为两个平方数之和的整数被另一个能表示为两个平方数之和的素数整除,则它们的商也能表示为两个平方数之和。”
假设a^2 + b^2能被p^2+q^2整除,且后者为素数。则p^2 + q^2能整除
:(pb-aq)(pb+aq) = p^2b^2 - a^2q^2 = p^2(a^2+b^2) - a^2(p^2+q^2).
由于p^2+q^2是素数,因此它能整除两个因子之一。假设它能整除pb-aq 。由于 :(a^2+b^2)(p^2+q^2) = (ap+bq)^2 + (aq-bp)^2\,
可推出p^2+q^2能整除(ap+bq)^2。于是等式能被p^2+q^2的平方整除。两边除以(p^2+q^2)^2得:
因此其商能表示为两个平方数之和。
如果p^2+q^2能整除pb+aq,则利用等式
同样可证。
第三步
“如果一个能表示为两个平方数之和的整数被另一个不能表示为两个平方数之和的整数整除,则它们的商也必有一个不能表示为两个平方数之和的因子。”
假设x 能整除a^2+b^2,且其商的分解式为p_1p_2\cdots p_n。则a^2+b^2 = x p_1p_2\cdots p_n。如果所有的因子p_i都能表示为两个平方数之和,则我们可以用p_1、p_2、等等去除a^2+b^2,并使用第二步的结论,可得每一个商都能表示为两个平方数之和。除到只剩x 的时候,可得x 也能表示为两个平方数之和,矛盾。因此,如果x 不能表示为两个平方数之和,则至少有一个素数p_i 也不能表示为两个平方数之和。
第四步
“如果a 和b 互素,则a^2 + b^2的所有因子都能表示为两个平方数之和。”
这一步用到了无穷递降法。设x
是a^2+b^2
的一个因子。可记
:a = mx \pm c,\qquad b = nx \pm d
其中c 和d 的绝对值最多不超过x 的一半。可得:
a^2 + b^2 = m^2x^2\pm 2mxc + c^2 + n^2x^2 \pm 2nxd + d^2 = Ax + (c^2+d^2). 因此,c^2+d^2一定能被x 整除,设c^2+d^2 = yx。如果c 和d 不互素,则它们的[[最大公约数]]与x 互质 (否则它就能整除a 和b ,与我们假设它们互素矛盾〕。因此它们的最大公约数的平方能整除y (因为它能整除c^2+d^2),于是我们得到e^2+f^2 = zx,其中e 和f 互素,且z 不超过x 的一半,这是因为
如果c 和d 互素,则我们可直接使用c 和d ,不必转换成e 和f 。
如果x 不能表示为两个平方数之和,则根据第三步的结论,可知必有一个z 的因子不能表示为两个平方数之和;设它为w 。于是我们从x 推出了一个更小的整数w ,都不能表示为两个平方数之和,但都能被一个能表示为两个平方数之和的整数整除。由于这个无穷递降是不可能的,因此x 一定能表示为两个平方数之和。
第五步
“任何形为4n+1的素数都能表示为两个平方数之和。”
如果p=4n+1,则根据费马小定理可得
被p 除都余1。因此它们的差2^{4n} -1, 3^{4n} -2^{4n},\dots,(4n)^{4n} - (4n-1)^{4n}都能被p 整除。这些差可分解为a^{4n} - b^{4n} =(a^{2n}+b^{2n}/(a^{2n} - b^{2n}.
由于p 是素数,它一定能整除这两个因子之一〔以下称它们为“和因子”和“差因子”〕。如果它能整除任何一个“和因子”,则根据第四步的结论可得p 能表示为两个平方数之和〔由于a 和b 仅相差1,它们必然互素〕。而如果它能整除所有的4n-1个“差因子”
,则它也能整除4n-2个一阶差、4n-3个二阶差,依此类推。由于数列1^k, 2^k, 3^k,\dots的第k 阶差都等于k! ,于是第2n 阶差都等于(2n)!,显然它不能被p 整除。因此,p 不能整除所有的“差因子”,得证p 能表示为两个平方数之和。
拉格朗日四平方和定理 拉格朗日四平方和定理:每个正整数均可表示为4个整数的平方和。 1743
年,瑞士数学家欧拉发现了一个著名的恒等式: 根据上述欧拉恒等式或四元数的概念可知如果正整数 则其乘积表示成
4个整数的平方和即可。
1751年,欧拉又得到了另一个一般的结果。即对任意奇素数 ,同余方程 必有一组整数解 满足 (引理)。 和 能表示为
4个整数的平方和, 也能表示为4个整数的平方和。于是为证明原命题只需证明每个素数可以至此,证明四平方和定理所需的全部引理已经全部证明完毕。此后,拉格朗日和欧拉分别在1770年和1773年做出最后的证明。
根据上面的四平方和恒等式及算术基本定理,可知只需证明质数可以表示成四个整数的平方和即可。
,因此只需证明奇质数可以表示成四个整数的平方和。
根据引理一,奇质数p 必有正倍数可以表示成四个整数的平方和。在这些倍数中,必存在一个最小的。设该数为 。又从引理可知 。
证明m0不会是偶数
设 是偶数,且 。由奇偶性可得知必有两个数或四个数的
的奇偶性相同,
的奇偶性相同, 奇偶性相同。不失一般性设
均为偶数,可得出公式:
是正整数使得假设 可以表示成四个整数的平方和不符。
证明m0=1
现在用反证法证明 。设 。
不可整除xj 的最大公因子,否m0^2可整除m0p ,则得m0是p 的因子,但1
0
下面证明m1p 可以表示成四个整数的平方和,从而推翻假设。 用四平方和恒等式令∑zi^2=∑yi^2*∑xi^2,可知zj 是m0的倍数,令zj= m0tj, ∑zi^2=∑yi^2*∑xi^2m0^2∑ti^2=m0m1m0p∑ti^2=m1p
将模 的二次剩余有 个,分别为 。
若
则
是模 的二次剩余,选取 使得 不属于模 的二次剩余,则剩下 ,而模p 的二次剩余仍有(p+1)/2 ,定理得证。若 组,分别为
个,由于(p+1)/2>(p-1)/2 ,根据抽屉原理,存在