拉格朗日四平方和定理

· · 算法·理论

命题：任何正整数都可以写成四个整数的平方和。

1. 哈密顿数（四元数）

四元数有四个元（顾名思义）。

::::info[铺垫：二元数（高斯数）]{open} 二元数是复数，两个元为 1,i，其中 i^2=-1， 一般形式是 a+b\times i（a,b\in R），拥有一个共轭 a-b\times i。

:::info[为何共轭？] 注意到 (a+b\times i)+(a-b\times i)=2a，(a+b\times i)\times (a-b\times i)=a^2+b^2，均为实数。 ::: ::::

四个元为 1,i,j,k，i^2=-1,j^2=-1,k^2=-1。\

四元数 $a+bi+cj+dk$ 拥有一个共轭 $a-bi-cj-dk$，二者积为 $a^2+b^2+c^2+d^2$（自己算去，注意四元数**不满足乘法交换律**，别算错了），这也被称为四元数 $a+bi+cj+dk$ 的**模**，写作 $|a+bi+cj+dk|$。\ 四元数有**模长公式**：四元数 $A,B$ 满足 $|A|\times |B|=|A\times B|$。\ 所以\ $(x_1+x_2i+x_3j+x_4k)\times(y_1+y_2i+y_3j+y_4k)=(x_1y_1-x_2y_2-x_3y_3-x_4y_4)+(x_1y_2+x_2y_1-x_3y_4+x_4y_3)i+(x_1y_3+x_2y_4+x_3y_1-x_4y_2)j+(x_1y_4-x_2y_3+x_3y_3+x_4y_1)k$\ 从而根据模长公式，有\ $(x_1^2+x_2^2+x_3^2+x_4^2)(y_1^2+y_2^2+y_3^2+y_4^2)=(x_1y_1-x_2y_2-x_3y_3-x_4y_4)^2+(x_1y_2+x_2y_1-x_3y_4+x_4y_3)^2+(x_1y_3+x_2y_4+x_3y_1-x_4y_2)^2+(x_1y_4-x_2y_3+x_3y_3+x_4y_1)^2$\ **四个数的平方和乘四个数的平方和，还是四个数的平方和。** ### 2. 一个引理 对于任何奇素数 $p$，皆有 $x,y(0\le x,y\le\frac{p-1}{2})$ 满足 $p\mid x^2+y^2+1$。\ 首先，$0^2,1^2,\dots,(\frac{p-1}{2})^2$ 在模 p 的情况下互不相同。 :::info[证明]{open} 反证法。\ 如果存在 $0\le x\le y\le\frac{p-1}{2}$ 但是 $p\mid y^2-x^2$， 由于 $y^2-x^2=(y-x)(y+x)$，所以 $p\mid y-x$ 或 $p\mid y+x$。\ 但是 $0<y-x<y+x<p$，矛盾。 ::: 其次，$-1-0^2,-1-1^2,\dots,-1-(\frac{p-1}{2})^2$ 在模 $p$ 下也不一样。\ 但两组都是 $\frac{p+1}{2}$ 个数，合起来有 $p+1$ 个数。\ 那就一定有 $x^2\equiv -1-y^2 \pmod{p},p\mid1+x^2+y^2$。 ### 3. 化简问题 对于 $p=2$，显然有 $0^2+0^2+1^2+1^2=2$。\ 如果对于所有奇素数命题都成立，根据**四个数的平方和乘四个数的平方和，还是四个数的平方和**，就可以证明对任意正整数命题成立。 ### 4. 证明 "对于所有奇素数命题都成立" 首先，根据引理可知存在 $0\le x_i<\frac{p}{2}$，使得 $x_1^2+x_2^2+x_3^2+x_4^2=mp$（取 $x_1=0,x_2=1$ 就变成了那个引理）。\ 若 $m=1$ 则命题已成，否则：\ 因为 $mp<(\frac{p}{2})^2\times4=p^2$，所以 $m<p$。\ 现在，取 $y_i\equiv x_i\pmod{m}(i=1),y_i\equiv -x_i\pmod{m}(i=2,3,4),-\frac{m}{2}<y_i\le\frac{m}{2}$，则 $y_1^2+y_2^2+y_3^2+y_4^2=rm,0\le r\le m$，\ 若 $r=0$，则 $y_1=y_2=y_3=y_4=0，m\mid x_1,x_2,x_3,x_4,m^2\mid mp,m\mid p$，矛盾。\ 若 $r=m$，则 $y_1=y_2=y_3=y_4=\frac{m}{2},y_1^2\equiv y_2^2\equiv y_3^2\equiv y_4^2\equiv\frac{m^2}{4}\pmod{m^2}$，同样 $m^2\mid mp,m\mid p$，依然矛盾。\ 所以 $1\le r<m$。\ 现在，有 $z_1=x_1y_1-x_2y_2-x_3y_3-x_4y_4,z_2=x_1y_2+x_2y_1-x_3y_4+x_4y_3,z_3=x_1y_3+x_2y_4+x_3y_1-x_4y_2,z_4=x_1y_4-x_2y_3+x_3y_3+x_4y_1$。\ 易知 $m^2\mid z_i$，而且 $z_1^2+z_2^2+z_3^2+z_4^2=(x_1^2+x_2^2+x_3^2+x_4^2)(y_1^2+y_2^2+y_3^2+y_4^2)=rm^2p$。\ 所以 $u_i=z_i/p$ 则 $u_1+u_2+u_3+u_4=rp$，又 $r<m$，所以无穷递降法可知结论成立。