第2卷 第3章 互质

学习目标

• 能用 gcd 和 lcm 解释分数的约分、通分，并证明 ab=gcd(a,b)lcm(a,b)
• 能按质数坐标写出自然数的指数向量，判断 1、质数和平方数的坐标特征
• 能把乘法、gcd、lcm 翻译成指数向量的加法、逐坐标 min/max 运算
• 能用支撑不相交和内积为 0 两种语言判断两个数是否互质，并解释几何“垂直”

从分数 8/30 开始

“互质”不是一个脱离运算的标签。分数相加时要通分，计算结束后又要约分；这两个方向相反的动作，分别暴露最小公倍数和最大公约数的结构。

先预测：为什么约分结束后分子分母一定互质？为什么最大公约数与最小公倍数的乘积等于原数之积？全零指数向量为什么表示 1？两个合数又怎样可能彼此“垂直”？本章会用质数账本、指数向量和交互实验逐项验收。

一、通分、约分与最简分数

给分母 6 和 10 通分，需要找到共同的倍数。最小的正公共倍数是：

$$\operatorname{lcm}(6,10)=30.$$

最小公倍数把不同分母送到同一个刻度。若得到 8/30，约分则寻找分子和分母的公共约数：

$$\gcd(8,30)=2,\qquad \frac8{30}=\frac{8\div2}{30\div2}=\frac4{15}.$$

现在 gcd(4,15)=1。最大公约数为 1 的两个正整数叫作互质；分子分母互质的分数叫最简分数，也叫既约分数。

一次除以最大公约数为什么足够？令 d=gcd(a,b)，写成 a=da'、b=db'。若 a' 和 b' 仍有大于 1 的公因数 e，那么 de 同时整除 a,b，且比 d 大，与 d 的最大性矛盾。因此：

$$\gcd\left(\frac a{\gcd(a,b)},\frac b{\gcd(a,b)}\right)=1.$$

分子分母互质不是观察出来的偶然结果，而是约分操作保证的性质。

最大公约数

最大公约数的“最大”不是说数值大于 a、b，而是所有公共约数中最大的那个。欧几里得算法可以通过反复取余高效计算它：

$$\gcd(a,b)=\gcd(b,a\bmod b).$$

二、gcd、lcm 与乘积恒等式

最小公倍数

取 a=18,b=24：

$$18=2^1\cdot3^2,\qquad 24=2^3\cdot3^1.$$

共同拥有的质因数按较少次数拿取：

$$\gcd(18,24)=2^1\cdot3^1=6.$$

要同时成为两数的倍数，必须按较多次数覆盖：

$$\operatorname{lcm}(18,24)=2^3\cdot3^2=72.$$

直接核对 18×24=432，6×72=432。一般地：

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

这就是恒等式ab等于gcd乘lcm。它不是只对 18 和 24 成立的数值巧合，而是每个质数指数都平衡后的必然结果。

用质因数分解证明恒等式

设质数 p 在 a,b 中的指数分别为 α,β：

$$v_p(a)=\alpha,\qquad v_p(b)=\beta.$$

在 ab 中，指数是 α+β；在 gcd 中取 min(α,β)，在 lcm 中取 max(α,β)。因为：

$$\alpha+\beta=\min(\alpha,\beta)+\max(\alpha,\beta),$$

所以两边每个质数的指数完全相同。依靠质因数分解唯一性，得到乘积恒等式。这就是质因数分解结构证明：让每个质数独立结账，而不是模糊地搬运公共因子。

三、质数指数记数法

质数指数记数法

对每个质数 p，令 v_p(n) 表示 p 在 n 的唯一质因数分解中出现的次数。按质数顺序排列：

$$\mathbf v(n)=\langle v_2(n),v_3(n),v_5(n),v_7(n),v_{11}(n),\ldots\rangle.$$

例如 280=2^3·3^0·5^1·7^1，所以：

$$\mathbf v(280)=\langle3,0,1,1,0,\ldots\rangle.$$

坐标 0 不是“乘了 0”，而是对应质数没有出现。反过来，一个只有有限多个非零坐标的非负整数向量，也能通过质数幂乘积恢复唯一正整数。

1、质数与平方数的坐标特征

1 的零向量是：

$$\mathbf v(1)=\langle0,0,0,0,\ldots\rangle.$$

全零向量表示 2^0·3^0·5^0·…=1，不是 0。质数的单位坐标只有一个位置为 1，其余为 0；例如 v(7)=⟨0,0,0,1,0,...⟩。

平方数的偶指数坐标则满足每个坐标都是偶数，因为平方会把每个指数加倍。反过来，若全部坐标为偶数，把每个坐标除以 2 就得到平方根的指数向量，所以该数必为平方数；1 也因此是平方数。

四、乘法、gcd、lcm 的坐标运算

设：

$$\mathbf v(a)=\langle a_2,a_3,a_5,\ldots\rangle,\qquad \mathbf v(b)=\langle b_2,b_3,b_5,\ldots\rangle.$$ 乘法对应指数向量加法

同底数幂相乘时指数相加，所以：

$$\mathbf v(ab)=\mathbf v(a)+\mathbf v(b).$$

例如 12=2^2·3、50=2·5^2：

$$\mathbf v(12)=\langle2,1,0,\ldots\rangle,\quad \mathbf v(50)=\langle1,0,2,\ldots\rangle,$$ $$\mathbf v(600)=\langle3,1,2,\ldots\rangle.$$

普通乘法被翻译成坐标加法；代价没有消失，而是提前放在分解质因数中。

gcd 和 lcm 同样变成逐坐标运算：

$$v_p(\gcd(a,b))=\min(v_p(a),v_p(b)),$$ $$v_p(\operatorname{lcm}(a,b))=\max(v_p(a),v_p(b)).$$

也就是 gcd对应逐坐标最小值，lcm对应逐坐标最大值。对 18,24 的指数向量逐列取 min 得 6，逐列取 max 得 72。

a182021242535b182021242535重置实验

逐坐标账本

p=2：1 / 3

p=3：2 / 1

结构结果

gcd=6 · lcm=72

支撑交集：2, 3

指数内积：5 （有共同质数）

五、互质的支撑与几何语言

向量记录哪些质数真正出现：

$$\operatorname{supp}(n)=\{p\text{为质数}:v_p(n)>0\}.$$ 互质等价于质因数支撑不相交

两数互质的逐坐标判据是：

$$\gcd(a,b)=1 \quad\Longleftrightarrow\quad \min(v_p(a),v_p(b))=0\quad\text{对每个质数 }p.$$

这等价于支撑集合不相交。例如 20=2^2·5 与 21=3·7 都是合数，但支撑分别为 {2,5} 与 {3,7}，没有交集，所以 gcd(20,21)=1。互质是成对关系，而不是单个数的类别。

自然数的无限维空间把每个质数当作一条坐标轴。自然数的指数向量是这个空间中的一个点；质因数分解是在寻找该点沿每条质数轴的坐标。有限支撑保证每个具体自然数只含有限多个不同质因数，因此向量和内积对它仍是有限计算。

定义内积：

$$\mathbf v(a)\cdot\mathbf v(b)=\sum_{p\ \mathrm{prime}}v_p(a)v_p(b).$$

所有项都非负，所以内积为 0 当且仅当每个质数坐标至少有一方为 0：

互质的向量垂直 $$\gcd(a,b)=1 \quad\Longleftrightarrow\quad \mathbf v(a)\cdot\mathbf v(b)=0.$$

二维图只能画两条质数轴作切片，但“没有共同质因数”的判据在所有质数轴上同时成立。

官方概念锚点回收如下：分数约分与最简分数、分子分母互质、最大公约数、最小公倍数、恒等式ab等于gcd乘lcm、质因数分解结构证明、质数指数记数法、1的零向量、质数的单位坐标、平方数的偶指数坐标、乘法对应指数向量加法、gcd对应逐坐标最小值、lcm对应逐坐标最大值、互质等价于质因数支撑不相交、自然数的无限维空间、有限支撑和互质的向量垂直，都已经在分数操作、指数账本、逐坐标运算、支撑判据或几何内积中落到可复查证据上。

分步验收：从约分走到垂直

⚡分步1 / 4

1. 1
2. 2
3. 3
4. 4

重置

1. 约分：找出互质的起点

对 8/30 求 gcd，执行约分，再验证所得分子分母的 gcd 为 1；对比通分时 lcm 的职责。

上一步播放下一步

本章回顾：从约分走进无限维空间

• 通分使用 lcm 统一分母，约分使用 gcd 消去公共因子；最简分数的分子分母互质。
• 每个质数独立记录指数，gcd 取逐坐标 min，lcm 取逐坐标 max，因此 ab=gcd(a,b)lcm(a,b)。
• 1 是零向量，质数是单位坐标，平方数是全部坐标为偶数的点。
• 自然数乘法在质数指数空间中变成向量加法；有限支撑保证具体计算仍可完成。
• 互质等价于质因数支撑不相交，也等价于指数向量内积为 0，即几何上的垂直。

练习与答案

练习

1. 问题 1：完成约分审计。 对 8/30 找出 gcd，约成最简分数，并说明为什么一次除以 gcd 后就不能继续约分。

查看答案

gcd(8,30)=2，所以 8/30=4/15。若 4,15 还有大于 1 的公共因子 e，则 2e 会同时整除原来的 8 和 30，超过 gcd=2，与最大性矛盾；因此 gcd(4,15)=1。

2. 问题 2：验证乘积恒等式。 用指数向量计算 gcd(18,24)、lcm(18,24)，并验证 18×24 等于它们的乘积。

查看答案

v(18)=(1,2,0,...)、v(24)=(3,1,0,...)。逐坐标取 min 得 (1,1,0,...)，即 6；取 max 得 (3,2,0,...)，即 72。6×72=432=18×24。

3. 问题 3：改 Demo 代码。 为指数向量实验增加一个“显示共同质因数”开关和重置按钮：输入切换后高亮支撑交集，并说明它与 gcd 的关系。

查看答案

可以把两数支撑集合的交集绘成高亮列；交集为空时 gcd=1，交集非空时把对应质数的较小指数相乘就得到 gcd。重置按钮应恢复默认的 18 和 24，并清除高亮状态。

4. 问题 4：解释几何翻译。 为什么两个合数 20 和 21 的指数向量仍然可以垂直？

查看答案

20=2²·5 的支撑是 {2,5}，21=3·7 的支撑是 {3,7}，两集合不相交。所有坐标乘积都为 0，所以内积为 0；垂直描述的是两数共享质数的关系，不是每个数是否为质数。

名词解释

本章出现的专业名词，用大白话再讲一遍。

最大公约数

同时整除两个正整数的最大正整数，记作 gcd。

最小公倍数

同时是两个正整数倍数的最小正整数，记作 lcm。

质数指数记数法

按质数顺序记录正整数各质因数出现次数的向量。

乘法对应指数向量加法

两数相乘时，每个质数的指数分别相加。

互质等价于质因数支撑不相交

两数没有共同质因数，当且仅当它们的支撑集合没有交集。

互质的向量垂直

质数指数向量内积为 0，正好对应两数互质。