转载自某百度空间“素数分解为平方和”

定理&＃xff1a;设p是素数&＃xff0c;则p是两个数的平方和&＃xff0c;当且仅当p≡1 (mod 4)或p&＃61;2。

要由p≡1 (mod 4)推出p是两个数的平方和需要使用费马的无限下降算法&＃xff1a;设p≡1 (mod 4)&＃xff0c;目的是找出A²&＃43;B²&＃61;p的一组解。

1 先找出一组可行解满足A²&＃43;B²&＃61;Mp&＃xff0c;其中M2≡-1 (mod p)的某个解&＃xff0c;B取1。任取一个数1(p-1)/4 (mod p)&＃xff0c;则由24章的定理可知A²≡a^(p-1)/2≡(a/p) (mod p)&＃xff0c;即A²不是1就是-1&＃xff0c;而且概率都是50%。多取几次a&＃xff0c;必定能找到A²≡-1 (mod p)的解。

2 计算u≡A,v≡B&＃xff0c;且-0.5M<&＃61;u,v<&＃61;0.5M的u和v。

3 由于u²&＃43;v²≡A²&＃43;B²≡0 (mod M)&＃xff0c;可设u²&＃43;v²&＃61;Mr&＃xff08;1<&＃61;r

4 相乘&＃xff0c;即(u²&＃43;v²)(A²&＃43;B²)&＃61;M²rp。

5 上式可化为(uA&＃43;vB)²&＃43;(vA-uB)²&＃61;M²rp。

6 左右都除以M²&＃xff0c;得

((uA&＃43;vB)/M)²&＃43;((vA-uB)/M)²&＃61;rp。

可以证明M|uA&＃43;vB且M|vA-uB。

7 若r&＃61;1&＃xff0c;则算法结束&＃xff0c;否则转2.

算法每次都维护一组可行解A²&＃43;B²&＃61;Mp&＃xff0c;且每次执行都使得M单调递减。实际上&＃xff0c;可以证明r<&＃61;M/2&＃xff0c;即系数至少会折半&＃xff0c;因此总的运行次数是log级的。

对于任意整数a,如果a&＃61;p₁p₂&＃xff0c;且p_1,p₂都是符合上一章中分解条件的素数。设p₁&＃61;u²&＃43;v²,p₂&＃61;A²&＃43;B²&＃xff0c;则

a&＃61; (u²&＃43;v²)(A²&＃43;B²)&＃61;(uA&＃43;vB)²&＃43;(vA-uB)²

换句话说&＃xff0c;只要a分解质因数后所有的因子都是可分解的素数&＃xff0c;则a可分解为两个整数的平方和。

定理&＃xff1a;(a) 设m是正整数&＃xff0c;且m&＃61;p₁p₂…p_r&＃xff0c;其中p₁…p_r互不相同。则m可分解为两个整数的平方和当且仅当所有的p_i≡1 (mod 4)或等于2。

(b) m可写成m&＃61;a²&＃43;b² (其中gcd(a,b)&＃61;1)当且仅当它满足下列条件之一&＃xff1a;

(i) m是奇数且任何m的素因数模4余1

(ii) m是偶数&＃xff0c;m/2满足(i)。

再考虑一下勾股数&＃xff0c;可以得出结论&＃xff1a;

一个数c是一组本原勾股数中最大的数&＃xff0c;当且仅当c的素因数都模4余1。