零 . 引入

我在晚自习想到了这样一个问题：
对于任意正整数 $n$ , 在平面直角坐标系中是否都存在一个以 $d$ 为半径，原点为圆心的圆，满足圆周上恰有 $4n$ 个横纵坐标都为整数的点？
尝试构造，$n=1,2,3,4,5$，我都顺利给出了构造，后面的数太大了，我没有继续构造，但是能感觉到我的猜想是正确的。
尝试证明，毫无头绪。
回去问了下 Gemini ，直接甩了个构造给我—— $d^2=5^{k-1}$ 。
了解了一下背后的原理，于是有了这篇文章 。

一 . 你真的懂质因数分解吗？

小学的时候，我们都学过任意大于 $1$ 正整数都可以写作若干个质因数的乘积，这就是著名的 唯一分解定理 ，由 欧几里得 在约 2300 年前提出。但是这么多年来，我都没有意识到一个问题，我根本就不会证 这个定理。那它究竟怎么证呢？

1 . 带余除法

当你在分解质因数时，你究竟在干什么？—— 除法。

这是分解质因数最本质的操作，能整除的就除，不能整除的我们就过。这就是我们接下来证明的地基中的地基 —— 带余除法。

其中， $0\le R < |B|$，是一个非常有趣的条件，也很重要。

2 . 辗转相除法

有了带余除法，我们就有了接下来一个很重要的东西——辗转相除法 。继续沿用上述记号，即：

接下来我会给出一个严格证明：

要证最大公因数相同，我们干脆直接证明这二者的公因数集相同。

Step1. 证明 $A$ 和 $B$ 的公因数，必然也是 $B$ 和 $R$ 的公因数。

Step2. 证明 $B$ 和 $R$ 的公因数，必然也是 $A$ 和 $B$ 的公因数。

（最喜欢证明不写汉字了！）

由于余数 $R$ 严格单调递减且恒非负（$B > R_1 > R_2 > \dots \ge 0$），该算法必然在有限步内终止于余数为 $0$，此时的除数即为最大公约数。这就是为什么我说 $0\le R < |B|$，是一个非常有趣的条件。

3 . 裴蜀定理 (Bezout’s Theorem)

对于不全为零的任意整数 $a$ 和 $b$，必然存在整数 $x$ 和 $y$，使得：

事实上由辗转相除法的逆过程容易构造 $x,y$，这就是著名的扩展欧几里得算法。

其实还有一种非构造性证明，但是感觉写出来的话就太败味了，过于冷峻了，就不写了。

4 . 欧几里得引理

定理内容： 如果一个素数 $P$ 整除乘积 $A \cdot B$（记作 $P \mid AB$），那么 $P$ 必然整除 $A$，或者 $P$ 必然整除 $B$。

看上去好像很显然啊，自己来试试证明？

利用裴蜀定理确实很ez，偷个懒，不证了。

5.你终于会证明唯一分解定理了

假设一个数字 $N$ 有两种不同的质数分解方式：
看等式最左边的 $p_1$。显然，$p_1$ 整除整个式子，所以 $p_1$ 也必须整除右边的乘积 。
根据第欧几里得引理：既然 $p_1$ 整除一堆数字的乘积，它必然整除其中的某一个。
但是 $p_1$ 和 $q_1$ 都是质数，只能被 1 和自己整除。所以 $p_1$ 整除 $q_1$ 的唯一可能就是：既然它们相等，我们就可以在等式两边同时把它们约掉。接着拿 $p_2$ 去找 $q_2$……一直约下去。最终你会发现，这两组质因数分解不仅素数的种类一模一样，连个数也一模一样，只不过是排列顺序不同罢了。唯一性得证。

二 . 唯一分解定理可以扩展吗？

确实可以！

这一次我们把目标锁在一种特殊的复数上 —— 高斯整数。

我们定义集合 $\mathbb{Z}[i] = \{a+bi \mid a,b \in \mathbb{Z}\}$，也就是实部和虚部都是整数的复数，这被称为“高斯整数”。

Step1.

带余除法的核心条件是什么？在普通的整数里，求两个数的 GCD用的是辗转相除法。给定两个数 $A$ 和 $B$（假设 $A>B$），我们可以做到：这里的核心要求是：$|R| < |B|$。只有余数不断严格变小，辗转相除法才一定会停止，最终找到最大公约数。现在把战场转移到复平面上的高斯整数 $\mathbb{Z}[i]$。对于任意两个高斯整数 $A$ 和 $B$（$B \neq 0$），我们想做除法 $A \div B$。我们要找一个商 $Q$ 和一个余数 $R$（它们都必须是高斯整数），使得：并且要求：余数 $R$ 的“范数”（距离原点的距离平方）必须严格小于 $B$ 的范数。即：$N(R) < N(B)$。如果这件事对任意 $A$ 和 $B$ 都做得到，那么高斯整数的辗转相除法就成了，唯一分解也就保住了。

Step2.

如何在高斯整数里寻找商 $Q$？在复数域中，真正的精确除法是 $A/B$。为了得到高斯整数的商 $Q$，我们的想法很简单：类比整数，只不过这里平面是有向的，所以“四舍五入”，找离这个精确值 $A/B$ 最近的高斯整数作为 $Q$。我们可以把余数 $R$ 变形一下：两边同时取范数（即求距离的平方），因为复数乘法的模长等于模长的乘积，所以：现在目标非常明确了：要想让 $N(R) < N(B)$ 严格成立，我们必须保证 $N(\frac{A}{B} - Q) < 1$。
翻译成几何语言就是：在复平面上，任意一个精确的复数 $A/B$，到它最近的高斯整数 $Q$ 的距离的平方，必须严格小于 $1$。

Step3.

高斯整数 $\mathbb{Z}[i]$ 在复平面上构成了一个什么图形？

答案是：边长为 1 的正方形网格。

想象复平面上随便丢下一点 $P$ 代表精确值 $A/B$。

这个点必然落在某个 $1 \times 1$ 的正方形格子内部或边界上。

这个格子的四个顶点，就是候选的高斯整数商 $Q$。

点 $P$ 距离正方形四个顶点中最远的距离，发生在 $P$ 恰好位于正方形正中心的时候。边长为 1 的正方形，中心到顶点的距离是：所以，无论 $P$ 落在哪里，它到最近顶点的距离的平方（即范数）最大也就是 $0.5$。因为 $0.5 < 1$，所以：将这个不等式代回余数的公式：证明完成！

小问题

按照刚刚的说法，四个格点都是候选商，这样除法的结果并不唯一啊？这怎么会是对的呢？

其实，能够辗转相除的核心在于过程是否有限，而在刚刚的情景当中，范数是在不断递减的，并且递减有限值，因此四个点确实都可以来作为商。

三 . 终于结束了

还记得我们最开始的问题吗？

现在我们终于有能力来解决它了。

首先我先给出给出一个公式：

设整数 $N$ 的标准素因数分解为：其中：$p_i$ 是模 4 余 1 的质数，$q_j$ 是模 4 余 3 的质数。

关于不定方程 $x^2 + y^2 = N$ 的整数解的数量（记为 $r_2(N)$），有一个非常优美的结论：

1.如果存在某个模 4 余 3 的质数 $q_j$，其指数 $c_j$ 是奇数，那么这个方程无解，即圆上没有整点，$r_2(N) = 0$。

2.如果所有模 4 余 3 的质数 $q_j$ 的指数 $c_j$ 都是偶数 ，那么圆上整点的数量完全由模 4 余 1 的质数决定，公式为：
那我们如何来理解呢？

首先，你在平面直角坐标系上找 $x^2+y^2=n$ 的整点，等价于在高斯整数里寻找所有的 $z$，使得 $N(z) = n$。

这就等价于看高斯分解中有多少种大小为 2 的划分使得 $z \cdot \bar{z} = N$，其中 $z$ 指划分的乘积。

这是一个组合计数问题，而且是个相对简单的组合计数。

我们分类讨论：

1.

对于 $q_j$：它没法分裂。如果 $z$ 拿了 $q_j^m$，那么 $\bar{z}$ 必定也包含 $q_j^m$。所以 $z \cdot \bar{z}$ 中必定包含 $q_j^{2m}$。

这意味着：$N$ 中 $q_j$ 的指数 $c_j$ 必须是偶数。

如果 $c_j$ 是奇数，方案数为 $0$。如果 $c_j$ 是偶数，那么 $z$ 拿走一半，只有 $1$ 种拿法。

2.

对于 $2$：$z$ 必须拿走 $(1+i)^a$。因为 $(1+i)$ 和它的共轭 $(1-i)$ 只差一个单位元，分配给 $z$ 和 $\bar{z}$ 本质上不会产生新的组合分支。所以它的分配方案数也是 $1$ 种。

3.

对于 $p_k$ ：$N$ 中包含了 $b_k$ 个 $\pi_k$ 和 $b_k$ 个 $\bar{\pi}_k$。

为了让 $z \cdot \bar{z}$ 能够凑出这 $2b_k$ 个因子，你可以让 $z$ 拿走 $u$ 个 $\pi_k$ 和 $v$ 个 $\bar{\pi}_k$。

显然，$\bar{z}$ 就必须拿走 $u$ 个 $\bar{\pi}_k$ 和 $v$ 个 $\pi_k$。

要凑成 $N$，必须满足：$u + v = b_k$。

由于 $u$ 和 $v$ 都是非负整数，这个方程有多少组解？

显然 $u$ 可以取 $0, 1, 2, \dots, b_k$。一共 $b_k + 1$ 种选择。

连乘即可。

四. 后记

本来还想再聊一聊更深刻一点的代数数论，精力有限，以后再说吧。

完结撒花！