高斯整数的精确算术

最近格点提供下降量 ​

Euclidean域理路欧几里得整环Euclidean domain带有允许带余除法并严格下降的欧几里得函数的整环。页已经证明：把 $\alpha /\beta$ 的实部、虚部分别舍入到最近整数，得到 $q\in \mathbb{Z}[i]$，余数 $r=\alpha -q\beta$ 满足

原因是两个坐标的舍入误差各不超过 $1/2$，误差范数至多 $1/4+1/4$。恰在两整数中间时任选一个都合法，因此商和余数不必唯一。

这个界让计算可以一直往前走：将 $(\alpha ,\beta )$ 换为 $(\beta ,r)$，共同因子完全不变，而非零余数的范数严格下降。最后一个非零余数就是GCD。逐步回代余数等式，还得到

于是“确实整除两输入”和“一切共同因子都整除它”都有可检查证据。前一项由两个商验证，后一项由这个Bézout等式验证。

两步除法得到一个素数范数 ​

取 $\alpha =29,\beta =12+i$。第一商的精确值是

最近格点为 $q=2$，于是

再算

所以可取 $\delta =5-2i$。完整证书是

这三条等式只需整数乘加就能复核。它们不仅返回一个数，还解释了为什么任何别的共同因子也必须整除这个数。

范数会丢掉方向 ​

由 $\beta \mid \alpha$ 可以推出 $N(\beta )\mid N(\alpha )$，反向却不成立。例如 $5+2i$ 与 $5-2i$ 的范数都为 $29$，但

所以一个不整除另一个，它们也不是单位倍。只记录长度，会把这两个不同的素因子混在一起。

类似地，$N(gcd(\alpha ,\beta ))$ 一般不等于整数 $gcd(N(\alpha ),N(\beta ))$。取上面两个共轭数：它们的高斯GCD是单位，但范数的整数GCD是 $29$。高斯GCD为单位可直接由

核验；这条等式也由配套脚本检查。

将一个高斯商环化为普通模算术 ​

仍取 $\delta =5-2i$。在商环理路商环Quotient ring按理想的陪集构造的环。 $\mathbb{Z}[i]/(\delta )$ 中，$5-2i=0$，所以应把 $i$ 换成模 $29$ 的 $-12$。定义

因为 $(-12{)}^2\equiv -1(\mathrm{mod}29)$，这个代入尊重加法和乘法；普通整数已覆盖全部余类，所以映射满射。

核恰好是 $(\delta )$。一方面 $\varphi (\delta )=29\equiv 0$，故每个 $\delta$ 的倍数都在核里。另一方面，若 $a-12b\equiv 0$，则

的两个分子都被 $29$ 整除。因此核中的元素确实都是 $\delta$ 的倍数，得到

这给出可执行的约简规则，不只是一张抽象同构图。

例如 $3+i$ 对应 $20(\mathrm{mod}29)$，而 $20\cdot 16\equiv 1$。于是 $16$ 是 $3+i$ 在该商环中的逆元，并有原环证书

换成模 $(2)$ 就不能宣称商环仍是域：$1+i$ 的类非零，但 $(1+i{)}^2=2i\equiv 0$，出现了非零幂零元。模数的范数大于一，并不足以保证商环为域。

从算术走向整数表示 ​

范数乘法把高斯因子变成两平方和。上面的GCD立即交付 $29=5^2+2^2$。两平方和定理理路两平方和定理Sum of two squares theorem · Fermat–Euler two-square theorem · 两平方和判定以3模4素因子的指数奇偶性判定正整数是否为两平方和，并用高斯GCD证明1模4素数的表示与素因子分裂。会说明哪些整数能这样表示；表示计数理路两平方和的表示计数与本原性Two-square representation count · Jacobi two-square formula · 两平方和表示数通过分配共轭高斯素因子的指数计数并枚举两平方和，区分有序带符号、本原和正无序表示，处理坐标轴与对角线的特殊轨道。进一步利用“两个共轭方向不能混同”来列出所有答案。