第一章：算术平原的基石——自然数、质数与四则运算

自然数：算术平原的基石

当逻各斯（Logos）的意識觸及數學王國的第一片領地——算术平原 (Arithmetic Plain) 時，他看到的不是山川草木，而是一個由無數光點構成的、井然有序的數字群落。這些光點按照大小依次排列，從最小的點開始，逐個增加，無窮無盡。平原的守護者，一位 prudent 的數字精靈，正為一項緊急的資源分配任務蹙眉：如何將 120 顆魔法水晶 公平地分發給 8 個村落，使得每個村落獲得的數量既是整數，又能滿足後續建設對水晶質地的特殊要求（即水晶總數需表示為某些‘質數’的乘積）？這個看似簡單的分配問題，卻牽扯出算術世界最根本的結構——自然数 (Natural Numbers) 及其深層性質。

1.1 自然数的定义与基本性质

定义 1.1（自然数 (Natural Numbers)） 在本书中，自然数 指的是从 1 开始的正整数序列，即集合 $$\mathbb{N} = \{1, 2, 3, 4, \dots\}$$ （*注：部分现代数学文献将 0 纳入自然数集，但本章为与“质数”定义（大于1）及传统算术衔接，采用从1开始的约定。关于0的哲学与数学争议，可参见侧边栏。*）

自然数是人类最原始、最直观的数学抽象，源于对“计数”的需要。它们构成了算术平原的所有居民，所有后续的算术运算和数论概念都建立在这个集合之上。其最核心的性质可归纳为以下几点：

1. 离散性与有序性：自然数集是离散的，任意两个不同的自然数之间都存在有限个自然数（例如，在5与8之间，有6、7）。同时，它带有天然的全序关系（≤），即对于任意 $a, b \in \mathbb{N}$，必有 $a < b$、$a =

逻各斯凝视着这些光点，数字精灵轻声吟诵：“它们彼此不同，却又遵循着不可违背的秩序。任意两个，必可比较大小；且从最小的起点出发，总能到达任何一个。” 这揭示了自然数集的良序性 (Well-ordering Principle)：N的任何非空子集都含有一个最小元。这一看似显然的性质，是数学归纳法的基石，也是证明许多数论命题的“终极武器”。例如，要证明所有自然数都具有某性质P，可假设存在反例，由良序性，反例集合有最小元m；再证明m不可能存在，从而导出矛盾。这种最小反例法在后续证明算术基本定理的唯一性时将大放异彩。

1.2 四则运算的代数结构：半群、幺半群与群的萌芽

算术平原的居民日常活动，离不开四种基本操作：加法 (Addition)、减法 (Subtraction)、乘法 (Multiplication)、除法 (Division)。然而，在自然数集 $\mathbb{N}$ 这个封闭的舞台上，这四位“演员”的表现却不尽相同。逻各斯很快发现，它们各自的“行为模式”构成了不同的代数结构 (Algebraic Structures)。

1.2.1 加法与乘法：封闭、结合与交换

定义在集合上的二元运算，首先需满足封闭性 (Closure)：运算结果仍属于该集合。

• **加法**：对任意 $a, b \in \mathbb{N}$，$a + b \in \mathbb{N}$。例如 $5 + 7 = 12 \in \mathbb{N}$。
• **乘法**：对任意 $a, b \in \mathbb{N}$，$a \times b \in \mathbb{N}$。例如 $4 \times 6 = 24 \in \mathbb{N}$。

其次，结合律 (Associativity) 允许我们摆脱括号的束缚，进行连续运算：

• $(a + b) + c = a + (b + c)$。例如 $(2 + 3) + 4 = 5 + 4 = 9$，$2 + (3 + 4) = 2 + 7 = 9$。
• $(a \times b) \times c = a \times (b \times c)$。例如 $(2 \times 3) \times 4 = 6 \times 4 = 24$，$2 \times (3 \times 4) = 2 \times 12 = 24$。

再者，交换律 (Commutativity) 让我们可以交换操作数的位置：

• $a + b = b + a$。例如 $3 + 5 = 5 + 3 = 8$。
• $a \times b = b \times a$。例如 $4 \times 7 = 7 \times 4 = 28$。

这些性质是自然数加法和乘法运算的“本能”，使得长串计算成为可能。然而，它们并非所有运算的共性。

1.2.2 减法与除法：封闭性的缺失与运算的局限

当逻各斯尝试用减法解决“从8颗水晶中取出3颗后还剩几颗”时，$8 - 3 = 5 \in \mathbb{N}$，似乎顺利。但若问“从3颗中取出8颗”，$3 - 8$ 在 $\mathbb{N}$ 中无解。减法在自然数集上不封闭。同理，除法 $a \div b$ 要求 $b$ 整除 $a$ 才有自然数解，如 $12 \div 4 = 3 \in \mathbb{N}$，但 $7 \div 3 \notin \mathbb{N}$。除法在自然数集上也不封闭。

这种封闭性的缺失，揭示了 $\mathbb{N}$ 作为算术运算舞台的不完整性。为了解决“不够减”或“除不尽”的问题，数学王国必须向更广阔的领域拓展：引入整数集 $\mathbb{Z}$（包含负整数）使减法封闭；引入有理数集 $\mathbb{Q}$（包含分数）使除法（除数非零）封闭。但那是后续章节的旅程。在算术平原，我们只关注那些在 $\mathbb{N}$ 内永远有意义的运算——加法和乘法。

1.2.3 单位元与零元：运算的“中立者”

一个代数结构如果存在一个元素 $e$，使得对任意 $a$ 都有 $a * e = e * a = a$，则 $e$ 称为单位元 (Identity Element)。

• **加法**的单位元是 **0**。但根据本章自然数从1开始的约定，$0 \notin \mathbb{N}$。因此，在 $(\mathbb{N}, +)$ 中，**加法没有单位元**。这是一个关键的结构差异。
• **乘法**的单位元是 **1**。$a \times 1 = 1 \times a = a$ 对所有 $a \in \mathbb{N}$ 成立，且 $1 \in \mathbb{N}$。故 $(\mathbb{N}, \times)$ 有乘法单位元。

此外，若存在元素 $z$ 使得 $a * z = z * a = z$ 对所有 $a$ 成立，则 $z$ 为零元 (Zero Element)。

• 在乘法中，**0** 是零元（$a \times 0 = 0 \times a = 0$），但 $0 \notin \mathbb{N}$（按本章约定），故 $(\mathbb{N}, \times)$ 也无零元。
• 在加法中，若考虑扩展集，但在此无关。

1.2.4 代数结构的小结：从半群到幺半群

基于以上分析，我们可以定义两个核心结构：

• **半群 (Semigroup)**：一个集合配上一个满足**封闭性**和**结合律**的二元运算。
• $(\mathbb{N}, +)$：封闭、结合、交换，但无单位元（因0不在N中）。它是一个**交换半群**。
• $(\mathbb{N}, \times)$：封闭、结合、交换，且有单位元1。它是一个**交换幺半群 (Commutative Monoid)**。**幺半群**是半群加上单位元。

关键洞察：自然数集上的加法和乘法，虽然都是交换的，但乘法因拥有单位元1而具有更丰富的结构。这种结构差异在抽象代数中至关重要，它决定了我们能否定义“逆运算”。在 $(\mathbb{N}, \times)$ 中，元素 $a$ 的逆是 $1/a$，但 $1/a \notin \mathbb{N}$（除非 $a=1$），故乘法逆运算在 $\mathbb{N}$ 中不封闭。这再次印证了 $\mathbb{N}$ 的局限性。

下表总结了自然数集上四则运算的代数性质：

| 运算 | 封闭性 | 结合律 | 交换律 | 单位元 (在 $\mathbb{N}$ 中?) | 结构类型 | | :--- | :---: | :---: | :---: | :---: | :--- | | 加法 (+) | ✓ | ✓ | ✓ | 0 (✗, 0∉N) | 交换半群 | | 乘法 (×) | ✓ | ✓ | ✓ | 1 (✓) | 交换幺半群 | | 减法 (−) | ✗ | ✗ | ✗ | 无 | 非结构 | | 除法 (÷) | ✗ | ✗ | ✗ | 无 | 非结构 |

*表 1.1：自然数集 $\mathbb{N}$ 上四则运算的代数性质对照*

> 侧边栏：关于 0 的哲学与数学地位 > 在本章中，我们采用 $\mathbb{N} = \{1, 2, 3, \dots\}$ 的约定，主要出于与“质数”（定义要求大于1）及传统算术叙述的衔接。然而，将0纳入自然数集（$\mathbb{N}_0 = \{0, 1, 2, \dots\}$）在现代集合论、计算机科学和分析学中更为普遍。此时，$(\mathbb{N}_0, +)$ 成为交换幺半群（单位元为0），$(\mathbb{N}_0, \times)$ 仍是交换幺半群（单位元为1），但0成为乘法的零元。两种约定各有其历史与实用考量。读者需注意上下文，明确作者所指。本书后续章节在需要时（如讨论整数环）将包含0。

1.2.5 实例：资源分配问题的代数视角

回到数字精灵的困境：将120颗水晶分给8个村落，要求每个村落获得整数颗，且分配方案需体现水晶的“质数质地”（即总水晶数应分解为质数的乘积，以便后续按质数类型进行魔法强化）。

从代数角度看，这是一个整除问题：寻找 $x \in \mathbb{N}$ 使得 $120 = 8 \times x$。由乘法的封闭性，若 $x$ 存在，则 $x = 120 \div 8 = 15$。$15 \in \mathbb{N}$，故初步方案为每村15颗。但精灵要求“体现质数质地”，即 $120$ 的质因数分解必须与分配方案关联。进行分解： $$120 = 12 \times 10 = (2^2 \times 3) \times (2 \times 5) = 2^3 \times 3 \times 5$$ 质因数为2, 3, 5。若要使每个村获得的水晶数本身也是这些质数的乘积（即“质地纯正”），则 $x=15=3 \times 5$ 恰好由质因数3和5构成，满足条件。但若总水晶数为121（$11^2$），分给11村，每村得11（质数），同样满足。若分给5村，$121 \div 5$ 非整数，方案失败。这凸显了整除关系在分配问题中的核心作用。

---

1.3 整除、因数与质数：算术平原的“原子”

要深入理解自然数的内部结构，必须引入整除 (Divisibility) 这一核心概念。它是连接数的大小与内部成分的桥梁。

1.3.1 整除的定义与基本性质

定义 1.2（整除 (Divisibility)） 设 $a, b \in \mathbb{N}$，称 $a$ 整除 $b$（或 $b$ 被 $a$ 整除），记作 $a \mid b$，当且仅当存在 $k \in \mathbb{N}$，使得 $b = a \times k$。此时，$a$ 称为 $b$ 的因数 (Divisor/Factor)，$b$ 称为 $a$ 的倍数 (Multiple)。

例如：

• $3 \mid 12$，因为 $12 = 3 \times 4$，3是12的因数，12是3的倍数。
• $4 \nmid 15$，因为不存在自然数 $k$ 使 $15 = 4 \times k$。

整除关系具有以下基本性质（证明均为直接由定义推出，留作练习）： 1. 自反性：$a \mid a$（取 $k=1$）。 2. 传递性：若 $a \mid b$ 且 $b \mid c$，则 $a \mid c$。 *证明*：$b = a k_1$, $c = b k_2 = a (k_1 k_2)$，且 $k_1 k_2 \in \mathbb{N}$。 3. 若 $a \mid b$ 则 $a \le b$（因 $k \ge 1$）。 4. 1整除一切：$1 \mid a$ 对所有 $a \in \mathbb{N}$ 成立（$a = 1 \times a$）。 5. $a \mid 0$ 对所有 $a \in \mathbb{N}$ 成立（$0 = a \times 0$），但 $0 \mid a$ 无定义（因0不能作除数）。

这些性质构成了整除关系的“语法规则”。

1.3.2 因数与倍数：数的“家族谱系”

给定一个自然数 $n$，其所有因数构成一个集合。例如 $n=12$，其正因数集合为 $\{1, 2, 3, 4, 6, 12\}$。其中，1 和 $n$ 本身称为平凡因数 (Trivial Divisors)，其余称为真因数 (Proper Divisors)。真因数的和若大于 $n$，则 $n$ 为盈数 (Abundant Number)（如12，真因数和 $1+2+3+4+6=16 > 12$）；若小于 $n$，则为亏数 (Deficient Number)；若等于 $n$，则为完美数 (Perfect Number)（如6，真因数和 $1+2+3=6$）。完美数的寻找是数论中的古老谜题，与梅森素数紧密相关。

最大公约数 (Greatest Common Divisor, GCD) 是两数公因数中最大者。对 $a, b \in \mathbb{N}$，记 $\gcd(a, b)$。例如 $\gcd(12, 18) = 6$。若 $\gcd(a, b) = 1$，则称 $a$ 与 $b$ 互质 (Coprime/Relatively Prime)。例如 8 与 15 互质（公因数仅1）。

最小公倍数 (Least Common Multiple, LCM) 是两数公倍数中最小者。记 $\operatorname{lcm}(a, b)$。例如 $\operatorname{lcm}(4, 6) = 12$。

重要关系：对任意 $a, b \in \mathbb{N}$，有 $$\gcd(a, b) \times \operatorname{lcm}(a, b) = a \times b$$ 这个恒等式揭示了公约数与公倍数的对偶性，其证明可利用质因数分解（见下节）。

1.3.3 质数：算术的“原子”

在自然数的因数家族中，有一类成员具有极其特殊的地位——它们只能被1和自身整除，无法再分解为更小的自然数（大于1）的乘积。这就是质数 (Prime Number)。

定义 1.3（质数 (Prime)） 一个大于1的自然数 $p$，如果它的正因数只有1和 $p$ 本身，则称 $p$ 为质数。例如：2, 3, 5, 7, 11, 13, 17, 19, 23, ...。

合数 (Composite Number) 则是大于1的非质数自然数，即至少有一个真因数。例如 4, 6, 8, 9, 10, 12, ...

1 的特殊性：1 只有因数1，按定义它不是质数（质数要求恰好两个不同正因数），也不是合数。它是乘法单位元，在整除中扮演中性角色：$1 \mid a$ 对所有 $a$ 成立，且 $a \mid 1$ 仅当 $a=1$。

质数的重要性：质数在某种意义上扮演了自然数“原子”的角色。算术基本定理断言，任何大于1的自然数，都可以唯一地表达为质数的乘积（不计顺序）。这意味着质数是构建所有自然数的“基本积木”。这一唯一分解性质是数论的基石，也是现代密码学（如RSA公钥加密）的数学基础。

素数的分布：质数在自然数中看似随机，却又遵循某种规律。素数定理 (Prime Number Theorem) 给出了质数计数函数 $\pi(x)$（不超过 $x$ 的质数个数）的渐近估计： $$\pi(x) \sim \frac{x}{\ln x}$$ 这意味着当 $x$ 很大时，不超过 $x$ 的质数个数大约为 $x / \ln x$。例如，$x=10^6$ 时，$\pi(10^6) \approx 72382$，而 $10^6 / \ln(10^6) \approx 72382$，吻合极好。但素数定理的证明需要复分析，属于高等数论。本章仅触及皮毛。

> 侧边栏：寻找质数的算法 > - 试除法 (Trial Division)：检验 $n$ 是否被所有 $\le \sqrt{n}$ 的质数整除。效率低，适用于小 $n$。 > - 埃拉托斯特尼筛法 (Sieve of Eratosthenes)：系统性地标记合数，一次性找出一定范围内的所有质数。其思想是：从2开始，将每个质数的倍数标记为合数。 > ```python > def sieve(n): > is_prime = [True]*(n+1) > is_prime[0] = is_prime[1] = False > for i in range(2, int(n**0.5)+1): > if is_prime[i]: > for j in range(i*i, n+1, i): > is_prime[j] = False > return [i for i, prime in enumerate(is_prime) if prime] > ``` > 该算法时间复杂度约 $O(n \log \log n)$，是生成小范围质数表的高效方法。

1.3.4 算术基本定理：唯一分解的皇冠

定理 1.1（算术基本定理，Fundamental Theorem of Arithmetic, FTA） 任何大于1的自然数 $n$，都可以唯一地表示为质数的乘积（不计因子的顺序）。即： $$n = p_1^{e_1} p_2^{e_2} \cdot