数学——数论--勒让德三平方和定理

勒让德三平方和定理（Legendre's three-square theorem）指出，如果自然数n可以写成$n = 4^a(8b+7)$的形式，其中a, b都是整数，那么自然数**无法**写成三个平方数之和的形式$n = x^2 + y^2 + z^2$。

比如数字7可以写成$4^a(8b+7)$的形式，并且7只能分解成 $$ 7=2^{2}+1{2}+1^{2}+1{2} $$ 一般能被4整除的数字是后两位可以被4整除，则数字可以被4整除。在计算机应用中可以借助位运算来进行加速判断，考虑二进制表示形式，如果一个数字可以被4整除，那么其最低的两个二进制位一定是0，换言之，如果数字可以被4整除，则必有(n & 3) == 0，证明：

• 考虑一个数字的二进制表示，如果最低为是1，那么代表这个数字是奇数，肯定不能被4整除
• 如果倒数第二位是1，最低位肯定是0，那么数字n可以写成：

$$n = a_{32} \times 2^{31}+a_{31} \times 2^{30} + \cdots + a_3 \times 2^2 + 2^1 + 0, a_i =0 或1$$

很显然n除以$2^2$必定会产生余数2，那么意味着数字n能被4整除，二进制最低的两位必然是0。

所以先把数字n里的4去掉的办法是：

while ((n & 3) == 0) n >>= 2;

接下来就是判断数字能否写成$8b+7$的形式，只需要将数字减7，然后和判断能否被4整除的方法类似，只需判断二进制后三位是否全为0即可。

while ((n & 3) == 0) n >>= 2;
if ((n - 7) & 7) //数字只能写成4个平方和的形式

解释为什么数字如果满足$n = 4^a(8b+7)$，只能写成4个平方和。因为如果数字可以写成两个数的平方和，那么只需要再增加一个0即可。