高斯整数的基本理论 / P2508 题解

esquigybcu · 2023-03-25 16:49:32 · 个人记录

先挖个坑。填完了记得找 wzy 让他把 P2508 这题所有没证明唯一分解的题解都毙了。

约定

## 定义形如 $a+bi$，其中 $a,b\in\mathbb{Z}$ 的复数称为**高斯整数** (Gaussian integer)，所有高斯整数的集合记作 $\mathbb{Z}[i]$. 对于 $a\in\mathbb{Z}$ 我们不区分 $a$ 与 $a+0i$.（也就是，所有整数同时是高斯整数。）请读者自行验证以下性质： * 高斯整数对于加法和乘法封闭。（任意两个高斯整数的和与积都是高斯整数） * 若 $ab=0$ 那么 $a=0$ 或 $b=0$. * 定义 $x=a+bi$ 的**共轭**是 $\bar x=a-bi$. * $a\in\mathbb{Z}$ 时 $\bar a=a

c=a+b \implies \bar c=\bar a+\bar b
c=ab \implies \bar c=\bar a\bar b
- 记 N(a)=a\bar a.
N(a)\in\mathbb{Z}_+
若 N(a)=0 则 a=0
N(a)=N(\bar a)
N(ab)=N(a)N(b)

如果高斯整数 a 满足存在 b\in\mathbb{Z}[i] 使 ab=1，那么称 a 为单位 (unit)。\mathbb{Z}[i] 的单位一共有 4 个，分别是 1,i,-1,-i. 如果两个高斯整数互相差一个单位因子（即存在单位 u 使 a=bu），则它们互为伴随 (associates)。

和整数的情况一样，如果存在高斯整数 c 使得 a=bc，那么称 b 整除 a，b 是 a 的因子。如果一个高斯整数 \pi 不是单位，且其所有因子都要么是单位要么是 \pi 的伴随，那么称它为既约元 (irreducible)。注意整数范围内的素数不一定还在 \mathbb{Z}[i] 中既约，例如 5=(2+i)(2-i).

带余除法

在 \mathbb{Z} 上，我们有：

对于所有 a,b\in\mathbb{Z}，b\ne 0，都存在 q,r\in\mathbb{Z} 使 a=bq+r 且 |r|<|b|.

类似地，在 \mathbb{Z}[i] 上，也有：

对于所有 a,b\in\mathbb{Z}[i]，b\ne 0，都存在 q,r\in\mathbb{Z}[i] 使 a=bq+r 且 N(r)<N(b).

证明：取 z=\frac{a}{b}=x+yi（注意 z 不一定是高斯整数）。令 q=\mathrm{round}(x)+\mathrm{round}(y)i，r=a-qb，其中 \mathrm{round} 是四舍五入。那么 |q-z|\le \frac{\sqrt{2}}{2}，|r|=|b|\cdot |q-z|\le\frac{\sqrt{2}}{2}|b|<|b|，N(r)<N(b). \square

这个证明中取四舍五入的本质就是要找到离 z 尽量近的 q. 正是因为 \mathbb{Z}[i] 在复平面上构成一个正方形晶格，我们才能找到足够近的 q，才有这个定理。

理想

一个子集 I\subseteq\mathbb{Z}[i] 被称为一个理想 (ideal)，如果 0\in I，a,b\in I\implies a+b\in I，且 a\in I,b\in\mathbb{Z}[i]\implies ab\in I.

对一个 a\in\mathbb{Z}[i]，a 生成的主理想 (principal ideal) 就是 a 的所有倍数的集合，即 \{ab|b\in\mathbb{Z}[i]\}，记作 (a). 类似地，我们也可以定义 (a_1,a_2,\cdots,a_n)=\{\sum_{j=1}^n a_jb_j|b_j\in\mathbb{Z}[i]\}.

请读者自行验证以下性质： * 若 $a\in I$ 那么 $-a\in I$. * $(a)=(b)$ 当且仅当 $a,b$ 互为伴随。具体地，$(a)=(1)$ 当且仅当 $a$ 是单位。 * $(a)\subseteq (b)$ 当且仅当 $b|a$. 接下来我们证明： > （$\mathbb{Z}[i]$ 是主理想整环）每个 $\mathbb{Z}[i]$ 的理想都是主理想。证明：设 $I\ne (0)$，那么存在 $a\in I$ 使 $a\ne 0$. 不妨取 $N(a)$ 最小的 $a$，那么 $(a)\subseteq I$. 反证，设 $I$ 不是主理想，那么存在 $b\in I\setminus (a)$. 作带余除法 $b=aq+r$，那么由理想的定义 $r\in I$，且 $r\ne 0$，$N(r)<N(a)$，与 $a$ 的定义矛盾！$\square

这个定理有一个重要推论：

（既约元是素元）若 p 是既约元，p|ab，那么 p|a 或 p|b.

证明：设 p\nmid a. 考虑 (a,p)，它是一个主理想，设它为 (x). 那么 (p)\subsetneq (a,p)=(x)，所以 x|p 但 x 不是 p 的伴随。由既约元的定义，x 是单位，所以 (a,p)=(1)，1\in (a,p). 由 (a,p) 的定义，存在 u,v 使 au+pv=1.

两边乘上 b，得到 (ab)u+p(bv)=b. 因为 p|ab，所以 p|\mathrm{LHS}，所以 p|b. \square

有了这个推论，就可以开始做唯一分解了。

唯一分解定理

（唯一分解定理）设 a\in\mathbb{Z}[i]，a\ne 0. 那么将 a 分解成既约元的乘积的方式，不计顺序和单位，是存在且唯一的。

这里“不计顺序和单位”的意义是“可以交换既约元的顺序，也可以将某几个既约元乘上单位，只要最后乘积不变”。

证明：存在性：对 N(a) 归纳。若 a 是既约元，那么自然存在。否则，设 a=bc，N(b),N(c)\in (1,N(a)). 由归纳假设 b,c 均可以分解成既约元的乘积，所以 a 也可以。

下面是重头戏。

唯一性：假设 a 有两种分解方式：

a=p_1p_2\cdots p_n=q_1q_2\cdots q_m

对 n 归纳。n=0 时 a=1，自然成立。否则，由上面的推论，存在 i 使 p_1|q_i. 由既约元的定义，p_1 和 q_i 是伴随。我们可以通过把这个单位转移给其他的因子的方式来让 p_1=q_i. 那么我们可以从两边同时消掉 p_1=q_i，由归纳假设剩下的部分也一样，所以这两种分解是一样的。 \square

高斯素数

因为“既约元”这个名字太拗口了，从下面开始我们管它叫“高斯素数”。（请注意，在某些环上这两个概念不等价。只有满足所有理想都是主理想的环上才能这么做。）

首先我们介绍一个初等数论中的引理：

设 p 是奇素数，那么存在 x\in\mathbb{Z} 使 x^2\equiv -1\pmod{p} 当且仅当 p\equiv 1\pmod{4}.

证明：\implies：(-1)^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1\pmod{p}. 那么因为 -1\not\equiv 1\pmod{p}，所以 2|\frac{p-1}{2}，4|p-1.

\impliedby$：设 $g$ 是模 $p$ 的原根，取 $x=g^{\frac{p-1}{4}}$ 即可。$\square

引理：

设 p 是奇素数，那么 p 不是高斯素数当且仅当 p\equiv 1\pmod{4}.

证明：\implies：设 \pi|p，\pi 是高斯素数。N(\pi)|N(p)=p^2，所以 N(\pi)=p. 所以 p 是两个整数的平方和，所以 p\equiv 0,1,2\pmod{4}. 但 2\nmid p，所以 p\equiv 1\pmod{4}.

\impliedby$：假设 $p$ 是高斯素数，设 $x^2\equiv -1\pmod{p}$. 那么 $p|(x+i)(x-i)$，但 $p\nmid x+i$，$p\nmid x-i$，矛盾。$\square

下面我们给出高斯素数一个完整的刻画。

设 \pi 是一个高斯素数。那么 \pi 满足下列之一：

\pi$ 是一个实素数且 $q\equiv 3\pmod{4}

证明：注意到 \pi|\pi\bar\pi=N(\pi)\in\mathbb{Z}_+. 由唯一分解定理，\pi 整除某个素数。设 \pi|p.

p\equiv 3\pmod{4}$：由上面知 $p$ 是高斯素数，$\pi=p$. $\square

回到原题

给定一个 n，我们要求出满足 N(a)=n 的 a 的个数。

设 n 的质因数分解是 2^\alpha (p_1^{\beta_1}p_2^{\beta_2}\cdots p_a^{\beta_a})(q_1^{\gamma_1}q_2^{\gamma_2}\cdots q_b^{\gamma_b})，其中 p_i\equiv 1\pmod{4}，q_i\equiv 3\pmod{4}.

考虑 a 的每个素数因子 \pi 对于 N(a) 的贡献。

\pi=1+i$：$N(\pi)=2
\pi\in\mathbb{Z}$：$N(\pi)=q^2$，其中 $q\equiv 3\pmod{4}

所以，不考虑单位的情况

每个 2 的情况是唯一的
每个 \equiv 1\pmod{4} 的质数 p_i 有 \beta_i+1 种方式（分别是 \pi^j\bar\pi^{\beta_i-j}，0\le j\le \beta_i）
每个 \equiv 3\pmod{4} 的质数 q_i，其指数 \gamma_i 必须为偶数，此时有一种情况；否则不可能有 N(a)=n.

到这里我们就完整地推导了 N(a)=n 有多少个解。根据唯一分解定理，N(a)=n 的解的个数就是每个质数的方案数的乘积。

注意题目给你的是 r，你要求的 n=r^2.

#include <stdio.h>
#include <string.h>
#include <algorithm>

typedef long long ll;

int main()
{
    ll n, ans = 4;
    scanf("%lld", &n);
    n *= n;

    while (!(n & 1)) n >>= 1;

    for (int i = 3; i * i <= n; i++)
        if (n % i == 0)
        {
            ll cnt = 0;
            if (i % 4 == 1)
            {
                while (n % i == 0)
                    n /= i, cnt++;
                ans *= cnt + 1;
            }
            if (i % 4 == 3)
                while (n % i == 0)
                    n /= i;
        }

    if (n != 1)
        if (n % 4 == 1)
            ans *= 3;
    printf("%lld\n", ans);
    return 0;
}