两平方和定理

为什么3模4素因子只能成对进入 ​

先用二次剩余理路二次剩余Quadratic residue模奇素数同余于某个平方的非零剩余类。的已知判据：对奇素数 $q$，$-1$ 是模 $q$ 的平方，当且仅当 $q\equiv 1(\mathrm{mod}4)$。

若 $q\equiv 3(\mathrm{mod}4)$ 且 $q\mid x^2+y^2$，假如 $q\nmid y$，就能除以 $y^2$，得到 $(x{y}^{-1}{)}^2\equiv -1(\mathrm{mod}q)$，矛盾。因此 $q\mid y$，再由 $q\mid x^2$ 得 $q\mid x$。于是

每发现一个 $q$，实际都可以从两坐标中各提出一个 $q$，从总数中提出 $q^2$。反复执行，$n$ 中 $q$ 的指数只能为偶数。这证明了必要性，也给出无解时的短证书：指出某个3模4素数的指数为奇数即可。

从模平方根制造一个高斯因子 ​

现在令 $p\equiv 1(\mathrm{mod}4)$ 为素数，选整数 $t$ 使 $t^2\equiv -1(\mathrm{mod}p)$。在高斯整数环理路高斯整数的精确算术Gaussian integers · 高斯整数 · Gaussian integer arithmetic把整数格点看成可整除的复数，用范数下降计算GCD与Bézout系数，并以显式核验完成高斯商环中的约简和求逆。中计算

要证明 $N(\delta )=p$，必须排除两个极端：它不能是单位，也不能与 $p$ 互为单位倍。

若它是单位，Bézout等式给出 $1=up+v(t+i)$。两边乘 $t-i$；因为 $p\mid t^2+1$，右边都被 $p$ 整除，便推出 $p\mid t-i$。一个普通整数 $p$ 整除高斯整数时必须整除其两个坐标，可是这里虚部是 $-1$，矛盾。

若 $\delta$ 与 $p$ 互为单位倍，则由 $\delta \mid t+i$ 得 $p\mid t+i$，同样与虚部为一矛盾。另一方面，$\delta \mid p$，所以 $N(\delta )$ 是 $p^2$ 的正因子。排除 $1$ 和 $p^2$ 后，只剩

写 $\delta =u+vi$，就构造出 $p=u^2+v^2$。这个证明没有先猜平方和；GCD把一个模同余解变成了整数等式。

分裂表为什么没有遗漏 ​

范数为普通素数的高斯整数必不可约：若分成两个非单位，范数会把一个素数分成两个大于一的整数。高斯环是Euclidean域，因而是唯一分解整环理路唯一分解整环Unique factorization domain · UFD每个非零非单位元素都能唯一地分解为不可约元乘积的整环。，不可约元在这里也是素元。因此上面得到的 $\delta$ 及其共轭都是高斯素元。

它们不会相伴。若 $u+vi$ 与 $u-vi$ 相差 $\pm 1$ 或 $\pm i$，分别迫使一个坐标为零，或 $|u|=|v|$。前者使奇素数 $p$ 成为整数平方，后者使它等于 $2u^2$，都不可能。

若 $q\equiv 3(\mathrm{mod}4)$ 在高斯环可约，取非单位分解 $q=\alpha \beta$。范数乘积为 $q^2$，两个范数只能都为 $q$，于是 $q$ 是两平方和，与刚才的必要性矛盾。因此它不可约，也就是素元。对 $2$，直接用 $2=-i(1+i{)}^2$ 和 $N(1+i)=2$ 即可。

最后，任意高斯素元 $\pi$ 都整除整数 $N(\pi )=\pi \bar{\pi }$。将这个正整数分成普通素数，素元性迫使 $\pi$ 整除其中某一个。因此逐一分解普通素数已经覆盖全部高斯素元，不会还藏着第四类。

将素数答案拼成一般整数 ​

两个范数之积还是范数，展开就是

$2=1^2+1^2$，每个1模4素数刚才已构造为两平方和，而 $q^{2h}=(q^h{)}^2+0^2$。当所有 $f_k$ 为偶数时，对这些因子逐个使用乘法公式，便得到 $n$ 的表示，完成充分性证明。

$325=5^2\cdot 13$ 没有3模4素因子，因此可表示。实际计算

取范数就得 $325=1^2+{18}^2$。若将最后一个因子换成共轭，得到 $17+6i$，于是另有 $325={17}^2+6^2$。判定定理保证存在，但本身还没有数清全部表示；这由下一页承担。

$45=3^2\cdot 5$ 可表示，$21=3\cdot 7$ 不可表示。第二个例子还说明，仅检查 $nmod4$ 不够：$21\equiv 1(\mathrm{mod}4)$，却有两个各出现一次的3模4素因子。局部的模4筛选只提供必要条件，不等于完整素因子判定。

“可表示”也不等于“坐标互素”。$45$ 的任何表示都被 $3$ 同时整除。若要求本原表示，需另外禁止所有3模4素因子，并要求 $4\nmid n$；这个更严格的条件将在表示计数与本原性理路两平方和的表示计数与本原性Two-square representation count · Jacobi two-square formula · 两平方和表示数通过分配共轭高斯素因子的指数计数并枚举两平方和，区分有序带符号、本原和正无序表示，处理坐标轴与对角线的特殊轨道。中证明。

哪种证书能独立复查 ​

存在性证书最短可以只是整数对 $(x,y)$：核验 $x^2+y^2=n$ 即可，不需要相信找到它的过程。若还要解释如何生成，保留每个1模4素因子的模平方根、GCD除法等式和范数乘积，就能逐步检查构造。

无解证书则可给出 $n=q^{2h+1}m$，其中 $q\equiv 3(\mathrm{mod}4)$ 为素数且 $q\nmid m$。乘法核验、素性证书和一次不整除检验共同说明指数确实为奇数。不能只列出一个未经确认是素数的3模4因子，因为复合因子的指数没有同样作用。

一般整数的判定依赖它的素因子分解，不能把分解成本隐藏在“检查指数”四个字里。若已经给出 $-1$ 的模平方根，Cornacchia算法理路Cornacchia 算法：两平方和构造Cornacchia algorithm · Cornacchia sum-of-two-squares algorithm · Cornacchia 两平方和算法给定−1的模平方根，以截断欧几里得余数链构造本原两平方和，用余数和系数双不变量证明平方根阈值后的结果恰好等于模数。可以直接构造本原两平方和；这是另一种输入承诺，不意味着一般因数分解因此变得容易。