(1) 初等数论

GESP C++五级官方考试大纲中，共有9条考点，本文针对第1条考点进行分析介绍。

（1）掌握初等数论相关知识的概念和应用，包括素数与合数、最大公约数与最小公倍数、同余与模运算、约数与倍数、质因数分解、奇偶性等。 {: .prompt-info}

由于本人也是边学、边实验、边总结，且对考纲深度和广度的把握属于个人理解。因此本文更多的不是一个教程，而是个人知识梳理，如有遗漏、疏忽，欢迎指正、交流。

数论是研究整数（也就是我们常说的“整个数”）的数学分支。初等数论是数论的基础部分，里面有一些简单但很有意思的概念，帮助我们了解数字的“秘密”。

一、素数与合数

1.1 定义

• 素数（质数）：大于1的自然数，如果它只有1和它本身两个因数（只能被1和自己整除），就叫素数。比如：2、3、5、7、11。
• 合数：大于1的自然数，如果它不是素数（也就是说，除了1和它本身，还有其他因数），就叫合数。比如：4（能被2整除）、6（能被2和3整除）、9（能被3整除）。

1.2 说明

• 素数就像数的“基本零件”，因为任何大于1的数都可以用素数乘起来表示。
• 合数则可以“拆开”成更小的数相乘。

二、最大公约数（GCD）与最小公倍数（LCM）

2.1 定义

• 最大公约数（GCD）：两个或多个数的公约数（能同时整除它们的数）中最大的那个。比如，8和12的公约数有1、2、4，最大的是4，所以$\mathrm{GCD}(8, 12) = 4$。
• 最小公倍数（LCM）：两个或多个数的公倍数（它们都能整除的数）中最小的一个。比如，8和12的公倍数有24、48、72，最小的是24，所以$\mathrm{LCM}(8, 12) = 24$。

2.2 计算方法

重点介绍 最大公约数（GCD） 和 最小公倍数（LCM） 的公式和解释

2.2.1 求最大公约数（Greatest Common Divisor, GCD）

求法一：列出所有约数

适合小数：

• 12 的约数：1, 2, 3, 4, 6, 12
• 18 的约数：1, 2, 3, 6, 9, 18 → 最大的公共约数是 6

求法二：辗转相除法（欧几里得算法）

适合大一点的数，步骤如下：

1. 用大数 $\div$ 小数，求余数
2. 用原来的小数和余数再进行除法
3. 一直除下去，直到余数是0
4. 最后那个不为0的数，就是最大公约数！

例如：

步骤：

• $48 \div 18 = 2$ 余 $12$
• $18 \div 12 = 1$ 余 $6$
• $12 \div 6 = 2$ 余 $0$ → 所以 GCD = 6

2.2.2 求最小公倍数（Least Common Multiple, LCM）

最重要的公式：

对于任意两个正整数 a 和 b：

例如：

求 12 和 18 的最小公倍数：

我们已经知道：

• 12 × 18 = 216

• GCD(12, 18) = 6

• 所以：

  $$\text{LCM}(12, 18) = \frac{12 \times 18}{6} = \frac{216}{6} = 36$$

注：最大公约数和最小公倍数的关系

GCD × LCM = 两个数的乘积

$$>\text{GCD}(a, b) \times \text{LCM}(a, b) = a \times b >$$

{: .prompt-tip}

例如：

对于数 $12$ 和 $18$：

• $\text{GCD}(12,18) = 6$
• $\text{LCM}(12,18) = 36$
• $6 \times 36 = 216 = 12 \times 18$

2.3 典型应用场景

• GCD可以用来简化分数，比如$\frac{8}{12}$可以约分成$\frac{2}{3}$。
• LCM能帮我们解决“对齐”问题，比如两个人分别每3天和每4天跑步一次，他们下次一起跑步是第几天？答案是$\mathrm{LCM}(3, 4) = 12$天。

{% include custom/custom-post-content-inner.html %}

三、同余与模运算

3.1 定义

模运算：一个数除以另一个数后取余数。比如，$17 \div 5 = 3$余2，所以$17 \mod 5 = 2$。

同余：如果两个数$a$和$b$除以同一个数$m$余数相同，就说$a$和$b$模$m$同余，写成:

例如，$17 \equiv 7 \pmod{5}$。

3.2 说明

• 同余就像"钟表数学"。比如，钟表是12小时一循环，13点其实就是1点，因为 $13 \equiv 1 \pmod{12}$。
• 在生活中，它可以用来算星期几，或者在计算机里做循环计算。

四、约数与倍数

4.1 定义

• 约数：如果一个数 $d$ 能整除另一个数 $n$（除完没余数），$d$ 就是 $n$ 的约数。比如，$12$ 的约数有 $1$、$2$、$3$、$4$、$6$、$12$。
• 倍数：如果一个数 $m$ 能被另一个数 $n$ 整除，$m$ 就是 $n$ 的倍数。比如，$12$ 是 $3$ 的倍数，因为 $12 \div 3 = 4$。

4.2 说明

• 约数告诉我们一个数能被哪些数整除，倍数告诉我们一个数能整除哪些数。
• 比如，12的约数是1、2、3、4、6、12，它的倍数有12、24、36……

4.3 常用公式

约数个数公式

• 如果一个数的质因数分解是 $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$，它的约数个数是 $(a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$。
• 例子：12 = $2^2 \times 3^1$，约数个数 = $(2 + 1)(1 + 1) = 3 \times 2 = 6$（约数是1、2、3、4、6、12）。

五、质因数分解

5.1 定义

• 把一个大于1的自然数，用素数（质数）相乘的形式表示出来，这个过程就叫做质因数分解。
• 比如，$12$ 可以写成 $2 \times 2 \times 3$。

为什么要学质因数分解？

• 用来求最大公约数、最小公倍数
• 在分数约分中很常用
• 有助于理解数的结构和倍数关系
• 是初中代数和数学竞赛的基础工具 {: .prompt-info}

5.2 定理

• 算术基本定理：每个大于1的自然数都可以唯一地分解成素数相乘（顺序不算）。

5.3 常用分解方法

5.3.1 方法一：短除法（连除法） —— 常用

步骤如下：

1. 从最小的素数 $2$ 开始除
2. 能除尽就一直除；不能除就换下一个素数 $(3,5,7,\ldots)$
3. 一直除到最后结果是 $1$ 为止
4. 把所有除数写下来，它们就是质因数

例如：分解 60

所以：

5.3.2 方法二：分解因数树（因数分解图）

把一个数分解成两个数的乘积，然后继续把每个数再分解，直到每个数都是素数。结构像“树”。

例如：分解 36

        36
       /  \
      6    6
     / \  / \
    2  3 2  3

所以：

判断是否已经分解完成的方法

• 如果每一个因数都是素数，就结束了。
• 常见素数有：2、3、5、7、11、13、17、19… {: .prompt-tip}

5.4 小技巧

• 如果一个数是偶数，一定可以先除以2。
• 如果个位数是5或0，可以除以5。
• 如果各位数字加起来是3的倍数，可以除以3。

六、奇偶性

6.1 定义

• 偶数：能被2整除的数，比如2、4、6、8。
• 奇数：不能被2整除的数，比如1、3、5、7。

6.2 说明

• 奇偶性的一般规律：
  • $\text{奇数} + \text{奇数} = \text{偶数}$（比如$3 + 5 = 8$）
  • $\text{偶数} + \text{偶数} = \text{偶数}$（比如$4 + 6 = 10$）
  • $\text{奇数} + \text{偶数} = \text{奇数}$（比如$3 + 4 = 7$）
  • $\text{奇数} \times \text{奇数} = \text{奇数}$（比如$3 \times 5 = 15$）
  • $\text{偶数} \times \text{偶数} = \text{偶数}$（比如$4 \times 6 = 24$）
  • $\text{奇数} \times \text{偶数} = \text{偶数}$（比如$3 \times 4 = 12$）
• 这些规律在数学证明中经常用到。

七、总结

素数和合数是最基本的分类，GCD和LCM帮我们处理分数和周期问题，同余让我们看到数的循环规律，约数和倍数揭示数的除法关系，质因数分解把数拆成“零件”，奇偶性则带来简单的加法、乘法规律。

{% include custom/custom-post-content-footer.md %}

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP 认证学习微信公众号