Gauss 二元型合成

共同中项让两个理想用同一条方向 ​

由 $B-b_i=2a_i{k}_i$，剪切 $T_{k_i}$ 将 $Q_i$ 变成

$C$ 确为整数：$B^2-D$ 分别被 $4a_1,4a_2$ 整除，而二者最小公倍数为 $4A$。

固定正虚部的 $\sqrt{D}$，令 $\eta =(B+\sqrt{D})/2$。两个型的理想现在有共同的第二基向量：

乘积由 $A,a_1\eta ,a_2\eta ,{\eta }^2$ 生成。因为 $gcd(a_1,a_2)=1$，Bézout 系数理路整数欧几里得算法Euclidean algorithm for integers反复使用带余除法计算最大公约数的有限算法。使 $\eta$ 本身也是 $a_1\eta ,a_2\eta$ 的整数线性组合；而

所以乘积精确等于

这条生成元等式认证了公式，而不只验证新型恰好有判别式 $D$。

表示数的乘法可以直接展开 ​

若共同中项下的两个表示为

则

对两边取范数并除以 $A$，得到

这解释了“合成”如何把两个表示相乘。若输入先经过换元，须先把表示坐标移到共同中项的两组基中，再使用这条式子。

完整算出 $D=-23$ 的乘法表 ​

约化已经列尽三个类，记为

先算 $A^2$。两个原始首系数都为二，先把第二个型用 $S$ 变成 $(3,-1,2)$。然后求

可取 $B=5$。两输入分别剪切为 $(2,5,6)$、$(3,5,4)$，乘积型为

再执行

故 $A^2=\bar{A}$。最终约化矩阵为 $S{T}_1=\left(\begin{array}{cc}0& -1\\ 1& 1\end{array}\right)$。

再算 $A\bar{A}$。将第二个型 $(2,-1,3)$ 交换成 $(3,1,2)$，共同中项可取 $B=1$，得到

所以 $A\bar{A}=e$。三类彼此不同，群律又已由理想对应保证，完整乘法表为

于是 ${\mathcal{C}}_{-23}\cong C_3$。这里既有穷尽代表的证据，也有群结构和生成元阶的证据。

不满足互素条件时，CRT 还不够 ​

若对 $(2,1,3)$ 自乘时直接令 $A=4,B=1$，两条模四同余虽都满足，却得到

输出甚至不是整数型。首系数不互素时，两个 $4a_i$ 的最小公倍数不再等于 $4a_1{a}_2$，前面的整除论证失效。更一般的合成公式确实可以处理这些输入，但本算法的修复方式明确：先换元得到互素首系数，再执行已证明的公式。

任意乘积恒等式不能定义正类合成 ​

若一条恒等式写成 $Q_1{Q}_2=Q_3(X,Y)$，也能写成

右边两个型可能并不正等价。$D=-23$ 的 $A$ 与 $\bar{A}$ 已给出这种真实区别，所以仅寻找一个双线性表示恒等式，不足以在二者间选择。固定复嵌入、正定向和理想乘法，才指定了正确的类。

本原表示也不一定在乘法后保持。例如 $D=-4$ 的 $x^2+y^2$ 在 $(1,1)$ 本原表示二，两份表示相乘时 $X=0,Y=2$，得到四的非本原表示。类乘法是良定义的，坐标是否互素仍须单独检查。

为什么总能把首系数变互素 ​

固定本原型 $Q$ 和正整数 $N$。我们要找 $gcd(x,y)=1$ 且 $gcd(Q(x,y),N)=1$ 的向量，再把它补成 $S{L}_2(\mathbb{Z})$ 矩阵的第一列。

对每个 $p\mid N$，在模 $p$ 下至少有一个向量使 $Q$ 非零。事实上，若 $(1,0),(0,1),(1,1)$ 三处都为零，就依次得到 $a=c=b=0(\mathrm{mod}p)$，与本原性矛盾。对每个素因子选一对这样的坐标，再用 CRT 拼成

还需要全局坐标互素，不能只检查模 $N$。先在 $y_0+M\mathbb{Z}$ 中选一个非零整数 $y$。对每个整除 $y$ 却不整除 $M$ 的素数 $q$，额外要求 $x\equiv 1(\mathrm{mod}q)$；这些模数与 $M$ 互素，CRT 再次给出 $x$。若 $p\mid y$ 且 $p\mid M$，原先 $Q(x_0,0)\not\equiv 0(\mathrm{mod}p)$ 已保证 $x_0\not\equiv 0(\mathrm{mod}p)$。因此没有素数同时整除最终 $x,y$。

这就得到所需本原向量。用 Bézout 系数补成首列矩阵后，新首系数为 $Q(x,y)$，与 $N$ 互素。若 $N=1$，直接用 $(1,0)$ 即可。计算两型合成时取 $N=a_1$，只改第二个型便够。

这个证明给出有限构造；也允许程序依次枚举本原向量直到成功。枚举方式的终止有了依据，但这里不声称它按输入位数具有多项式运行时间，避免把正定约化的速度误当成整个预处理的速度。

四种选择为什么都不影响输出类 ​

先看输入代表。由定向理想对应，正等价换元只将 $I_i$ 改成 ${\lambda }_i{I}_i$，所以乘积改成 $({\lambda }_1{\lambda }_2)I_1{I}_2$，理想类不变。这同时覆盖了寻找互素首系数时不同本原向量、不同 Bézout 补列的选择。

再看共同中项。两个 CRT 解相差 $2A\ell$；相应乘积型恰相差剪切 $T_{\ell }$，因为中项由 $B$ 变为 $B+2A\ell$，末项按相同判别式被唯一决定。它们属于同一正类。

最后看乘积理想的正定向基与约化过程。前者只改变型的正等价代表，后者无论使用哪张正确换元证书，都必须落到唯一的约化三元组。因此输入换元、补列、CRT 解及末端约化的全部自由选择都已被覆盖。

理想乘法的结合律、交换律和单位元通过双射直接传给型类。单位理想 $\mathcal{O}$ 的范数型就是上面的 $Q_0$；公式 $I_Q\overline{I_Q}=a\mathcal{O}$ 给出逆类 $(a,-b,c)$。不需要仅凭有限算例猜测群律。

类数相同与群结构相同是两个问题 ​

有限约化代表只回答“有几个类”，还须合成才能决定元素的阶。例如 $D=-84$ 的全部代表为

后三者都与各自中项反号的型正等价：中项为零时直接相同，$|b|=a$ 时一次剪切恢复，$a=c$ 时一次 $S$ 恢复。所以每个非单位类都为二阶，群是 $C_2\times C_2$，而非 $C_4$。

还可实际检查两个不同非单位类的乘积：$(2,2,11)$ 与 $(3,0,7)$ 取共同中项六，得到 $(6,6,5)$；再经 $S,T_1$ 得 $(5,4,5)$。这与四元群表一致，也检验了偶判别式及 $a=c$ 边界。

完整的 二元型类证书练习 将 $-23$ 的九格表、理想基转换和 $13$ 的指定型表示放在同一份可复算输出中，并迁移到 $-20$ 与 $-84$。