密码学数学基础 笔记 3：从对加减法封闭的整数集合出发，证明素因数分解的唯一性，再讨论最大公因数与最小公倍数

整数模与算术基本定理

前面已经证明，每个大于 $1$ 的整数都可以分解为素数的乘积。这一篇补上唯一性的证明

关键是先理解整数线性组合构成的集合，由此得到 Bézout 等式，再证明一个素数整除乘积时，必然整除其中某个因子

整数模

讲义中的 modulus 指一个对加法、减法封闭的非空整数集合，本文称为整数模。这里的“模”是集合的名称，需要与同余式中“模 $n$”的整数 $n$ 区分

具体来说，非空集合 $S\subseteq\mathbb{Z}$ 是整数模，要求

$$m,n\in S\quad\Longrightarrow\quad m+n\in S,\ m-n\in S$$

例如：

• $\{0\}$，称为零模
• 全体整数 $\mathbb{Z}$
• 某个正整数 $d$ 的所有整数倍，即 $d\mathbb{Z}=\{dk:k\in\mathbb{Z}\}$

用群论的语言说，这些集合就是整数加法群的子群

基本性质

由于 $S$ 非空，可以取 $a\in S$。于是

$$0=a-a\in S,\qquad -a=0-a\in S$$

继续做有限次加法、减法，便得到 $a$ 的任意整数倍都属于 $S$。因此，对 $a,b\in S$ 和任意整数 $u,v$，

$$ua+vb\in S$$

反过来，固定整数 $a,b$，它们所有整数线性组合构成的集合

$$S=\{ax+by:x,y\in\mathbb{Z}\}$$

也是整数模：它包含 $0$，且两个线性组合的和、差仍然是同样形式的线性组合

每个非零整数模都是倍数集合

定理：若 $S\neq\{0\}$，则存在唯一的正整数 $d$，使得

$$\boxed{S=d\mathbb{Z}}$$

证明分为两步

首先，$S$ 中有非零元素，又对取负封闭，所以一定有正元素。由良序原理，取 $S$ 中最小的正整数为 $d$。由于整数模包含其元素的所有整数倍，有 $d\mathbb{Z}\subseteq S$

其次，对任意 $n\in S$ 做带余除法：

$$n=qd+r,\qquad 0\leq r<d$$

由于 $n,qd\in S$，所以 $r=n-qd\in S$。若 $r>0$，它就是比 $d$ 更小的正元素，产生矛盾。因此 $r=0$，即 $d\mid n$，所以 $S\subseteq d\mathbb{Z}$

两者合起来得到 $S=d\mathbb{Z}$。其中 $d$ 就是 $S$ 的最小正元素，因此也唯一

从整数模得到最大公因数

设整数 $a,b$ 不同时为 $0$，考虑

$$S=\{ax+by:x,y\in\mathbb{Z}\}$$

由上一节，存在正整数 $d$ 使得 $S=d\mathbb{Z}$。下面说明这个 $d$ 恰好就是 $\gcd(a,b)$

一方面，取 $(x,y)=(1,0)$ 和 $(0,1)$，可知 $a,b\in S$，所以

$$d\mid a,\qquad d\mid b$$

另一方面，$d\in S$，因此存在整数 $u,v$，使得

$$d=au+bv$$

如果 $e$ 是 $a,b$ 的任意公因子，那么 $e\mid au+bv=d$。所以 $d$ 是公因子，且每个正公因子都不超过它，即

$$d=\gcd(a,b)$$

我们同时得到三个结论：

$$\begin{aligned} \{ax+by:x,y\in\mathbb{Z}\}&=\gcd(a,b)\mathbb{Z},\\ \gcd(a,b)&=\min\{ax+by:ax+by>0,\ x,y\in\mathbb{Z}\},\\ au+bv&=\gcd(a,b)\quad\text{对某些整数 }u,v\text{ 成立} \end{aligned}$$

最后一条就是 Bézout 等式。上一讲通过欧几里得算法构造它，这里通过集合的最小正元素证明它

例如

$$6=-2\times42+3\times30,$$

所以 $42x+30y$ 的全部可能取值恰好是 $6$ 的所有整数倍

互素与缩放

若 $\gcd(a,b)=1$，则称 $a,b$ 互素。由 Bézout 等式，互素等价于存在整数 $u,v$，使得

$$au+bv=1$$

对于非零整数 $c$，所有 $acx+bcy$ 构成的集合是

$$c\{ax+by:x,y\in\mathbb{Z}\} =c\gcd(a,b)\mathbb{Z}$$

它的最小正元素为 $|c|\gcd(a,b)$，因此

$$\gcd(ac,bc)=|c|\gcd(a,b)$$

特别地，若 $d=\gcd(a,b)$，则

$$\gcd\left(\frac ad,\frac bd\right)=1$$

欧几里得引理

欧几里得引理：若 $p$ 为素数，且 $p\mid ab$，则

$$\boxed{p\mid a\quad\text{或}\quad p\mid b}$$

如果 $p\mid a$，结论已经成立。否则，由于 $p$ 的正因子只有 $1,p$，有 $\gcd(a,p)=1$。于是存在整数 $x,y$，使得

$$ax+py=1$$

两边乘以 $b$：

$$abx+pby=b$$

左侧两项都被 $p$ 整除，所以 $p\mid b$，证毕

素数条件很关键。例如 $6\mid2\times3$，但 $6$ 既不整除 $2$，也不整除 $3$

对引理反复应用，可得：若素数 $p$ 整除有限个整数的乘积，则它至少整除其中一个因子

算术基本定理：唯一性

算术基本定理：每个整数 $n>1$ 都存在唯一的标准分解

$$n=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}, \qquad p_1<p_2<\cdots<p_k,\quad \alpha_i>0$$

存在性已在第一篇中证明。现在假设 $n$ 有两种素因数分解，先将重复因子全部展开：

$$n=p_1p_2\cdots p_r=q_1q_2\cdots q_s$$

由于 $p_1$ 整除右边的乘积，由欧几里得引理，它整除某个 $q_j$。但 $p_1,q_j$ 都是素数，因此 $p_1=q_j$

将这对相同的因子约去，对剩下的乘积重复上述过程。两边的因子必然一一配对：如果一边先被约完，另一边还剩素因子，就会得到 $1$ 等于若干个大于 $1$ 的整数之积，矛盾

因此两边素因子的种类及出现次数完全相同。将同类素数合并、按大小排序后，标准分解唯一

这也解释了为什么把 $1$ 排除在素数定义之外：任意插入因子 $1$ 都不会改变乘积，却会破坏“只允许交换因子顺序”的唯一性表述

最大公因数与最小公倍数

有了唯一分解，整除关系就可以转化为对素因数指数的比较

设 $a,b$ 为正整数，把二者出现过的素数统一列为 $p_1,\ldots,p_s$，写成

$$a=\prod_{i=1}^s p_i^{\alpha_i},\qquad b=\prod_{i=1}^s p_i^{\beta_i}$$

这里允许指数为 $0$，表示该素数没有出现在对应整数的分解中。于是

$$a\mid b\quad\Longleftrightarrow\quad \alpha_i\leq\beta_i\quad\text{对所有 }i\text{ 成立}$$

指数取最小值与最大值

公因子在每个素数上的指数都不能超过 $\alpha_i,\beta_i$，所以

$$\boxed{\gcd(a,b)=\prod_{i=1}^s p_i^{\min(\alpha_i,\beta_i)}}$$

$a,b$ 的最小公倍数记为 $\operatorname{lcm}(a,b)$，是同时被二者整除的最小正整数。因为 $ab$ 就是一个正公倍数，它总是存在

公倍数在每个素数上的指数都不能小于 $\alpha_i,\beta_i$，所以

$$\boxed{\operatorname{lcm}(a,b)=\prod_{i=1}^s p_i^{\max(\alpha_i,\beta_i)}}$$

这个数本身是公倍数，而且整除任意其他公倍数，因此确实最小。其他公倍数即使包含额外的素因子，也不影响这个整除关系

例如

$$72=2^3\times3^2,\qquad 120=2^3\times3\times5,$$

于是

$$\gcd(72,120)=2^3\times3=24, \qquad \operatorname{lcm}(72,120)=2^3\times3^2\times5=360$$

GCD 与 LCM 的乘积

由

$$\min(\alpha_i,\beta_i)+\max(\alpha_i,\beta_i) =\alpha_i+\beta_i,$$

逐个比较素数的指数，得到

$$\boxed{\gcd(a,b)\operatorname{lcm}(a,b)=ab}$$

因此，计算最小公倍数时可以先用欧几里得算法求 GCD，再计算

$$\operatorname{lcm}(a,b)=\frac{a}{\gcd(a,b)}\,b$$

这样不需要先分解 $a,b$，且先除后乘可以减小中间结果

多个整数的情形

对于多个正整数，GCD 和 LCM 仍然是在每个素数上分别取所有指数的最小值、最大值。因此可以逐个合并，例如

$$\begin{aligned} \gcd(a,b,c)&=\gcd(\gcd(a,b),c),\\ \operatorname{lcm}(a,b,c)&=\operatorname{lcm}(\operatorname{lcm}(a,b),c) \end{aligned}$$

但两个数的乘积公式不能直接照搬。例如 $2,4,8$ 的 GCD 为 $2$、LCM 为 $8$，两者之积为 $16$，而三个数的乘积为 $64$

例题：用素因数指数计算对数

讲义最后的例题把唯一分解用于计算。思路是：乘法对应素因数指数相加，取对数后又变成线性组合

本节重新用 $a,b,c,d,e$ 表示五个对数：

$$\begin{aligned} a&=\log_{10}\frac{1025}{1024},\\ b&=\log_{10}\frac{1024^2}{1023\times1025},\\ c&=\log_{10}\frac{81^2}{80\times82},\\ d&=\log_{10}\frac{125^2}{124\times126},\\ e&=\log_{10}\frac{99^2}{98\times100} \end{aligned}$$

这些分数都很接近 $1$，所以对数很小，适合用级数近似。目标是用它们表示 $\log_{10}2$、$\log_{10}3$ 和 $\log_{10}41$

把乘法转化为指数运算

正有理数的素因数指数允许为负数，表示分母中的因子。例如

$$10^a=\frac{1025}{1024}=2^{-10}5^2\times41$$

类似地，对 $10,10^a,\ldots,10^e$ 分解，得到各个素数的指数：

给这六列依次乘以 $59,5,8,-3,-8,4$ 再相加，得到的指数向量为

$$(196,0,0,0,0,0,0)^{\mathsf T}$$

例如 $2$ 的指数为

$$59-50+160+15+24-12=196,$$

其他素数的指数均为 $0$。由唯一分解，

$$10^{59}(10^a)^5(10^b)^8(10^c)^{-3}(10^d)^{-8}(10^e)^4 =2^{196}$$

两边取以 $10$ 为底的对数，就得到

$$\boxed{196\log_{10}2=59+5a+8b-3c-8d+4e}$$

要计算另外两个对数，只需让目标指数向量分别只在素数 $3$、$41$ 的位置非零，再解相应的线性方程组。结果为

$$\begin{aligned} 392\log_{10}3&=187+69a+32b+37c-32d+16e,\\ 49\log_{10}41&=79+64a+24b-9c-24d+12e \end{aligned}$$

用小量的级数近似求值

对 $0<x<1$，有

$$\ln(1+x)=x-\frac{x^2}{2}+\frac{x^3}{3}-\cdots$$

保留前三项，截断误差的绝对值不超过 $x^4/4$。上面五个分数对应的小量分别为

$$\frac1{1024},\quad \frac1{1023\times1025},\quad \frac1{80\times82},\quad \frac1{124\times126},\quad \frac1{98\times100}$$

其中最大的也小于 $10^{-3}$，因此前三项已经能给出很精确的近似。再由换底公式

$$\log_{10}(1+x)=\frac{\ln(1+x)}{\ln10},$$

使用讲义给定的 $\ln10\approx2.3025850930$，计算这五个小对数，代入前面的线性组合，得到

$$\log_{10}2\approx0.3010299957$$

即保留小数点后十位的结果

这个例子把“求一个对数”拆成了两步：先通过素因数指数找到精确的代数关系，再对接近 $1$ 的数使用快速收敛的级数