代数数论——复数域上的数论

会写这个是因为前几天看到了 2019 年的集训队论文，于是学习了一下

这是前两天写的每日一题的具体解答：

给出两个复数 (x,yinmathbb Z[i])，请求出一对复数 (a,binmathbb Z[i])，使得 (|ax+by|) 非零且最小，输出这个最小值。(1leq|x|,|y|leq 10^9)。

sol.

这是一道论文题。题目来源：国家集训队 2019 论文集 ——「算法竞赛中一些数论问题的推广与高斯整数初探」李佳衡。

我们将说明如下的两个事实：在环 (mathbb Z[i]) 上贝祖（Bezout）定理成立；在环 (mathbb Z[i]) 上可以使用辗转相除法求得公约数。

若未声明，以下所有运算均在环 (R=(M,oplus,otimes)) 上进行，且不区分集合 (M) 与建立在 (M) 上的代数系统。

定义 1（公约数）. 设 (alpha,etain M)，若 (deltain M,deltamidalpha,deltamideta)，则称 (delta) 为 (alpha) 与 (eta) 的公约数。

定义 2（最大公约数）. 设 (alpha,etain M) 且不全为零元 (omicron)，若存在 (Deltain M) 满足 (Deltamidalpha,Deltamideta)，且对于任意 (alpha,eta) 的公约数 (delta) 都有 (deltamidDelta)，那么称 (Delta) 为 (alpha,eta) 的最大公约数，记做 (Delta=gcd(alpha,eta))。

注意到两个数的最大公约数可能有多个，它们都是相伴的（即互相等价）。

若未声明，以下所有运算均在环 (R=(mathbb Z[i],+, imes)) 上进行，且不区分集合 (M) 与建立在 (M) 上的代数系统。

定义 3（范数）. 称 (xinmathbb Z[i]) 的范数（norm）为 (N(x)=Re^2x+Im^2x=|x|^2)。

定理 1. 设 (alpha,etainmathbb Q[i])，则 (N(alphaeta)=N(alpha)N(eta))，若 (alphamideta) 则 (N(alpha)mid N(eta))。

定理 2. 设 (nin mathbb N)，则 (mathbb Z[i]) 中范数等于 (n) 的元素只有有限个。

以上两个定理的证明十分简单，这里略去。

定理 3（带余除法）. 设 (alpha,etainmathbb Z[i]) 且 (alpha eq 0)，那么存在 (eta,gammainmathbb Z[i])，使得

[eta=etaalpha+gamma,qquad 0leq N(gamma)<N(alpha) ]

Proof.

设 ( au=fracetaalpha=r+siinmathbb Q[i])，取 (u,vinmathbb Z) 为 ( au) 的实部和虚部四舍五入的结果，即使得 (|u-r|leq frac 12,|v-s|leq frac 12)。

记 (eta=u+viinmathbb Z[i])，则

[N( au-eta)=|u-r|^2+|v-s|^2leq(frac 12)^2+(frac 12)^2=frac 12 ]

又有 (gamma=( au-eta)alpha)，故而

[N(gamma)=N( au-eta)N(alpha)leqfrac 12N(alpha)<N(alpha) ]

以下记满足 (N(gamma)leqfrac 12N(alpha)) 的 (gamma) 为 (etamodalpha)。

定理 4（贝祖定理）. 对于不全为 (0) 的 (alpha,etainmathbb Z[i])，(Delta=gcd(alpha,eta)) 存在且存在 (x,yinmathbb Z[i]) 满足方程

[alpha x+eta y=Delta ]

Proof.

设 (S={alpha x+eta ymid x,yinmathbb Z[i]})，设其中范数最小的非零元素为 (delta)，于是由 (deltain S) 推知对于任意 (etamidalpha,etamideta) 都有 (etamiddelta)。

再设 ( uin S)，由定理 3，将 ( u) 表示为

[ u=etadelta+gamma,qquad 0leq N(gamma)<N(delta) ]

现在假定 (N(gamma) eq 0)，于是 (gamma= u-etadeltain S)，且 (0 eq N(gamma)<N(delta))，这与 (N(delta)) 最小矛盾，于是一定有 (gamma=0)。故而 (deltamid u)。现在注意到 (alpha,etain S)，于是 (deltamidalpha,deltamideta)，根据定义， (delta=gcd(alpha,eta))。

定理 5（辗转相除法）. 对于 (alpha,etainmathbb Z[i])，有

[gcd(alpha,eta)=gcd(eta,alphamodeta) ]

证明是显然的，这里略去。

那么本题的做法就很显然了：直接求出 (gcd(x,y)) 就是答案，这可以使用辗转相除法。因为每一次的余数都会严格下降一半，于是总复杂度是 (mathcal O(log N(xy)))。

Quite Easily Done.

以及一种特殊的模 (4) 意义下的狄利克雷特征函数：

[chi(n)= left{ egin{aligned} & 1 & nequiv 1pmod 4\ & -1 & nequiv 3pmod 4\ & 0 & otherwise end{aligned} ight. ]

这个函数有个性质：

定理 6. 设 (ninmathbb N)，(mathbb Z[i]) 中范数等于 (n) 的元素个数为：

[E(n)=4sum_{dmid n}chi(d) ]

证明可以参考另一篇论文「《整点计数》命题报告以及对高斯整数的若干研究」徐翊轩。