---
url: https://xuehaizhixing.com/root/B01-数论基础/M01-整除与质数/S03/B01-M01-S03-U05.md
---

# 一、模块层

* **知识点编号**：B01-M01-S03-U05
* **所属模块**：B01 → M01 → S03

## 纵向关联

* 上接：
  * [短除法求gcd题根](/root/B01-数论基础/M01-整除与质数/S03/B01-M01-S03-U02)
  * [质因数分解法求gcd题根](/root/B01-数论基础/M01-整除与质数/S03/B01-M01-S03-U03)
* 下启：
  * [辗转相除法步骤理解题根](/root/B01-数论基础/M01-整除与质数/S03/B01-M01-S03-U04)

## 知识关联

### 横向关联

* 前置基础：
  * `同类项合并题根`
  * `乘除正负数题根`
* 同位衔接：
  * `全等证明技巧题根`
  * `捆绑/插空与概率题根`
  * `鸽笼原理题根`
* 后续延伸：
  * [数论极值问题题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S03/B01-M04-S03-U04)
  * [特殊技巧题根](/root/B01-数论基础/M03-不定方程/S05/B01-M03-S05-U04)
  * [数论存在性证明题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S03/B01-M04-S03-U03)
  * [无穷递降法初步题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S02/B01-M04-S02-U04)
  * [二次剩余定义题根](/root/B01-数论基础/M02-同余理论/S07/B01-M02-S07-U01)
  * [欧拉判别法题根](/root/B01-数论基础/M02-同余理论/S07/B01-M02-S07-U02)
  * [构造法数论题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S02/B01-M04-S02-U03)
  * [数论组合构造题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S03/B01-M04-S03-U02)

# 二、本源层

* **本源**：互质是整数间的一种"独立性"关系——两个整数$a,b$互质（或互素）当且仅当$\gcd(a,b)=1$，即它们没有任何大于1的公共质因数。互质不是"没有关系"，而是一种纯粹的共存关系：它们各自携带着完全不同的质因数集合，彼此之间唯一的纽带是数字$1$。互质的核心价值在于它揭示了整数的"质因数独立性"——当两数互质时，它们在乘法结构中互不干扰，这一性质是整个数论推理的重要基石。
* **原点**：整数的整除关系构成了一个偏序结构（用整除关系排序），其中$\gcd(a,b)=1$意味着$a$和$b$在这个偏序中没有大于$1$的下界。1是"最小公因数"和"普遍公因数"的统一——任何两个整数都以1为公因数，所以"互质"不是"没有公因数"，而是"没有大于1的公因数"。从质因数分解的视角看，互质等价于两数的质因数集合不相交——这一定义将互质判断转化为集合交运算：若${p\mid p\mid a}\cap{p\mid p\mid b}=\varnothing$则互质。这一集合论视角不仅使互质判断更加直观，还为后续学习欧拉函数$\varphi(n)$（计数与$n$互质的数的个数）和裴蜀定理（互质的充要条件）提供了结构化的预备知识。
* **道法**：互质判断推理，三锚合一，层层递进。
  * **首锚·gcd判互**：直接求两数的最大公因数，若结果为$1$则互质，否则不互质——这是最直接最可靠的判定标准，适用于一切正整数。
  * **次锚·质因交集**：分别写出两数的质因数集合，检查是否有交集；无交集则互质——这一视角揭示了互质的深层结构含义，适用于可分解的小数字。
  * **三锚·性质速判**：利用互质的常用性质快速判断——相邻整数必互质、质数与不被其整除的数互质、以及与1同为互质的充要条件等。
* **关键心法**：
  gcd为1即互质，质因无交即为偶。相邻必质穿透通，欧拉函数由此生。

掌握这一心法意味着：面对一个具体问题，你的第一反应不是套公式，而是先问“这属于哪一类？”——这是从“术”到“道”的跨越。

* **终极一句话**：
  $\gcd(a,b)=1\iff a$与$b$无公共质因数——互质是整数在质因数层面"相互独立"的精确数学表达，是数论推理中最常用的关系前提，也是后续学习欧拉函数和同余可逆性的概念起点。

这句话浓缩了该概念最本质的数学事实，每一个字都经得起推敲。理解这句话，就掌握了进入该领域的钥匙。

* **数学思想进化轴**：欧几里得《几何原本》（约公元前300年）首次定义互质概念——"不能由同一单位度量的两个数"，并给出互质数的基本性质→斐波那契《计算之书》（1202）系统使用互质性质简化分数运算和商业算术中的比例计算→欧拉（1763）引入$\varphi(n)$函数专门计数与$n$互质的数的个数，互质从一种关系概念上升为一种计数函数→高斯《算术研究》（1801）将互质概念纳入同余理论的框架，互质成为模运算中"可逆元"的判定标准→现代密码学中，RSA加密算法（1977）的安全性直接建立在"两个大质数互质"以及"与$\varphi(n)$互质的公钥指数"的数学基础之上——互质概念从理论数论走向了现代信息安全的实际应用。

# 三、知识点层

* **知识点编号**：B01-M01-S03-U05
* **名称**：互质数列判断题根
* **标准定义**：
* 定义一（两数互质）：正整数$a,b$称为互质（互素），如果$\gcd(a,b)=1$。等价地：$a$和$b$没有大于$1$的公共因数，即它们的质因数集合的交集为空集（忽略$1$）。例如$14=2\times7$与$25=5^2$质因数集合分别为${2,7}$和${5}$，交集为空→互质。
  * 定义二（整体互质与两两互质）：一组正整数$a_1,a_2,\ldots,a_k$称为整体互质（或简称互质），如果$\gcd(a_1,\ldots,a_k)=1$。称为两两互质，如果对任意$i\neq j$有$\gcd(a_i,a_j)=1$。两两互质$\Rightarrow$整体互质（因为每对中没有公共质因数，整体也不可能有），但反之不成立（如$6,10,15$整体$\gcd=1$，但$\gcd(6,10)=2\neq1$，$\gcd(6,15)=3\neq1$）。

从等价关系角度看，这一定义实际上建立了一个划分：它将所有可能的情形分为互不相交的两类，且覆盖了全集。这是一个最简单的二元分类系统。

在实际解题中，这一定义提供了三种判定策略：(1)正面验证——直接检查条件是否成立；(2)反面排除——检查是否属于另一类来确定；(3)等价转化——利用该定义的某个等价刻画来判定。

该定义还有一个重要推论：若某对象满足定义条件，则它自动具有该类别的一切性质；反之，若某性质在某对象上不成立，则该对象必不属于此类别。

特别需要注意两件事：一是定义中条件的充分必要性——既不能多也不能少；二是定义的边界情形——当条件处于模糊地带时该如何判定。

* **核心本质**：**互质是整数在质因数层面的"独立性"——两个数互质当且仅当它们没有任何公共质因数。这是数论中最基础的关系之一：互质的两个数在乘法结构中互不干扰，允许"因数穿透"（若$a\mid bc$且$\gcd(a,b)=1$则$a\mid c$）和"乘积拆分"（若$\gcd(a,b)=1$则$\gcd(a,ab)=\gcd(a,b)$等）。从更宏观的视角看，互质概念的本质是"结构最小公因数"——当两数互质时，它们的质因数结构完全不重叠，意味着它们在乘法积中的分解是"干净的"：$\gcd(a,b)=1$的充要条件是存在整数$x,y$使$ax+by=1$（裴蜀定理的特例），这一等价关系将互质从"因数层面"提升到了"线性组合层面"，为数论中的同余方程求解提供了关键工具。互质也是可逆性概念的原型——在模$a$运算中，$b$可逆当且仅当$\gcd(a,b)=1$，这一事实连接了数论与抽象代数中的群论。锁死·拓展应用层通用内容**
* **核心性质**：
  * 性质一：单位元性质——1与任何整数互质：$\gcd(1,n)=1$对所有整数$n$成立。这是互质关系的"单位元"特征——1作为乘法的单位元，在质因数层面是空集，不可能与任何数共享质因数。这条性质虽平凡，却在许多证明中起到"锚点"作用（如数学归纳法中作为基础步骤）。
  * 性质二：连续整数互质性——任意两个连续正整数互质：$\gcd(n,n+1)=1$。证明：设$d=\gcd(n,n+1)$，则$d\mid(n+1)-n=1$→$d=1$。更一般地，任意两个相差1的整数互质。这条性质的核心意义在于：连续的整数在数论中保持了一种"最简"的关系——它们之间唯一的公共因数是1。这一性质在分数化简（相邻分母）、丢番图逼近和代数数论中都有重要应用。
  * 性质三：因子穿透性——若$a\mid bc$且$\gcd(a,b)=1$，则$a\mid c$。这是互质关系中最有用的性质之一：当一个数与乘积的一个因子互质时，它"穿透"这个因子去整除另一个因子。证明：由裴蜀定理，存在$x,y$使$ax+by=1$，两边乘以$c$得$acx+bcy=c$。由于$a\mid acx$且$a\mid bcy$（因为$a\mid bc$），故$a\mid c$。
  * 性质四：加法稳定性——对互质的两数$a,b$，$\gcd(a+b,a-b)$只能是1或2。更一般地，若$d=\gcd(a,b)=1$，则$\gcd(a+b,a-b)$可进一步分析：若$a,b$同为奇数则$=2$，若一奇一偶则$=1$。这反映了互质关系在加法运算下的变化规律——加法和减法不会在互质对中引入太大的公因数（最大只到$2$）。这条性质是竞赛题中构造互质证明的常用工具。

# 四、教案版本

## 【专业版】

### 【基础层例题】

判断14和25是否互质。
① 求$\gcd(14,25)$——14和25都是较小的数，可用枚举法或质因数分解法求gcd，看结果是否为1。关键：判断互质不需要列出全部因数，只需检查质因数集合是否有交集。
② 常见误区：认为互质的两个数自身必须是质数（如认为$4$和$9$不互质因为它俩都不是质数）。纠正：互质无关乎各数本身是否为质数，只关乎它们是否共享质因数——$4=2^2$和$9=3^2$没有公共质因数，故互质。
③ 方法策略：优先采用"质因交集法"判断小数的互质性——分别写出两数的质因数集合，检查交集是否为空。这种方法比直接求gcd更能揭示"为什么互质"的结构性原因，也容易验算。

* **标准解答**：$14$的质因数：$14=2\times7$。$25=5^2$。两数没有公共质因数→$\gcd(14,25)=1$→互质。验算：$\gcd(14,25)=1$，两数互质。注意：判断互质不需要列出全部因数，只需看质因数集合是否有交集。
  上述解答过程中，每一步推导的依据是该知识点的核心性质——准确把握每一步的逻辑基础，是确保解题正确性的关键。
  这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。
  验证是解题的重要环节——将答案代回原题检验是否满足所有条件，既能确认正确性，也能培养良好的解题习惯。
  这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。### 【易错变式题】
  判断”三个数两两互质”与”三个数整体互质”是否等价？举例说明。
  ① 解题思路：用反例法——尝试构造三个数使整体$\gcd=1$但并非每对互质。经典反例$(6,10,15)$的构造思路：让每两个数共享一个不同的质因数，而这三个质因数互不相同，确保没有质因数同时出现在所有三个数中。
  ② 常见错误：认为”整体互质”和”两两互质”等价，或认为整体互质强于两两互质。实际上两两互质蕴含整体互质，但反之不成立——整体互质只能保证没有”全数共享”的质因数，无法阻止每对数各自有公因数。
  ③ 方法策略：区别两者的关键是考察”共享的范围”——整体互质检查的是”是否有全数共享的质因数”，两两互质检查的是”是否有任意两数共享的质因数”。在数论证明中，两两互质通常比整体互质更有用，因为它允许对每对数独立使用互质性质（如因子穿透）。
* **标准解答**：不等价。两两互质（每对$\gcd=1$）$\Rightarrow$整体互质（全体$\gcd=1$），但反之不成立。反例：$6,10,15$。$\gcd(6,10,15)=1$（整体互质），但$\gcd(6,10)=2\neq1$，$\gcd(6,15)=3\neq1$，$\gcd(10,15)=5\neq1$（不是两两互质）。为什么？因为整体gcd=1只要求三数没有公共质因数，但每对数可以有各自的公共质因数（6和10共享2，6和15共享3，10和15共享5）。”整体互质”允许每对”共谋”，只要不”全数共谋”。；上述解答过程中，每一步推导的依据是该知识点的核心性质——准确把握每一步的逻辑基础，是确保解题正确性的关键。；这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。；验证是解题的重要环节——将答案代回原题检验是否满足所有条件，既能确认正确性，也能培养良好的解题习惯。；这道题的核心考点是考查学生对基本概念的准确理解——只有概念清晰，才能从题目条件中识别出可用的结论。
  从思维训练的角度看，这道题考察的核心能力是在复杂条件中识别出可应用该知识点的结构特征——这种识别能力是数学素养的重要组成部分。
  从思维训练的角度看，这道题考察的核心能力是在复杂条件中识别出可应用该知识点的结构特征——这种识别能力是数学素养的重要组成部分。### 【高阶例题】
  证明：对任意整数$n$，$n$和$n+1$互质。
  ① 解题思路：采用反证法——假设存在大于$1$的公因数$d$，则$d\mid n$且$d\mid(n+1)$，利用整除的线性组合性质（若$d\mid a$且$d\mid b$则$d\mid(a-b)$）可得$d\mid1$，与$d>1$矛盾。
  ② 常见错误：试图用具体数值验证代替一般性证明（如说"5和6互质因为验证过"），落入以偏概全。需要的是对所有$n$成立的普遍性证明而非特例验证。
  ③ 方法策略：相邻整数互质的证明是反证法与整除线性组合性质联用的经典示范——先假设矛盾结论，再利用"差为1"的结构特征推导出矛盾。这一策略可迁移到其他互质证明中：若两数之差为$1$的倍数而公因数$d$整除两者则必整除其差，由此推出$d\mid1\rightarrow d=1$。
* **标准解答**：假设$\gcd(n,n+1)=d>1$。则$d\mid n$且$d\mid(n+1)$。由整除的线性组合性质：$d\mid (n+1)-n=1$。因此$d\mid 1$，但$d>1$不可能整除$1$，矛盾。故假设不成立，$d=1$，$n$和$n+1$互质。这一证明的精妙之处在于：它不依赖于$n$的具体值，仅利用”相邻整数之差为$1$”这一结构特征，适用于一切正整数（甚至一切整数）。

## 【药典版】

### 定位：整数间最”纯粹”的关系——一剂独立无涉的判断方，互质意味着两个数在质因数层面完全独立，唯一的纽带只有数字1

#### 🌱 药材本体

* **第一味药——gcd判互**：$\gcd(a,b)=1$是互质的充要条件。无论用枚举法、短除法还是辗转相除法，只要gcd的结果为1，就宣告互质。这是最直接、最可靠的判断方法。
* **第二味药——质因交集**：${p\mid p\mid a}\cap{p\mid p\mid b}=\varnothing$——互质等价于质因数集合无交集。这一视角为互质判断提供了”结构性”直觉：互质就是”各玩各的质因数”。
* **第三味药——因子穿透**：若$a\mid bc$且$\gcd(a,b)=1$则$a\mid c$——互质关系下因子的”穿透”性质。这是互质关系在整除推理中的核心工具，被称为”欧几里得引理”。
* **第四味药——加减稳定性**：互质的两数经过加法或减法运算后，公因数的变化是有限且可控的——$\gcd(a+b,a-b)$只能是1或2。这为后续分析互质对的代数变换提供了定量工具。
* **药材核心药性**：以独立为体，以穿透为用——“互质则穿透，共享则阻塞”。
  这一数学概念的核心特性在于其基础性和工具性——它不仅是解决问题的基础工具，更是连接不同知识模块的桥梁。

#### 🛠️ 功能主治

* **主治**：区分不清”整体互质”和”两两互质”的概念混淆——通过反例$(6,10,15)$让学生直观感受差别
* **解决**：面对”若$a\mid bc$且$\gcd(a,b)=1$求证$a\mid c$”这类推理时无从下手——互质性质的代数应用训练
* **根治**：对欧拉函数$\varphi(n)$理解困难的前置障碍——$\varphi(n)$的定义本身就是”与$n$互质的数的计数”
* **打通**：从”两数互质”到”整体互质”到”两两互质”到”欧拉函数”到”费马小定理”到”RSA加密”的数论主线——互质是这一切的起点

#### 🧪 核心药方

1、**gcd判互方**——直接求两数的最大公因数，结果为1则互质。适用于一切正整数，可用短除法或辗转相除法。适配基础表达阶
2、**质因交集方**——分别写出两数的质因数集合，检查是否有交集。适用于可分解的小数字，能提供”为什么互质”的结构性理解。适配进阶表达阶
3、**穿透证明方**——利用欧几里得引理”若$a\mid bc$且$\gcd(a,b)=1$则$a\mid c$”进行数论证明。这一性质在绝大多数互质相关的竞赛题中是核心推理工具。适配高阶表达阶

#### 🌌 药理

**互质是整数的”独立宣言”——两个数互质意味着它们在乘法结构中互不欠债。**

互质概念看似简单（”最大公因数为1”六个字就能说清），却蕴含了数论中最深刻的结构关系。它是整除关系的”否定”形式——不是”一个整除另一个”，而是”唯一共同的正因数是1”。这种”否定关系”在许多情况下比”肯定关系”更有用：因为互质允许”因子穿透”——如果一个数与积的一个因子互质，它就可以”穿透”这个因子去整除另一个。这是数论证明中最常用的技巧之一，也是唯一分解定理在推理层面的直接推论。

从历史看，互质概念可追溯到欧几里得《几何原本》（公元前300年），其中第七卷定义12明确指出：”互质数是那些除单位外没有任何公度量的数。”这一定义一直沿用至今。互质概念的核心地位在18世纪得到空前提升：欧拉（1763）引入$\varphi(n)$函数，专门计数与$n$互质的数的个数；此后费马小定理（$a^{p-1}\equiv1\pmod{p}$）和高斯互反律等深刻定理都建立在互质假设之上。

在教学中，互质概念是学生从”具体计算”走向”抽象推理”的关键一步。判断互质本身并不困难，但利用互质性质进行推理（如欧几里得引理的证明和应用）需要对整除关系有深刻理解。这是数学思维的重要转折点。

#### 👨‍🏫 老师修炼阶梯

* **基础表达**：教学生用求$\gcd$的方法判断互质——“最大公因数等于1就是互质”。先用$14$和$25$等简单例子，让学生掌握”互质≠没有公因数（1永远是公因数）”这一关键辨析。
* **进阶表达**：引入”整体互质”和”两两互质”的区分。用$(6,10,15)$作为经典反例，让学生通过具体数字感受这两种互质的差异。训练学生准确判断”这组数是否两两互质”。
* **高阶表达**：证明和应用欧几里得引理（$a\mid bc$且$\gcd(a,b)=1\Rightarrow a\mid c$）。这是互质性质在竞赛题中的核心应用，要求学生掌握从裴蜀定理出发的证明方法。
* **顶阶表达**：连接互质与欧拉函数$\varphi(n)$——计数与$n$互质的数的个数。进一步导向费马小定理和RSA加密的基本原理，让学生看到”互质”这一简单概念如何支撑起现代密码学。

#### 🗣️ 一句话封神

$\gcd(a,b)=1\iff a$与$b$无公共质因数——互质是整数的”独立宣言”，唯一的共同点是$1$。
数学学习的关键不在于刷了多少题，而在于是否建立了知识之间的联系——当不同模块的知识在心中形成网络，解题就不再是搜索记忆而是自然涌现。
真正的高手不是记得多少公式，而是能看到不同方法背后的统一思想——这就是数学的眼光。#### 🩺 一眼诊断

* **与质数混淆型**：以为互质的两个数自己必须是质数（如认为$4$和$9$不互质因为$4$和$9$都不是质数）。→纠正：互质无关乎各数本身是否为质数，只关乎它们是否共享质因数。$4=2^2$和$9=3^2$没有公共质因数→互质。
* **整体两两混淆型**：把”整体互质”（$\gcd(a,b,c)=1$）等同于”两两互质”。→用$(6,10,15)$做反例：整体$\gcd=1$但不是两两互质，让学生自己动手计算每对的gcd来验证。
* **穿透盲区型**：在使用”若$a\mid bc$且$\gcd(a,b)=1$则$a\mid c$”时，忘记检查$\gcd(a,b)=1$的条件，或默认$a$和$b$总是互质。→强调条件检查的重要性，用反例演示：$6\mid 2\times3$但$\gcd(6,2)=2\neq1$，所以$6\nmid 3$。
* **加减误判型**：认为互质的两数相加后仍然互质（如$2$和$3$互质但$2+3=5$与$2$互质是对的，但$3$和$5$互质而$3+5=8$与$3$的gcd=1？不对，$\gcd(8,3)=1$仍然互质……需要更典型的反例，如$2$和$7$互质但$2+7=9$与$2$互质、与$7$互质。实际上要注意：$\gcd(a+b,a-b)$才是受控的，$\gcd(a+b,a)$或$\gcd(a+b,b)$不一定等于1）。

#### 🧭 导航路径

* **步行（L1-L2）** → 对标
  1. 判断12和35是否互质。用质因数分解法说明理由。
     * 解答提示：$12=2^2\times3$，$35=5\times7$。质因数集合${2,3}$和${5,7}$无交集→$\gcd(12,35)=1$→互质。尽管$12$和$35$都不是质数，但它们的质因数完全不同，仍然互质。

> 进一步引导：这个步骤的关键在于区分干扰信息和关键信息——题目中看似复杂的条件往往只有少数几个与分类判定直接相关，学会筛选信息本身就是重要的数学素养。

2. 写出三组互质正整数对：一组是两数均为质数，一组是两数均为合数，一组是一质一合。
   * 解答提示：质-质对：$(2,3)$，$(5,7)$，$(11,13)$。任意两个不同质数都互质。合-合对：$(4,9)$（$2^2$和$3^2$无交集），$(8,15)$（$2^3$和$3\times5$），$(14,25)$（$2\times7$和$5^2$）。质-合对：$(2,9)$（质数2不整除9），$(7,12)$（7不整除12），$(11,25)$（11不整除25）。
3. 证明：若$p$为质数，$a$为整数，则要么$p\mid a$，要么$\gcd(p,a)=1$。
   * 解答提示：设$d=\gcd(p,a)$，则$d\mid p$。因为$p$是质数，$d$只能是$1$或$p$。若$d=p$，则$p\mid a$。若$d=1$，则$\gcd(p,a)=1$。两情形恰好是对原命题的”二选一”表达。这个命题揭示了质数与其他数的特殊关系：质数要么整除一个数，要么与该数互质——没有中间状态。

> 进一步引导：这个步骤的关键在于区分干扰信息和关键信息——题目中看似复杂的条件往往只有少数几个与分类判定直接相关，学会筛选信息本身就是重要的数学素养。养成先筛选再判断的习惯，能大幅提升解题速度和准确性。

上述解答过程中，每一步推导的依据是该知识点的核心性质——准确把握每一步的逻辑基础，是确保解题正确性的关键。- **刚性达标阈值**：掌握基础概念，正确率≥90%

* **骑车（L3-L4）** → 对标

  1. 证明：若$\gcd(a,b)=1$，则$\gcd(a+b,a-b)$只能是$1$或$2$。
     * 解答提示：设$d=\gcd(a+b,a-b)$。则$d\mid(a+b)+(a-b)=2a$，且$d\mid(a+b)-(a-b)=2b$。所以$d\mid\gcd(2a,2b)=2\gcd(a,b)=2$。所以$d\mid2$，即$d=1$或$d=2$。进一步：如果$a,b$一奇一偶→$a+b$和$a-b$都是奇数→$d$不能是偶数→$d=1$。如果$a,b$同奇→$a+b$和$a-b$都是偶数→$d$可能为$2$。例如$a=3,b=5$：$\gcd(8,2)=2$。所以$d=2$可达。
  2. 若$\gcd(a,b)=1$，求证：$\gcd(a+b,ab)=1$。
     * 解答提示：设$d=\gcd(a+b,ab)$且$d>1$，则$d$有质因数$p$。$p\mid ab\Rightarrow p\mid a$或$p\mid b$（由欧几里得引理）。若$p\mid a$，由$p\mid a+b$得$p\mid b$，矛盾于$\gcd(a,b)=1$。同理若$p\mid b$也导出矛盾。故$d=1$，$\gcd(a+b,ab)=1$。这一性质是欧几里得引理应用的典型代表。
  3. 求所有小于$20$且与$20$互质的正整数的个数。
     * 解答提示：$20=2^2\times5$。与$20$互质的数不含质因数$2$和$5$。小于$20$的正整数中排除所有偶数和$5$的倍数即可。列出$1$到$19$，剔除偶数（$2,4,6,8,10,12,14,16,18$）和$5$的倍数（$5,10,15$，注意$10$已剔除），剩下：$1,3,7,9,11,13,17,19$。共$8$个。这正是欧拉函数$\varphi(20)=20\times(1-\frac12)(1-\frac15)=20\times\frac12\times\frac45=8$的枚举验证。

  * **刚性达标阈值**：能灵活运用解决变式问题，正确率≥85%
* **开车（L5-L6）** → 对标
  1. 证明：欧拉函数$\varphi(n)$等于$1$到$n$中与$n$互质的数的个数。
     * 解答提示：利用容斥原理。设$n=\prod p_i^{e_i}$，全集$U={1,2,\ldots,n}$。对每个质因子$p_i$，设$A_i={k\in U\mid p_i\mid k}$，则$|A_i|=n/p_i$。与$n$互质的数的集合是$U\setminus\bigcup A_i$。由容斥：$\varphi(n)=n-\sum n/p_i+\sum n/(p_ip_j)-\cdots=n\prod(1-1/p_i)$。这就是欧拉函数的乘积公式。
  2. 证明：对任意正整数$n$，存在连续$n$个合数。
     * 解答提示：考虑$(n+1)!+2,;(n+1)!+3,;\ldots,;(n+1)!+(n+1)$。因$k\mid (n+1)!$且$k\mid k$，故$k\mid (n+1)!+k$对每个$k=2,3,\ldots,n+1$成立。所以每个$(n+1)!+k$都是$k$的倍数且$>k$，因此都是合数。这$n$个连续整数全是合数。这一构造利用的是阶乘的”全包含”性质和互质关系的逆用——虽然没有直接使用互质，但利用了”整除意味着质因数共享”的对偶思想。
  3. 证明：$\sum\_{d\mid n}\varphi(d)=n$。
     * 解答提示：考虑分数$\frac{k}{n}$（$k=1,2,\ldots,n$），约分到最简形式。每个最简分数的分母$d$是$n$的约数，且分子是$1$到$d$中与$d$互质的数，有$\varphi(d)$个。每个$k/n$约分后得到唯一的最简分数，反之每个最简分数对应$\varphi(d)$个$k$。故$n=\sum\_{d\mid n}\varphi(d)$。这是一个极为优雅的组合数论证明，将欧拉函数与约数结构联系了起来。
  * **刚性达标阈值**：能综合解决复杂问题，正确率≥80%