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

# 一、模块层

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

## 纵向关联

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

## 知识关联

### 横向关联

* 前置基础：
  * `整式次数与项数题根`
  * `事件关系判断题根`
* 同位衔接：
  * `排列组合区分题根`
  * `混合计数题根`
  * `分类与枚举结合题根`
* 后续延伸：
  * [σ(n)计算题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S01/B01-M04-S01-U02)
  * [反证法数论题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S02/B01-M04-S02-U01)
  * [二次剩余定义题根](/root/B01-数论基础/M02-同余理论/S07/B01-M02-S07-U01)
  * [非互质模化简题根](/root/B01-数论基础/M03-不定方程/S04/B01-M03-S04-U03)
  * [模分析题根](/root/B01-数论基础/M03-不定方程/S06/B01-M03-S06-U02)
  * [数学归纳法数论题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S02/B01-M04-S02-U02)
  * [τ(n)计算题根](/root/B01-数论基础/M04-数论函数与进阶技巧/S01/B01-M04-S01-U01)
  * [费马小定理推广题根](/root/B01-数论基础/M02-同余理论/S03/B01-M02-S03-U05)

# 二、本源层

* **本源**：枚举法求最大公因数（GCD）的核心逻辑是"列出全部可能，从中选出最大公有的一个"——对正整数$a$和$b$，$\gcd(a,b)=\max{d\in\mathbb{N}^+\mid d\mid a\ \text{且}\ d\mid b}$。枚举法直接基于最大公因数的定义运作：分别列出$a$和$b$的所有正因数，求出两因数集合的交集，从交集中取出最大元素即可得到$\gcd$。这是"定义即算法"在数学中的典型范例——概念怎么说，操作就怎么做。枚举法的精髓在于它让抽象的gcd定义转化为具体可操作的流程步骤，使学生无需任何额外技巧就能直观理解最大公因数的本质含义，为后续学习短除法、质因数分解法等高效算法奠定坚实的理解基础。
* **原点**：任一正整数$a$的因数集是有限且可穷举的——因为若$d\mid a$且$d>0$，则必有$1\le d\le a$，这意味着因数个数不可能超过$a$本身。因此通过逐一检查区间$\[1,\min(a,b)]$内的每个正整数是否同时整除$a$和$b$，一定能找出两数的所有公因数并从中确定最大值。这一"有限搜索$\rightarrow$逐一验证$\rightarrow$取最大值"的三段式流程，不仅构成了计算机科学中暴力搜索算法的原始模型，更在数学教育中扮演着"从定义到算法"的关键启蒙角色——它让学生在亲手操作中直观感悟"最大公因数究竟是什么"。枚举法虽然效率不高，却是零技巧前提下理解gcd概念的必经之路。正是通过这种"笨办法"的亲自实践，学生才真正建立起"最大公因数是所有公因数中最大的那个"这一核心概念，从而为后续学习短除法、辗转相除法等高效算法奠定坚实的理解基础。枚举法本质上是在有限搜索空间中通过逐一验证来求解，这种思想范式贯穿了整个数学和计算机科学领域。
* **道法**：首锚·枚举思想推理，次锚·有序思考推理，三锚·分类讨论推理。枚举法求GCD的标准路径：(1)列出较小数的所有正因数——从$1$到$\min(a,b)$逐一试除，记录能整除者；(2)判断这些因数是否也是较大数的因数——逐一检查整除性；(3)从公共因数中找出最大值。优化技巧：只需列出较小数的因数，因为较大数的因数只会更多。(4)对大数可采用对称缩小策略：检查到$\lfloor\sqrt{n}\rfloor$即可成对获取所有因数。三锚合一，层层递进。
* **终极一句话**：$\gcd(a,b)=\max{d\in\mathbb{N}^+\mid d\mid a\ \text{且}\ d\mid b}$——枚举法是最大公因数定义的直接执行，是"看见即可得"的最朴素方法。它不依赖任何技巧或公式，仅凭"逐一列出$\rightarrow$逐一验证$\rightarrow$取最大值"三步骤，便完成了从抽象定义到具体数值的完整转化，成为一切gcd算法之母。
* **关键心法**：枚举穷尽不遗漏，逐一验证得公因；定义驱动真算法，零基入门最自然。最大公因从中取，数论算法此为基。
* **数学思想进化轴**：欧几里得《几何原本》（约公元前300年）第七卷首次以线段公度的形式系统讨论最大公因数概念并建立互质定义→斐波那契《计算之书》（1202）将枚举法明确用于整数GCD计算，系统列举大量实例并总结计算规律，使枚举法从哲学概念发展为实用计算工具→施蒂费尔《整数算术》（1544）系统整理质因数分解方法，为枚举法向质因数分解法过渡提供了技术基础→高斯《算术研究》（1801）严格证明算术基本定理，将gcd纳入同余和代数结构框架，使枚举法从"手工操作"升华为"算法概念"的理论基石→20世纪计算机科学兴起后，枚举法的思想范式深刻影响了暴力搜索、穷举法等基础算法设计理念，其"定义驱动算法"的原始模型在算法教学中至今不可替代。

# 三、知识点层

* **知识点编号**：B01-M01-S03-U01
* **名称**：枚举法求gcd题根
* **标准定义**：
* 定义一（最大公因数定义法）：对正整数$a,b$，若正整数$d$满足$d\mid a$且$d\mid b$，则$d$是$a$和$b$的一个公因数。所有公因数中的最大者记为$\gcd(a,b)=\max{d\in\mathbb{N}^+\mid d\mid a\ \text{且}\ d\mid b}$。枚举法直接基于这一定义：分别列出$a$和$b$的所有正因数，取两因数集合的交集，再从交集中取出最大元素即为$\gcd(a,b)$。这一定义揭示了枚举法的本质——它既是从最小公因数$1$到最大可能值$\min(a,b)$之间的逐一搜索过程，也是集合论中交运算与比较运算结合的初步实践。特别地，当两数互质时，公因数集合只有${1}$，此时枚举的结果为$\gcd(a,b)=1$。
  * 定义二（素数幂分解形式）：若$a=p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$且$b=p_1^{\beta_1}p_2^{\beta_2}\cdots p_k^{\beta_k}$（允许指数为$0$），则$\gcd(a,b)=p_1^{\min(\alpha_1,\beta_1)}p_2^{\min(\alpha_2,\beta_2)}\cdots p_k^{\min(\alpha_k,\beta_k)}$。这一定义揭示了枚举法的深层对象——当"枚举因数"升级为"枚举质因数"时，枚举法就自然地转化为质因数分解法。两种定义的内在同一性体现了数论的结构之美：公因数的集合描述与指数描述是等价的，枚举法的操作过程恰好是在执行这一定义的算法化表达。

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

* **核心本质**：
  **枚举法将最大公因数的定义直接转化为操作流程——无需预备知识或技巧，只需穷尽有限种可能并从中筛选出最大值。这是"定义驱动算法"的数学原型，也是学生理解算法概念的第一个自然起点。从"知道gcd是什么"到"能求出gcd"之间，枚举法是最近的一座桥。枚举法的每一步操作都有定义作依据：列出因数对应"若$d\mid a$则$d$是因数"，取交集对应"公因数需同时满足$d\mid a$且$d\mid b$"，取最大值对应"$\gcd$是公因数中最大的那个"。这种定义与操作的严格对应，使枚举法成为数论教学中连接抽象概念与具体计算的最佳范例。锁死·拓展应用层通用内容**

这一本质深刻揭示了一个事实：表面上的数值多样性掩盖了底层的结构统一性。一旦掌握了这个统一性，看似千变万化的问题都可以归结为同一种分析框架来处理。

* **核心性质**：
  * 性质一：枚举的有限性——任何正整数$n$的正因数个数不超过$n$，且实际远小于$n$（例如$n=100$只有$9$个正因数：$1,2,4,5,10,20,25,50,100$）。这保证了枚举在数字较小时高效可行。因数的个数随$n$增大而增长缓慢（平均约$\ln n$个），1000以内的数通常只需尝试几十次，这是枚举法教学可行性的数学保障。
  * 性质二：公因数的最大性——若$d$是$a$和$b$的任一公因数，则$d\le\gcd(a,b)$。这意味着$\gcd(a,b)$不仅是所有公因数中的最大值，而且任何公因数都受它约束。这一看似平凡的性质为"最大"二字提供了严密数学保障：公因数集合有上界$\min(a,b)$，因此最大值必然存在且唯一。
  * 性质三：公因数的生成传递性——若$d$是$a$和$b$的公因数，则$d$整除$\gcd(a,b)$的任何整数倍。反之，$\gcd(a,b)$的任何正因数都是$a$和$b$的一个公因数。这一双向性质揭示了$\gcd(a,b)$作为"公因数生成元"的代数本质——所有公因数恰好是$\gcd(a,b)$的全体正因数。
  * 性质四：枚举法的效率瓶颈——当数字较大时，枚举法不再可行。例如求$\gcd(12345,67890)$，即使只枚举较小数$12345$的因数，也需检查$12345$次除法，手工计算几乎不可行。这一局限自然驱动了短除法（质因数分解法）和辗转相除法（欧几里得算法）的引入——枚举法不是求GCD的终极方法，却是理解GCD概念和算法思想的最佳起点。

# 四、教案版本

## 【专业版】

### 【基础层例题】

用枚举法求24和36的最大公因数。

* **解题思路**：①提取条件：正整数$a=24$和$b=36$，用枚举法求最大公因数。②参照范例步骤：从小到大逐一列出两数的所有正因数，取两因数集合的交集，再从中找出最大值——24的因数有$1,2,3,4,6,8,12,24$，36的因数有$1,2,3,4,6,9,12,18,36$，公有因数为${1,2,3,4,6,12}$。③预判答案：$\gcd(24,36)=12$，验证两商互质即可确认。
* **标准解答**：24的正因数从小到大：$1,2,3,4,6,8,12,24$。36的正因数：$1,2,3,4,6,9,12,18,36$。公有因数为${1,2,3,4,6,12}$，其中最大的是$12$。故$\gcd(24,36)=12$。验证：$24\div12=2$，$36\div12=3$，商互质。
  上述解答过程中，每一步推导的依据是该知识点的核心性质——准确把握每一步的逻辑基础，是确保解题正确性的关键。
  这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。
  验证是解题的重要环节——将答案代回原题检验是否满足所有条件，既能确认正确性，也能培养良好的解题习惯。
  这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。### 【易错变式题】
  用枚举法求0和12的最大公因数。0的”因数”是什么？
* **常见错误**：①错误行为：认为0没有正因数或$0\div0$无意义而判定gcd不存在，或将$\gcd(0,12)$误算为$0$。②认知原因：不理解任何非零整数都整除$0$（$0=d\times0$），且误以为"0没有因数"意味着"gcd不存在"。③忽视点：$\gcd(0,n)=|n|$——0的因数集是全体正整数，故gcd取另一数的值而非0。
* **标准解答**：根据整除定义，任何非零整数$d$都整除$0$（因为$0=d\times0$），所以$0$的”因数集”是全体正整数。$12$的正因数有$1,2,3,4,6,12$。两者的公共部分是${1,2,3,4,6,12}$，最大者为$12$。因此$\gcd(0,12)=12$。一般结论：$\gcd(0,n)=|n|$对一切$n\neq0$成立。；上述解答过程中，每一步推导的依据是该知识点的核心性质——准确把握每一步的逻辑基础，是确保解题正确性的关键。；这道题还可以从另一个角度切入：通过构造等价条件或转化视角，往往能得到更简洁的解法。；验证是解题的重要环节——将答案代回原题检验是否满足所有条件，既能确认正确性，也能培养良好的解题习惯。；这道题的核心考点是考查学生对基本概念的准确理解——只有概念清晰，才能从题目条件中识别出可用的结论。；解答这类问题时，建议先明确已知条件与所求目标之间的逻辑关系，再进行逐步推导，避免跳步导致的逻辑漏洞。
  从思维训练的角度看，这道题考察的核心能力是在复杂条件中识别出可应用该知识点的结构特征——这种识别能力是数学素养的重要组成部分。
  从思维训练的角度看，这道题考察的核心能力是在复杂条件中识别出可应用该知识点的结构特征——这种识别能力是数学素养的重要组成部分。### 【高阶例题】
  求满足$\gcd(a,b)=6$且$a+b=30$的所有正整数对$(a,b)$，其中$a\le b$。
* **方法策略**：①问题类型：已知$\gcd(a,b)=6$和$a+b=30$，求所有正整数对$(a,b)$。②方法选择：设参数法——由$\gcd(a,b)=6$设$a=6m,b=6n$，利用$\gcd(m,n)=1$将条件转化为互质枚举。③分类/步骤：设参数$a=6m,b=6n$→由和条件列方程$m+n=5$→枚举和为5的互质数对$(1,4),(2,3)$→还原原数并验证。
* **标准解答**：设$a=6m$，$b=6n$，其中$m,n$为正整数且$\gcd(m,n)=1$（提取全部公因数后剩余部分必互质）。代入$a+b=30$得$6(m+n)=30\Rightarrow m+n=5$。枚举和为$5$且互质的$(m,n)$对：$m=1,n=4$，$\gcd(1,4)=1$✓；$m=2,n=3$，$\gcd(2,3)=1$✓。对应$(a,b)$为$(6,24)$和$(12,18)$。答案：$(6,24)$和$(12,18)$。

## 【药典版】

### 定位：最大公因数的”定义即算法”——一剂回归本源的入门方，枚举法用最原始的方式，让定义自己说话

#### 🌱 药材本体

* **第一味药——因数清册**：从$1$到$n$逐一试除，记录所有能整除$n$的正整数——建立完整因数清单。这是枚举的第一步，也是”定义驱动”的开端。
* **第二味药——公因筛选**：将两份因数清册对照，挑出同时出现在两清单中的数——找到全部公因数。这是从”各自因数”到”公共因数”的集合运算实践。
* **第三味药——最大枚冠**：从公因数列表中选出最大值——这是gcd定义在枚举框架下的最终落地。枚举法至此完成了从定义到结果的完整路径。
* **第四味药——检约判互**：根据最大公因数是否为1，判断两数是否互质。这是枚举法的延伸应用——枚举法不仅求gcd，还自然回答”两数是否互质”的问题。
* **药材核心药性**：以定义为体，以枚举为用——“定义怎么说，算法就怎么做”。
  这一数学概念的核心特性在于其基础性和工具性——它不仅是解决问题的基础工具，更是连接不同知识模块的桥梁。

#### 🛠️ 功能主治

* **主治**：学生不理解”最大公因数究竟是什么意思”——枚举法让定义可视化、操作化，使抽象的gcd概念变得可见可触
* **解决**：面对较小数字(≤100)不会求gcd的操作困境——只需逐个数检查，零门槛入门，不依赖任何除法之外的预备技能
* **根治**：算法思维缺失——枚举法让学生亲历”列出→筛选→取最大”的完整算法流程，建立算法直觉，理解”算法”的本质就是”按确定步骤求解”
* **打通**：从枚举法→短除法→质因数分解法→辗转相除法的算法进化链条——理解了枚举的朴素，就理解了为什么需要更好的算法

#### 🧪 核心药方

1、**全面枚举方**——分别列出两数的所有正因数，取公共最大者。适用于数字≤100的入门操作，零基础可完成。适配基础表达阶
2、**对称缩小方**——只需枚举到$\lfloor\sqrt{n}\rfloor$即可成对获得所有因数。例如求$\gcd(48,72)$：枚举$1,2,\ldots,6$（$\sqrt{48}\approx6.9$），成对得全部因数，再取公共最大，枚举量减少一半以上。适配进阶表达阶
3、**参数枚举方**——由$\gcd(a,b)=d$设$a=dm,b=dn$且$\gcd(m,n)=1$，转化为$m,n$的互质枚举问题。用于解与gcd相关的方程和整数拆分问题，将枚举对象从”因数”提升为”互质对”。适配高阶表达阶

#### 🌌 药理

**枚举是最笨的方法，也是最聪明的方法——因为它从不撒谎。**

枚举法的魅力在于它的”诚实”：它不依赖任何技巧或公式，只是严格遵循最大公因数的定义一步步操作。”列出所有因数”的每一步都对应着整除定义的一次应用，”找出公共最大”的每一步都对应着集合概念的一次实践。这使枚举法成为gcd概念教学的天然起点——学生不仅仅学会了计算，更通过动手操作，在头脑中建立了”什么是最大公因数”的真实图景。

从历史看，枚举法是人类认识gcd的第一个方法。欧几里得在《几何原本》（公元前300年）第七卷中首先以”线段公度”的方式定义最大公因数——两条线段能否用同一单位测量？这本质上就是枚举所有可能的”单位”并找出最大的。中世纪数学家斐波那契在《计算之书》（1202）中系统使用枚举法求解整数GCD问题，并给出完整例题。直到17世纪，随着天文学和航海计算推动大数运算，数学家才开始寻找更高效的算法。

枚举法的教学价值不在于它的效率，而在于它的”可理解性”——它是从”知道gcd定义”到”能求出gcd”之间最自然的一座桥。走过这座桥，学生才能理解为什么需要短除法、辗转相除法等更高效的算法。

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

* **基础表达**：教会学生从$1$到$\min(a,b)$逐一试除列因数。先用$24$和$36$这样的小数字操作，让学生自己发现”公因数集合”和”最大公约数”的对应关系。关键教具：在黑板上逐一列出因数，用不同颜色标记公有和独有部分，让”最大”二字直观可见。
* **进阶表达**：引入对称缩小法，让学生理解”因数是成对出现的”（若$d\mid n$则$(n/d)\mid n$）。通过$\gcd(48,72)$等示范，让学生体会”枚举到平方根就够”的优化，感受算法优化带来的便利。
* **高阶表达**：将枚举法转化为参数法——“已知gcd求原数”的问题本质上是枚举互质的$(m,n)$对。这需要学生理解”提取公因数后剩余部分必互质”这一核心逻辑，将问题从”因数枚举”升级为”互质枚举”。
* **顶阶表达**：引导学生将枚举法与其他算法对比——枚举法是$O(n)$，短除法是$O(\sqrt{n})$（分解复杂度），辗转相除法是$O(\log n)$。通过效率对比让学生理解”算法进步”的本质意义，培养算法分析和优化的思维方式。

#### 🗣️ 一句话封神

$\gcd(a,b)=\max{d\mid d\mid a\text{且}d\mid b}$——枚举法是gcd定义的直接执行，让”定义自己说话”。
数学学习的关键不在于刷了多少题，而在于是否建立了知识之间的联系——当不同模块的知识在心中形成网络，解题就不再是搜索记忆而是自然涌现。
真正的高手不是记得多少公式，而是能看到不同方法背后的统一思想——这就是数学的眼光。#### 🩺 一眼诊断

* **因数遗漏型**：列举因数时漏掉某几个（如48的因数漏写16或24）。→引导学生用成对法：从$1$到$\sqrt{n}$检查，发现$d$的同时写下$n/d$，保证不重不漏。
* **公因错认型**：列了因数但找错公因数（如把24的因数8当成36的因数）。→强调必须在两因数清册中”共同出现”才算公因数，使用两列对照表或维恩图辅助观察。
* **概念混淆型**：把最大公因数当成”最大公倍数”或”最小公倍数”。→回到定义：公因数是”能同时整除两数的数”，最大是”其中最大的那个”。必须用具体数值验证，如$\gcd(4,6)=2$而非$4$。
* **参数断链型**：设$a=dm,b=dn$后忘记$\gcd(m,n)=1$条件导致多解。→强调提取全部公因数后剩余必互质，可反问”如果不互质会怎样？”引导学生自己推出矛盾。

#### 🧭 导航路径

* **步行（L1-L2）** → 对标
  1. 用枚举法求18和27的最大公因数：分别列出18和27的所有正因数，找出公共部分的最大值。
     * 解答提示：$18=2\times3^2$，其正因数为$1,2,3,6,9,18$。$27=3^3$，其正因数为$1,3,9,27$。公因数：${1,3,9}$，最大为$9$。所以$\gcd(18,27)=9$。验证：$18\div9=2$，$27\div9=3$，商互质。

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

2. 判断14和25是否互质（即最大公因数是否为1）。
   * 解答提示：14的正因数：$1,2,7,14$。25的正因数：$1,5,25$。公因数只有${1}$，最大值$1$。所以$\gcd(14,25)=1$，两数互质。关键：互质的定义就是最大公因数为1，而不是”没有公因数”——1永远是公因数。

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

3. 三个数48, 60, 84的最大公因数是多少？（分别列出三数的所有正因数，找共同的）
   * 解答提示：48的正因数：$1,2,3,4,6,8,12,16,24,48$。60的正因数：$1,2,3,4,5,6,10,12,15,20,30,60$。84的正因数：$1,2,3,4,6,7,12,14,21,28,42,84$。三者的公因数：${1,2,3,4,6,12}$，最大为$12$。所以$\gcd(48,60,84)=12$。

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

* **刚性达标阈值**：掌握基础概念，正确率≥90%
* **骑车（L3-L4）** → 对标
  1. 已知$\gcd(a,b)=4$且$a\times b=240$，求所有可能的正整数对$(a,b)$（设$a\le b$）。
     * 解答提示：设$a=4m,b=4n$，$\gcd(m,n)=1$，则$a\times b=16mn=240\Rightarrow mn=15$。枚举互质的$(m,n)$对（$m\le n$且$mn=15$）：$(1,15)$，$\gcd(1,15)=1$✓；$(3,5)$，$\gcd(3,5)=1$✓。对应$(a,b)=(4,60)$和$(12,20)$。注意$(15,1)$和$(5,3)$是$m>n$的对称解，若无限定$a\le b$也需计入。
  2. 用枚举法求$\gcd(2^3\times3^2,2^2\times3\times5)$——不计算具体数值，只用标准分解式比较指数。
     * 解答提示：写成标准分解式：$2^3\times3^2\times5^0$和$2^2\times3^1\times5^1$。枚举公有质因数：$2$和$3$。取最小指数：$2^{\min(3,2)}=2^2$，$3^{\min(2,1)}=3^1$。$5$不是公有质因数（第一个数指数为$0$，$5^0=1$）。故$\gcd=2^2\times3^1=12$。这是枚举法向质因数分解法的自然过渡。
  3. 证明：若$a\mid bc$且$\gcd(a,b)=1$，则$a\mid c$。
     * 解答提示：由$\gcd(a,b)=1$，存在整数$x,y$使$ax+by=1$（裴蜀定理）。两边乘以$c$：$acx+bcy=c$。由于$a\mid acx$且$a\mid bcy$（因为$a\mid bc$），故$a\mid(acx+bcy)=c$，证毕。这条性质在数论证明中极为常用——它说明”与一方互质的因数可穿透乘法”。

上述解答过程中，每一步推导的依据是该知识点的核心性质——准确把握每一步的逻辑基础，是确保解题正确性的关键。- **刚性达标阈值**：能灵活运用解决变式问题，正确率≥85%

* **开车（L5-L6）** → 对标
  1. 求$\gcd(2^{100}-1,2^{120}-1)$。
     * 解答提示：利用性质$\gcd(a^m-1,a^n-1)=a^{\gcd(m,n)}-1$（对$a>1$成立）。这里$a=2$，$m=100,n=120$，$\gcd(100,120)=20$。所以$\gcd(2^{100}-1,2^{120}-1)=2^{20}-1=1048575$。这一性质可由辗转相除法推导，是指数形式下枚举法的推广。
  2. 证明：对任意正整数$n$，$\gcd(n!+1,(n+1)!+1)=1$。
     * 解答提示：设$d=\gcd(n!+1,(n+1)!+1)$。则$d\mid\[(n+1)!+1]-n!+1$的线性组合。注意$(n+1)!+1=(n+1)n!+1$，相减得$n\cdot n!$，所以$d\mid n\cdot n!$。同时$d\mid n!+1$。若$d>1$，则$d$有质因数$p$，由$p\mid n!+1$知$p\nmid n!$（$n!+1$与$n!$互质），但由$p\mid n\cdot n!$知$p\mid n!$或$p\mid n$，矛盾。故$d=1$。
  3. 证明：相邻两个斐波那契数$\gcd(F_n,F\_{n+1})=1$对一切$n\ge1$成立。
     * 解答提示：用欧几里得算法思想：$F\_{n+1}=F_n+F\_{n-1}$，所以$\gcd(F\_{n+1},F_n)=\gcd(F_n,F\_{n-1})$。持续应用得$\gcd(F\_{n+1},F_n)=\gcd(F_2,F_1)=\gcd(1,1)=1$。这本质上是枚举法在递归结构中的延伸——通过递推不断缩小被枚举的数对，直至平凡情形。
  * **刚性达标阈值**：能综合解决复杂问题，正确率≥80%