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

# 一、模块层

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

## 纵向关联

* 上接：
  * [枚举法求gcd题根](/root/B01-数论基础/M01-整除与质数/S03/B01-M01-S03-U01)
* 下启：
  * [互质数列判断题根](/root/B01-数论基础/M01-整除与质数/S03/B01-M01-S03-U05)

## 知识关联

### 横向关联

* 前置基础：
  * `多边形内角和题根`
  * `垂直的定义与性质题根`
* 同位衔接：
  * `勾股数题根`
  * `等积变形题根`
  * `圆内接四边形性质题根`
* 后续延伸：
  * [原根定义题根](/root/B01-数论基础/M02-同余理论/S06/B01-M02-S06-U01)
  * [函数积性证明题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S01/B01-M04-S01-U05)
  * [μ(n)定义与性质题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S01/B01-M04-S01-U03)
  * [模分析题根](/root/B01-数论基础/M03-不定方程/S06/B01-M03-S06-U02)
  * [欧拉判别法题根](/root/B01-数论基础/M02-同余理论/S07/B01-M02-S07-U02)
  * [指标与同余方程题根](/root/B01-数论基础/M02-同余理论/S06/B01-M02-S06-U05)
  * [佩尔方程最小解题根](/root/B01-数论基础/M03-不定方程/S03/B01-M03-S03-U04)
  * [特殊高次方程题根](/root/B01-数论基础/M03-不定方程/S06/B01-M03-S06-U04)

# 二、本源层

* **本源**：质因数分解法求gcd的核心是基于算术基本定理的"指数取最小"：每个正整数可唯一分解为质因数的幂次乘积，两个数的最大公因数就是它们公有质因数的最低次幂的乘积。这一方法将gcd从"找出公共因数"的枚举操作提升为"比较指数大小"的代数运算，实现了从形象思维到抽象思维的跨越。
* **原点**：算术基本定理（唯一分解定理）——每个大于1的正整数$n$都可以唯一写成$n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$的形式（$p_i$为质数且$p_1\<p_2<\cdots\<p_k$，$e_i\ge1$）。这是整个数论的基石定理，质因数分解法求gcd正是这一核心定理的最直接应用。因为每个数的质因数分解是唯一的，所以它们的"公共部分"——公有质因数最低次幂——也是唯一确定的。质因数分解法将gcd从"试除对比"的操作层面提升到"指数比较"的代数层面：不再需要列举所有因数逐个检验，只需将各数分解到质因数后，对每个质因数的指数逐一取最小值即可。这一跃迁标志着gcd求解从"枚举算法"进入"代数运算"时代，使gcd的求解高度形式化、可预测，并为后续学习最小公倍数（指数取最大）提供了统一且对称的理论框架。
* **道法**：质因数分解法求GCD推理，三锚合一，层层递进。
  * **首锚·质因分解**：将各数按质因数分解为标准分解式，写出每个质因数的指数，确保分解的唯一性和完备性，为后续指数比较奠定基础。
  * **次锚·指数取小**：找出所有公有质因数，对每个公有质因数在各分解式中取指数的最小值，这是"提取公有部分"的精确代数表达。
  * **三锚·相乘得果**：将所有最小指数对应的幂次相乘，所得即为最大公因数，完成从分解到结果的完整推理闭环。
* **关键心法**：
  分解见结构，指数定公因。取小相乘得gcd，指数语言统全局，对偶联通可证lcm。

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

* **终极一句话**：
  $\gcd(a,b)=\prod p^{\min(v_p(a),v_p(b))}$——gcd是质因数分解下指数取最小的乘积，指数最小化将gcd从"枚举找出"升华为"代数得出"，是所有整除性质证明的运算基石。

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

* **数学思想进化轴**：欧几里得《几何原本》（约公元前300年）提出质数定义及质数有无穷多个的证明，奠定了质因数理论的最初基石→高斯《算术研究》（1801）严格证明并阐述算术基本定理，为质因数分解法奠定理论基础，"指数取最小"的概念由此正式确立→狄利克雷（1837）将质因数分解法推广到代数数域，拓展了"指数取最小"思想的适用范围→库默尔（1844）引入理想数概念处理代数数域中的唯一分解问题，将"质因数分解"的视角从整数提升为抽象代数结构中的因子分解→现代数论中"指数取最小"的思想成为交换代数中局部化与赋值论的原型，深刻影响了代数几何中除子理论的发展方向。

# 三、知识点层

* **知识点编号**：B01-M01-S03-U03
* **名称**：质因数分解法求gcd题根
* **标准定义**：
* 定义一（指数取最小定义）：将$a,b$分解为质因数标准式$a=\prod p_i^{\alpha_i}$，$b=\prod p_i^{\beta_i}$（允许指数为$0$以便统一枚举），则$\gcd(a,b)=\prod p_i^{\min(\alpha_i,\beta_i)}$。其中$p_i$取遍两式中的全部质因数，$\min$运算确保了每个质因数的贡献恰好是两式中最小的指数——太少则不"公"，太多则不超过最小者。
  * 定义二（交集定义）：$\gcd(a,b)$是$a$和$b$的质因数集合中公共部分的"最大乘积"——即取公共质因数的各最小指数相乘，这一乘积是所有公因数中最大的那个。例如$a=2^3\times3^2\times5$，$b=2^2\times3^4\times7$，公共质因数集合为${2,3}$，最低指数分别为$2$和$2$，$\gcd=2^2\times3^2=36$。非公有质因数$5$和$7$的指数取$0$，不贡献于结果。

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

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

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

* **核心本质**：**质因数分解法将gcd的求解转化为标准分解式中的指数最小化运算——不再需要穷举所有因数，只需关注质因数的指数比较。这标志着gcd的计算从"枚举操作"上升到了"代数运算"的层次，是一次方法论的跃迁。核心洞察是：gcd不是"找出来的"，而是"从质因数分解中读出来的"——它蕴含在数自身的分解结构中。从更广阔的视角看，指数最小化方法揭示了数学中一个深刻的结构主义思想：一个对象的性质往往在其"构件层面"最容易理解。正如我们可以通过原子的种类和数量理解物质的组成，我们可以通过质因数的种类和指数理解数的gcd关系。质因数分解法的威力在于：它不仅解决了"如何求gcd"的操作问题，更从根本上回答了"gcd是什么"——gcd就是公有质因数最低次幂的乘积，这一理解是后续学习最小公倍数（指数取最大）、互质性判断（指数交集为空）、以及gcd与lcm乘积关系（$ab=\gcd\cdot\text{lcm}$）的理论基础。锁死·拓展应用层通用内容**
* **核心性质**：
  * 性质一：指数最小化的统一性——$\gcd(a,b)$的每个质因数的指数恰好等于$a$和$b$中该指数的最小值。这不仅是计算方法，更是gcd的代数定义。若$a=p^5q^3$，$b=p^2q^7$，则$\gcd(a,b)=p^{\min(5,2)}q^{\min(3,7)}=p^2q^3$。这一形式对任意多个数也成立：$\gcd(a_1,\ldots,a_k)=\prod p^{\min(v_p(a_1),\ldots,v_p(a_k))}$。
  * 性质二：质因数分解法为所有gcd性质提供了证明框架——绝大多数gcd性质都可以通过指数最小化简洁证明。例如$\gcd(ka,kb)=k\gcd(a,b)$：将$a,b$的每个指数$a_i,b_i$乘以$k$的对应指数$k_i$后，$\min(\alpha_i+k_i,\beta_i+k_i)=k_i+\min(\alpha_i,\beta_i)$→提取$k_i$。这种"指数化"证明远比枚举法证明简洁和通用。
  * 性质三：gcd与lcm的指数对偶性——$\gcd(a,b)$取各指数的最小值，而$\text{lcm}(a,b)$取各指数的最大值。两者的乘积恰好恢复为$a$和$b$的乘积：$\min+\max=\alpha+\beta$→$\gcd\times\text{lcm}=a\times b$。这是指数最小化方法的核心美学特征——一对互逆的运算在指数层面天然对称。
  * 性质四：质因数分解法的实用性限制——质因数分解本身对大数来说计算困难（这正是RSA加密的安全性基础）。因此质因数分解法仅在数字不太大、质因数容易获得时有效。例如$\gcd(123456789,987654321)$如果用质因数分解法，需要分解两个九位数；而用辗转相除法只需几步除法即可。这揭示了gcd算法的选择策略：小数用短除法/分解法，大数用辗转相除法。

# 四、教案版本

## 【专业版】

### 【基础层例题】

已知$A=2^3\times3^2\times5$，$B=2^2\times3^4\times7$，求$\gcd(A,B)$。
① 以代数结构思想统领——先找出两数标准分解式中的公有质因数，再取每个公有质因数的最小指数，最后相乘。关键：准确识别公有与非公有质因数，区分两者对结果的不同贡献。
② 常见误区：将非公有质因数（如$5$和$7$）的指数也纳入取最小运算，或忘记某个公有质因数导致漏乘。注意只出现在一个数中的质因数不贡献于gcd。
③ 方法策略：将两个标准分解式上下对齐书写，相同质因数上下对照，一眼即可看出哪些是公有、各指数多大——这种"垂直对齐比较法"将指数取小操作可视化，大幅降低遗漏概率。

* **标准解答**：两数的标准分解式中，公有质因数为$2$和$3$。$2$的指数：$\min(3,2)=2$；$3$的指数：$\min(2,4)=2$。$5$只出现在$A$中、$7$只出现在$B$中，不是公有质因数。故$\gcd(A,B)=2^2\times3^2=4\times9=36$。验算：$A\div36=2^3\times3^2\times5\div(2^2\times3^2)=2\times5=10$，$B\div36=2^2\times3^4\times7\div(2^2\times3^2)=3^2\times7=63$，$10$和$63$互质，结果正确。
  上述解答过程中，每一步推导的依据是该知识点的核心性质——准确把握每一步的逻辑基础，是确保解题正确性的关键。
  这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。
  验证是解题的重要环节——将答案代回原题检验是否满足所有条件，既能确认正确性，也能培养良好的解题习惯。
  这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。### 【易错变式题】
  求$1$和任意正整数$a$的最大公因数。$1$的质因数分解式是什么？
  ① 解题思路：$1$的质因数集合为空集，其与任何数$a$的公有质因数集合也为空集。根据指数取最小定义，空集对应的乘积为$1$（乘法单位元），故$\gcd(1,a)=1$。
  ② 常见错误：认为$1$没有质因数就无法使用质因数分解法，或认为$1$的质因数分解是$1=1^1$从而取$\min$得$1$（指数语言中$1$不是质数，不应出现在分解式中）。
  ③ 方法策略：指数取最小定义包含边界情况——当质因数集合为空时，乘积约定为$1$。这可以推广到更多边界场景：$\gcd(0,a)=|a|$，$\gcd(a,a)=a$，这些边界情况虽不常用，但理解它们有助于构建完整的gcd知识体系。
* **标准解答**：$1$没有质因数，即标准分解式中质因数集合为空集。$\gcd(1,a)$的纯质因数交集为空，故$\gcd(1,a)=1$。更直接的理解：$1$的因数只有$1$，$a$的因数恒包含$1$，故公因数集合为${1}$，最大为$1$。所以$\gcd(1,a)=1$对所有正整数$a$成立。这也可以看作”指数取最小”定义的边界情况：空交集对应乘积为$1$。；上述解答过程中，每一步推导的依据是该知识点的核心性质——准确把握每一步的逻辑基础，是确保解题正确性的关键。；这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。；验证是解题的重要环节——将答案代回原题检验是否满足所有条件，既能确认正确性，也能培养良好的解题习惯。；这道题的核心考点是考查学生对基本概念的准确理解——只有概念清晰，才能从题目条件中识别出可用的结论。
  从思维训练的角度看，这道题考察的核心能力是在复杂条件中识别出可应用该知识点的结构特征——这种识别能力是数学素养的重要组成部分。
  从思维训练的角度看，这道题考察的核心能力是在复杂条件中识别出可应用该知识点的结构特征——这种识别能力是数学素养的重要组成部分。### 【高阶例题】
  已知$a=2^5\times3^3\times5^2$，$b=2^3\times3^5\times5^1$，$c=2^4\times3^1\times5^3$，求$\gcd(a,b,c)$。
  ① 解题思路：推广指数取最小到三个数——逐个枚举公有质因数$2,3,5$，在每个质因数对应的三个指数中取最小值，最后相乘。多个数的gcd求解思路与两数完全相同，只是取最小值的样本量从两个增加到多个。
  ② 常见错误：遗漏某个质因数（如只取了$2$和$3$却忘取$5$），或在比对三个指数时取错最小值。建议将所有标准分解式按质因数排序对齐书写，逐一比较。
  ③ 方法策略：对于三个及以上数的gcd，用"表格对齐法"——将各数的指数按相同质因数排列成表，每一列取最小值，最后一列即为结果。这一方法将多变量取最小运算系统化、可视化，适用于任意个数的gcd计算。
* **标准解答**：先确定三个分解式中的公有质因数为$2,3,5$。对$2$取最小指数：$\min(5,3,4)=3$→$2^3$。对$3$取最小指数：$\min(3,5,1)=1$→$3^1$。对$5$取最小指数：$\min(2,1,3)=1$→$5^1$。故$\gcd(a,b,c)=2^3\times3^1\times5^1=8\times3\times5=120$。验证：$a\div120=2^2\times3^2\times5^1=180$，$b\div120=2^0\times3^4\times5^0=81$，$c\div120=2^1\times3^0\times5^2=50$，$180,81,50$中任意两个的gcd都是$1$（两两互质），整体也互质。

## 【药典版】

### 定位：最大公因数的”代数配方”——一剂指数比较的代数方，质因数分解法将gcd从枚举操作提升为指数最小化的代数运算

#### 🌱 药材本体

* **第一味药——质因分解**：将每个数分解为质因数的幂次乘积，写出标准分解式。这是质因数分解法的启动步骤，也是算术基本定理的实践体现。
* **第二味药——指数比对**：在两份标准分解式中标记出公有质因数，比较每个公有质因数在两个分解式中出现的指数大小。这一步骤是”取最小”的核心操作。
* **第三味药——取小相乘**：对每个公有质因数取最小指数，然后将这些幂次相乘。最小”←保证公因数”、”相乘”←保证最大——两个条件同时满足。
* **第四味药——边界兜底**：处理$1$和$0$等边界情况——$1$的分解式为空集，$\gcd(1,a)=1$；$\gcd(0,a)=|a|$（因为$0$的”倍数集”包含$a$的所有因数）。确保方法覆盖所有整数。
* **药材核心药性**：以分解为体，以指数为用——“分解见结构，取小得公因”。
  这一数学概念的核心特性在于其基础性和工具性——它不仅是解决问题的基础工具，更是连接不同知识模块的桥梁。

#### 🛠️ 功能主治

* **主治**：只会短除法的机械操作但不懂”为什么取这些质因数”——质因数分解法将操作原理完全透明化
* **解决**：面对标准分解式形式的问题（如$a=2^\alpha\times3^\beta$）时无从下手——指数最小化直接给出答案
* **根治**：对gcd的代数结构（指数对偶性、与lcm关系）缺乏深层理解的抽象瓶颈——指数语言是连接gcd与lcm的最短路径
* **打通**：从gcd的”指数取最小”到lcm的”指数取最大”的对称结构，再到一般格论中的交运算和并运算——gcd/lcm是”格”的原始模型

#### 🧪 核心药方

1、**分解对比方**——将各数分解为标准分解式，对比公有质因数，取最小指数乘积。适用于数字可分解、需形式化表达的场合。适配基础表达阶
2、**指数推演方**——直接利用质因数指数形式进行代数推导，不需算出具体数字。例如由$a=2^m3^n$和$b=2^p3^q$直接写出$\gcd(a,b)=2^{\min(m,p)}3^{\min(n,q)}$。适配进阶表达阶
3、**对偶联用方**——同时使用指数取最小（gcd）和指数取最大（lcm），利用$\gcd\times\text{lcm}=a\times b$解决未知数问题。例如已知$\gcd$和$\text{lcm}$求原数，或已知原数求$\gcd$和$\text{lcm}$的关系。适配高阶表达阶

#### 🌌 药理

**质因数分解法用最优雅的语言（指数）重新定义了gcd——不再是”最大的公因数”，而是”公有质因数的最低次幂”。**

这一定义的转型蕴含了深刻的数学思想：当我们从”数”的视角看gcd时，它只是一个数字；但当我们从”分解”的视角看时，它变成一个结构表达式——每个质因数的指数决定了它在gcd中的贡献。这就是数学中”结构主义”思想的雏形：关注对象的构成而非对象本身。

从历史看，质因数分解法的发展经历了漫长的过程。虽然质数的概念早在古希腊时期（欧几里得《几何原本》，公元前300年）就已建立，但”每个整数可以唯一分解为质因数之积”这一事实（算术基本定理）直到高斯《算术研究》（1801）才被严格证明。在高斯之前，数学家们虽然直觉上知道这个性质，但未曾认识到证明的必要性——他们更关注如何分解而非能否分解。

质因数分解法在教学中有一个独特优势：它提供了gcd和lcm的统一框架。一旦学生掌握了”指数取最小得gcd，指数取最大得lcm”，两者之间的关系（$\gcd\times\text{lcm}=a\times b$）就变得显而易见了。更重要的是，这种方法为后续的抽象代数学习（主理想整环中的最大公因子、多项式环中的GCD等）搭建了桥梁。

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

* **基础表达**：先教会学生用短除法或试除法将数字分解为质因数标准式。由$48=2^4\times3$等实例入手，让学生熟练掌握”质因数分解”这一前置技能，再展示”取最小指数相乘”求gcd。
* **进阶表达**：引导学生以指数形式描述任意两个数的质因数分解，形式化地写出$a=\prod p_i^{\alpha_i}, b=\prod p_i^{\beta_i}$，然后直接指出$\gcd=\prod p_i^{\min(\alpha_i,\beta_i)}$。让学生体会从具体数字到符号表达的抽象过程。
* **高阶表达**：将指数最小化推广到任意多个数，同时引入指数对偶性——gcd取最小、lcm取最大。证明$\gcd\times\text{lcm}=a\times b$，让学生感受指数语言的力量。
* **顶阶表达**：将质因数分解法拓展到多项式GCD和其他代数结构中的最大公因子概念。引导学生思考：为什么整数和多项式的GCD定义如此相似？因为它们共享”唯一分解”这个本质结构。

#### 🗣️ 一句话封神

$\gcd(a,b)=\prod p^{\min(v_p(a),v_p(b))}$——把数分解到质因数，gcd就是公有质因数指数取最小的乘积。
数学学习的关键不在于刷了多少题，而在于是否建立了知识之间的联系——当不同模块的知识在心中形成网络，解题就不再是搜索记忆而是自然涌现。
真正的高手不是记得多少公式，而是能看到不同方法背后的统一思想——这就是数学的眼光。#### 🩺 一眼诊断

* **分解卡顿型**：能理解指数最小化概念，但不会分解质因数（如不知$48=2^4\times3$）。→强化质因数分解训练，先用$30,42,66$等简单合数练习，确保”分解”技能先过关再教”取最小”。
* **指数漏取型**：写出标准分解式后漏掉了某些公有质因数（如$2^3\times3^2$和$2^2\times3^4\times5$，只取了$2$忘取$3$）。→养成”逐个枚举质因数”的习惯：先把两式中所有质因数列出，然后逐一判断是否为公有。
* **对偶混淆型**：把gcd和lcm搞混，求gcd时取了最大指数而非最小指数。→强调语义：最大公因数要”公”且”小”——公因数越大越难公，所以只能取最小的指数才能让双方都包含；用$\gcd(4,6)=2$而非$4$做具体对比例子。
* **0/1边界盲区型**：面对$\gcd(0,5)$或$\gcd(1,n)$不知如何处理。→明确规则：$\gcd(0,n)=|n|$，$\gcd(1,n)=1$；质因数分解法的边界情况退化到枚举法处理。

#### 🧭 导航路径

* **步行（L1-L2）** → 对标
  1. 用质因数分解法求$180$和$120$的最大公因数。先把$180$和$120$分解为质因数的标准形式。
     * 解答提示：$180=18\times10=2\times3^2\times2\times5=2^2\times3^2\times5^1$。$120=12\times10=2^2\times3\times2\times5=2^3\times3^1\times5^1$。公有质因数：$2,3,5$。取最小指数：$2^{\min(2,3)}\times3^{\min(2,1)}\times5^{\min(1,1)}=2^2\times3^1\times5^1=4\times3\times5=60$。所以$\gcd(180,120)=60$。

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

2. 已知$X=2^2\times3^5\times7$，$Y=2^4\times3^2\times11$，求$\gcd(X,Y)$。
   * 解答提示：公有质因数：$2$和$3$（$7$和$11$不公有）。取最小指数：$2^{\min(2,4)}=2^2=4$，$3^{\min(5,2)}=3^2=9$。$\gcd=4\times9=36$。验证：$X\div36=2^0\times3^3\times7=189$，$Y\div36=2^2\times3^0\times11=44$，$\gcd(189,44)=1$，正确。

> 深度解析：这里运用的实际上是反证法的思想雏形——通过分析奇偶性矛盾来证明某些情形不可能发生。不变量思想与反证法结合，是竞赛中最强大的组合工具之一。

3. 用质因数分解法证明：$\gcd(a,b,c)=\gcd(\gcd(a,b),c)$——即三个数的gcd可以先求两个再与第三个求。
   * 解答提示：设$a=\prod p^{\alpha_p}$，$b=\prod p^{\beta_p}$，$c=\prod p^{\gamma_p}$。$\gcd(\gcd(a,b),c)=\gcd(\prod p^{\min(\alpha_p,\beta_p)},\prod p^{\gamma_p})=\prod p^{\min(\min(\alpha_p,\beta_p),\gamma_p)}=\prod p^{\min(\alpha_p,\beta_p,\gamma_p)}=\gcd(a,b,c)$。证毕。这证明了gcd运算满足结合律。

> 思维延伸：将这个问题稍作变换——如果把条件中的某条规则改一下，结论是否还成立？这种改变条件观察变化的思维训练，有助于真正理解规则的本质。

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

* **刚性达标阈值**：掌握基础概念，正确率≥90%
* **骑车（L3-L4）** → 对标
  1. 已知$\gcd(a,b)=12$，$\text{lcm}(a,b)=180$，且$a\<b$，求$a,b$所有可能的值。
     * 解答提示：利用$\gcd\times\text{lcm}=a\times b$得$a\times b=12\times180=2160$。设$a=12m,b=12n$，$\gcd(m,n)=1$，则$144mn=2160\Rightarrow mn=15$。互质$(m,n)$对：$(1,15)$→$(12,180)$；$(3,5)$→$(36,60)$；$(5,3)$→$(60,36)$；$(15,1)$→$(180,12)$。限定$a\<b$得$(12,180)$和$(36,60)$。

  2. 求$1\times2\times\cdots\times100$（$100!$）和$1\times2\times\cdots\times101$（$101!$）的最大公因数。
     * 解答提示：$100!$和$101!=101\times100!$。由质因数分解法：$100!$和$101\times100!$的公有质因数就是$100!$的全体质因数（因为$101$是质数且不整除$100!$）。所以$\gcd(100!,101!)=100!$。更一般地：$\gcd(n!,(n+1)!)=n!$。

  3. 证明：$\gcd(a^n,b^n)=(\gcd(a,b))^n$对任意正整数$n$成立。
     * 解答提示：设$a=\prod p^{\alpha_p}$，$b=\prod p^{\beta_p}$，则$a^n=\prod p^{n\alpha_p}$，$b^n=\prod p^{n\beta_p}$。$\gcd(a^n,b^n)=\prod p^{\min(n\alpha_p,n\beta_p)}=\prod p^{n\min(\alpha_p,\beta_p)}=(\prod p^{\min(\alpha_p,\beta_p)})^n=(\gcd(a,b))^n$。这一性质本质上是”取最小”运算与”乘方”运算可交换——先取最小再乘方等于先乘方再取最小。

上述解答过程中，每一步推导的依据是该知识点的核心性质——准确把握每一步的逻辑基础，是确保解题正确性的关键。；这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。- **刚性达标阈值**：能灵活运用解决变式问题，正确率≥85%

* **开车（L5-L6）** → 对标
  1. 求$\gcd(2^{100}-1,2^{120}-1)$。
     * 解答提示：利用恒等式$\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1$。这里$a=2$，$m=100,n=120$，$\gcd(100,120)=20$。所以原式$=2^{20}-1=1048575$。这一恒等式的指数最小化本质：$a^m-1$包含质因数$a^{\gcd(m,n)}-1$（由$m,n$的指数结构决定）。
  2. 设$a,b$为正整数，证明：$\gcd(a+b,\text{lcm}(a,b))=\gcd(a,b)$。
     * 解答提示：设$\gcd(a,b)=d$，$a=dm,b=dn$，$\gcd(m,n)=1$。则$\text{lcm}(a,b)=dmn$。$\gcd(a+b,\text{lcm}(a,b))=\gcd(d(m+n),dmn)=d\gcd(m+n,mn)$。因为$\gcd(m,n)=1$知$\gcd(m+n,mn)=1$（若质数$p\mid m+n$且$p\mid mn$，则$p\mid m$或$p\mid n$，结合$p\mid m+n$得$p\mid(m+n)-m=n$或$(m+n)-n=m$，与互质矛盾）。故原式$=d\times1=\gcd(a,b)$。
  3. 求方程$\gcd(x,y)+\text{lcm}(x,y)=x+y$的所有正整数解$(x,y)$。
     * 解答提示：设$\gcd(x,y)=d$，$x=da$，$y=db$，$\gcd(a,b)=1$。则$\text{lcm}(x,y)=dab$。方程化为：$d+dab=da+db\Rightarrow1+ab=a+b\Rightarrow ab-a-b+1=0\Rightarrow(a-1)(b-1)=0$。所以$a=1$或$b=1$。即$x,y$中一个是另一个的倍数。所以解集为${(x,y)\mid x\mid y\text{或}y\mid x}$，即所有”一个整除另一个”的正整数对。
  * **刚性达标阈值**：能综合解决复杂问题，正确率≥80%