费马平方和定理
任意被4除余1的素数p,都可表示为两个平方数之和.
记为,p≡1(mod4)<=>p=x^2+y^2,x,y∈Z+.
Brahmagupta-Fibonacci恒等式
(a^2+b^2)(c^2+d^2)=(ac-bd)^2+(ad+bc)^2
---------------------~----------------------
(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2
证明,示下：
1.根据Brahmagupta-Fibonacci恒等式,任何两个被4除余1的素数的积也都能表示为两个平方数的和.
2.如果,一个能表示为两个平方数之和的整数被另一个能表示为两个平方数之和的素数整除,则他们的商也能表示为两个平方数之和.
假设,a^2 + b^2能被p^2+q^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得：
(a^2+b^2)/(p^2+q^2)=((ap+bq)/(p^2+q^2))^2+((aq-bp)/(p^2+q^2))^2
因此,其商能表示为两个平方数之和.
如果,p^2+q^2能整除pb+aq,则利用等式
(a^2+b^2)(q^2+p^2)=(aq+bp)^2+(ap-bq)^2,同理可证.
3.如果一个能表示为两个平方数之和的整数被另一个不能表示为两个平方数之和的整数整除,则他们的商也必有一个不能表示为两个平方数之和的因子.
假设x能整除a^2+b^2,且其商的分解式为,p1p2...pn,则,a^2+b^2=xp1p2...pn,
如果,所有的因子pi都能表示为两个平方数之和,则我们可以用p1,p2等去除a^2+b^2,并使用第二步的结论,可得每一个商都能表示为两个平方数之和
除到只剩x的时候,可得x也能表示为两个平方数之和,矛盾.
因此,如果x不能表示为两个平方数之和,则至少有一个素数,pi亦不能表示为两个平方数之和.
4.如果,a,b互为素数,则a^2+b^2的所有因子都能表示为两个平方数之和.
这一步用到了无穷递降法,设x是a^2+b^2的一个因子,可记为：
a=mx±c,b=nx±d
其中,c和d的绝对值最多不超过x的一半,可得：
a^2+b^2=m^2x^2±2mxc+c^2+n^2x^2±2nxd+d^2=Ax+(c^2+d^2)
因此,c^2+d^2一定可以被x整除.
设,c^2+d^2=yx
如果,c和d不互为素数,则他们的最大公约数与x互质（否则,他与x的最大公约数就能整除a和b,与我们假设,他们互素矛盾）.
因此,他们的最大公约数的平方能整除y（因为,他能整除c^2+d^2）,于是,我们得到:
e^2+f^2=zx
其中,e和f互为素数,且z不超过x的一半,这是因为：
zx=e^2+f^2<=c^2+d^2<=(x/2)^2+(x/2)^2=(1/2)x^2
如果,c和d互为素数,则,我们可以直接使用c和d,不必转换为e和f.
如果x不能表示为两个平方数之和,则根据第三步的结论,可知必有一个z的因子不能表示为两个平方数之和,设,他为w
于是,我们从x推出了一个更小的整数w,都不能表示为两个平方数之和
但都能被一个能表示为两个平方数之和的整数整除
由于这个无穷递降是不可能的
因此,x一定能表示为两个平方数之和.
5.任何形如,4n+1的素数,都能表示为两个平方数之和.
如果,p=4n+1,则,根据费马小定理,可得：
1,2^4n,3^4n,...,(4n)^4n被p除都余1
因此,他们的差2^4n-1,3^4n-2^4n,...,(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个“差因子”,2^2n-1,3^2n-2^2n,...,(4n)^2n-(4n-1)^2n
则他亦能整除4n-2个一阶差,4n-3个二阶差,依此类推.
由于,数列1^k,2^k,3^k,...之第k阶差都等于k!,于是,第2n阶差都等于2n.
显然,他不能被p整除,因此,p不能整除所有的“差因子”.
得证.