定理：设p是素数，则p是两个数的平方和，当且仅当p≡1 (mod 4)或p=2。
要由p≡1 (mod 4)推出p是两个数的平方和需要使用费马的无限下降算法：设p≡1 (mod 4)，目的是找出A2+B2=p的一组解。
1 先找出一组可行解满足A2+B2=Mp，其中M<p。可以让A取x2≡-1 (mod p)的某个解，B取1。任取一个数1<a<p，计算A≡a(p-1)/4 (mod p)，则由24章的定理可知A2≡a(p-1)/2≡(a/p) (mod p)，即A2不是1就是-1，而且概率都是50%。多取几次a，必定能找到A2≡-1 (mod p)的解。
2 计算u≡A,v≡B，且-0.5M<=u,v<=0.5M的u和v。
3 由于u2+v2≡A2+B2≡0 (mod M)，可设u2+v2=Mr（1<=r<M）。
4 相乘，即(u2+v2)(A2+B2)=M2rp。
5 上式可化为(uA+vB)2+(vA-uB)2=M2rp。
6 左右都除以M2，得
((uA+vB)/M)2+((vA-uB)/M)2=rp。
可以证明M|uA+vB且M|vA-uB。
7 若r=1，则算法结束，否则转2.
算法每次都维护一组可行解A2+B2=Mp，且每次执行都使得M单调递减。实际上，可以证明r<=M/2，即系数至少会折半，因此总的运行次数是log级的。
对于任意整数a,如果a=p1p2，且p1,p2都是符合上一章中分解条件的素数。设p1=u2+v2,p2=A2+B2，则
a= (u2+v2)(A2+B2)=(uA+vB)2+(vA-uB)2
换句话说，只要a分解质因数后所有的因子都是可分解的素数，则a可分解为两个整数的平方和。
定理：(a) 设m是正整数，且m=p1p2…pr，其中p1…pr互不相同。则m可分解为两个整数的平方和当且仅当所有的pi≡1 (mod 4)或等于2。
(b) m可写成m=a2+b2 (其中gcd(a,b)=1)当且仅当它满足下列条件之一：
(i) m是奇数且任何m的素因数模4余1
(ii) m是偶数，m/2满足(i)。
再考虑一下勾股数，可以得出结论：
一个数c是一组本原勾股数中最大的数，当且仅当c的素因数都模4余1。