【学习笔记】高斯整数与 π

今天看了一个很经典的题目 link。

本博客会讨论一些与圆上整点技术相关的公式。

这十分有趣，所以就来整理一下：

求以原点为圆心，半径为 $\sqrt{R}$ 的圆的圆周上有多少个点的坐标均是整数。

1、找规律

不妨先打出前几项的表。

$1,4,0,4,8,0,0,4,4,8,0,0,8,0,0,4,0\cdots$。

令人惊讶的发现，当 $n=4k+3$ 且 $n$ 为质数的时候答案为 $0$，当 $n=4k+1$ 且 $n$ 为质数的时候答案不为 $0$。

2、性质

根据定义可知，原方程相当于是询问存在多少组整数解 (x,y)，满足 $x^2+y^2=r^2$。因为这样的点对实际上是在一个复平面上，如图：

不放在复平面上考虑这个问题：

$(x+yi)(x-yi)=x^2+y^2$，$x^2+y^2=R$。

所以我们可以把所有的 $R$ 表示为两个复数分解的形式。

考虑整数的分解是几乎唯一的。

即 $x=p1p2p3p4\cdots pn$，其中 $pi$ 是质数。那么我们只能同时将两个数乘 $-1$。

扩展到复数域上有 对于一个复数的分解，唯一能做的就是将两个数同乘 $-1,-i$。

现在来考虑原问题，即将 R 分解的问题。考虑到将 R 分解等价于将 R 的每个质因子分解。

考虑到一个性质即所有 $4n+1$ 型的质数可以被分解为 $(2n+i)(2n-i)$ 所以对于每个 $p^k$，可以为答案提供 $k+1$ 的贡献。另外对于 $4n+3$ 型整数，即高斯整数，如果数量为偶数，贡献为 $1$，否则贡献为 $0$。值得注意的是 $2$，它与 -i,-1 的意义相同，不造成贡献。

于是就得到了一个解决方案。