高斯整数与平方和问题

---

1、Guassian Integers(高斯整数)

Definition 1.1
高斯整数是定义在复数域上的，实部和虚部均为整数的复数集，遵循复数运算法则

形式化的，我们把满足 $z=a+bi,其中a,b\in Z$ 的复数 $z$ 称为高斯整数（Guassian Integers）

Definition 1.2
定义高斯整数 $z=a+bi$ 的 norm(模长) 为 $N(z)=a^2+b^2$

特别地，定义 norm 等于 $1$ 的高斯整数为 unit(单位元)

Definition 1.3
对于高斯整数 $x,y$，若存在高斯整数 $a$ 使得 $ax=y$，则称 $x$ 为 $y$ 的因子，记作 $x|y$

Lemma 1.1
对于高斯整数$a,b$，$N(ab)=N(a)N(b)$

证明：设 $a=a_1+a_2 i$，$b=b_1+b_2 i$，则

$\begin{aligned}LHS&=(a_1 b_1 -a_2 b_2)^2+(a_1 b_2+a_2 b_1)^2=a_1^2 b_1^2+a_1^2 b_2^2+a_2^2 b_1^2+a_2^2 b_2^2 \\RHS&=(a_1^2+a_2^2)(b_1^2+b_2^2)=a_1^2 b_1^2+a_1^2 b_2^2+a_2^2 b_1^2+a_2^2 b_2^2\end{aligned}$

故$LHS=RHS$，引理成立

注：上述证明中，形如

$(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$

的式子称为斐波那契恒等式，根据该恒等式可以得到柯西不等式及其取等条件

Lemma 1.2
对于高斯整数 $a,b$，若 $a|b$，则 $N(a)|N(b)$，且逆命题不成立

证明：

• 证明命题成立，设 $b=az$，则 $N(b)=N(az)=N(a)N(z)$

故 $N(a)|N(b)$，命题成立

• 证明逆命题不成立，设 $N(b)=zN(a)$，而 $z$ 不一定能表示成 $N(z)$

的形式，故逆命题不成立

---

2、Gaussian primes(高斯素数)

Definition 2.1
若高斯整数 $z$ 不是单位元，且除自身及单位元外没有其他因子，则称 $z$ 为高斯素数（Guassian Prime Integers）

比如说 $2=(1+i)(1-i)$，故 $2$ 不是高斯素数

而 $3$ 不能继续分解，是高斯素数

Theorem 2.1
若素数 $P$ 满足丢番图方程 $x^2+y^2=P$ 无解，则 $P$ 为高斯素数

这个定理直接证比较困难，我们证明它的逆否命题：若 $P$ 不是高斯素数，则丢番图方程 $x^2+y^2=P$ 有解

• 证明必要性：设 $(a,b)$ 是丢番图方程 $x^2+y^2=P$ 的一组解，则

$P=a^2+b^2=(a+bi)(a-bi)$

$P$不是高斯素数

• 证明充分性：若 $P$ 不是高斯素数，设

$P=(x+yi)(a+bi)=ax-by+(bx+ay)i$

由于 $P$ 是整数，故 $ax-by=P$ 且 $bx+ay=0$，得到

$(a^2+b^2)x=aP$

由于 $a+bi$ 不是单位元，$a^2+b^2\neq 1$，且 $P$ 为素数，故 $a^2+b^2=P$

故$P$不是高斯素数时，方程有解

Lemma 2.1
若高斯整数 $z$ 满足 $N(z)$ 是素数，则 $z$ 是高斯素数

我们同样证明它的逆否命题：若 $z$ 不是高斯素数，则 $N(z)$ 不是素数

若 $z$ 不是高斯整数，则存在非单位元 $a,b$ 使得 $z=ab$

则 $N(z)=N(ab)=N(a)N(b)$，故 $N(z)$ 不是素数

Theorem 2.2（高斯整数的代数基本定理）
若 $z$ 是高斯整数，不考虑单位元的影响，存在唯一的高斯素数分解方式使得
$z=\prod z_i^{q_i}$

证明：根据代数基本定理，

$N(z)=\prod N(z_i)^{q_i}$

是唯一的，故 $z=\prod z_i^{q_i}$ 是唯一的

注：在代数基本定理中 $10=2\times5$，若考虑 $-1$ 的话 $10=(-2)\times(-5)$，分解不唯一，所以在代数基本定理中不考虑单位元 $\pm 1$ 的影响

类似的，这里也不考虑高斯整数单位元的影响

Lemma 2.2
$a^2+b^2\equiv 3(\bmod 4)$
恒不成立

证明：

• 若 $4\nmid a^2$，设 $a=\prod p_i^{q_i}$，则$a^2=\prod p_i^{2q_i}$，由欧拉定理得 $a^2\equiv \prod pi^{2q_i\%\phi(4)}\equiv \prod pi^{2q_i\%2}\equiv 1(\bmod 4)$

• 若 $4\mid a^2$，则 $a^2\equiv 0(\bmod 4)$

故 $a^2 \equiv 0,1(\bmod 4)$，得到

$a^2+b^2\equiv 0,1,2(\bmod 4)$

Lemma 2.3
若 $q$ 是素数，且 $q\equiv 3(\bmod 4)$，则 $q$ 为高斯素数

证明：设 $q=z_1 z_2$，且 $z_1=a+bi$，则

$N(q)=q^2=N(z_1)N(z_2)$

而 $N(z_1)=a^2+b^2\not\equiv 3(\bmod 4)$

故 $N(z_1)\neq q$，因此必然有 $N(z_1)=1$ 或 $N(z_2)=1$

Lemma 2.4
若 $q$ 为素数，且
$q\equiv 1(\bmod 4)$
则存在高斯素数 $z$ 使得 $q=z\overline{z}$

证明：由于 $q\equiv 1(\bmod 4)$，所以

$(-1)^{\frac{q-1}{2}}=1$

故 $-1$ 是模 $q$ 下的二次剩余，因此存在整数 $c$ 使得

$c^2\equiv -1(\bmod q)$

即 $q|(c+i)(c-i)$，但$(c+i)$ 和 $(c-i)$ 都不能整除 $q$，故 $q$ 不是高斯素数

因此存在 $z_1,z_2$，使得 $q=z_1 z_2$，而

$N(q)=q^2=N(z_1)N(z_2)$

故 $N(z_1)=N(z_2)=q$，所以 $z_1,z_2$ 互为共轭

---

3、Sum of squares(平方和问题)

Problem 3.1
求丢番图方程
$a^2+b^2=n$
的整数解 $(a,b)$ 的个数

设 $z=a+bi$，则 $z\overline{z}=a^2+b^2=n$，所以问题就变成了求乘积为 $n$ 的共轭高斯整数的数目

我们把 $n$ 按照如下方式分解：

$n=2^a \prod p_i^{q_i} \prod p_j^{q_j}$

其中 $p_i \equiv 1(\bmod4)$，$p_j \equiv 3(\bmod 4)$

那么我们只需要把这些因子划分成两部分使得这两部分乘积的 norm 相等，划分的方案数就是答案

由 Lemma2.3 可知，$p_j$ 已经是高斯素数，不能继续分解，只能均分到这两部分，显然如果存在$q_j$是偶数，则方程无解

由 Lemma2.4 可知，$p_i$ 可以继续分解为两个共轭高斯整数

设 $p_i=z\overline{z}$，则 $p_i^{q_i}=z^{q_i}\overline{z}^{q_i}$

而复数相乘满足 norm 相乘，辐角相加，故分配时 $z$ 与 $\overline{z}$ 对两边模长的贡献是相同的

所以只需要保证两边分配的 $z$ 和 $\overline{z}$ 的总数相同即可

例如 $5^2=(2+i)^2 (2-i)^2$，则分配方案如下：

• 左边：$(2+i)(2+i)$　　右边：$(2-i)(2-i)$

• 左边：$(2+i)(2-i)$　　右边：$(2-i)(2+i)$

• 左边：$(2-i)(2-i)$　　右边：$(2+i)(2+i)$

可以看出，$p_i^{q_i}$ 项共有 $(q_i+1)$ 种分配方案，所以 $\prod p_i^{q_i}$ 的贡献就是

$\prod(q_i+1)$

而在 Theorem2.2 中，我们提到高斯整数分解时可以通过乘以单位元得到不同的分解方案，例如

$\begin{aligned}5&=(2+i)(2-i)=(-2-i)(-2+i)\\&=(-1+2i)(-1-2i)=(1-2i)(1+2i)\end{aligned}$

在考虑单位元的情况下，每一种分解方案就有 $4$ 种分解方式，所以答案应该是

$4\prod(q_i+1)$

最后我们再考虑 $2^a$ 项的问题，注意到

$2=(1+i)(1-i)=i(1-i)^2$

所以只能把 $(1-i)$ 均等分配到两边，而 $i$ 作为单位元不影响答案，故 $2^a$ 只有一种分配方案

问题至此完美解决，最终的答案就是 $4\prod(p_i+1)$

---

4、Integral point on circles(圆上的整点)

BZOJ1041 圆上的整点
给定圆
$x^2+y^2=R^2$
求在圆周上有多少个点的横纵坐标都是整数

设 $R=2^a \prod p_i^{q_i} \prod p_i^{q_i}$，其中 $p_i \equiv 1(mod 4)$，$p_j \equiv 3(mod 4)$，则

$R^2=2^{2a}\prod p_i^{2q_i}\prod p_j^{2q_j}$

因为 $2q_j$ 为偶数，所以这一项不会导致无解

而 $2^{2a}$ 以及 $\prod p_j^{2q_j}$对答案无影响，所以答案就是

$4\prod (2q_i+1)$

具体做法就是分解质因数，找到形如 $4k+1$ 的质因子，计算次数即可，时间复杂度$O(\sqrt n)$

---

参考文献

• Gaussian Integers
• 隐藏在素数规律中的π
• Gauss整数学习笔记