初等数论 第一章 整除

学习目标：理解整除、素数、最大公因数、欧几里得算法与不定方程的基础概念。

一、整除的概念

我们暂时忘掉小数点，只考虑整数除法：

$$a \div b = q \dots r \Longleftrightarrow a = bq + r$$

整除讨论的核心，就是 “余数为 0 的除法”。

定义

$$\exists q \in \mathbb{Z},\ a = bq \Longleftrightarrow b \mid a$$

默认 $b \neq 0$。若不成立，则记为 $b \nmid a$。

性质

• 正负无影响：
  $b \mid a \Rightarrow (-b) \mid a, \ b \mid (-a), \ (-b) \mid (-a)$

• 传递性：
  $c \mid b, \ b \mid a \Rightarrow c \mid a$

• 线性可加性：
  $c \mid a, \ c \mid b \Rightarrow c \mid (sa \pm tb), \ \forall s,t \in \mathbb{Z}$

• 互整性：
  $a \mid b, \ b \mid a \Rightarrow a = \pm b$

二、素数

定义

$$p \in \mathbb{Z},\ p \neq 0, \pm 1,\ 且\ 仅有\ \pm1, \pm p\ 为因子 \Longrightarrow p\ 是\ 素数$$

即素数只有“平凡因子”。

性质与分布

• 若 $p$ 是素数，则 $-p$ 也是素数。
• 素数越往远处越稀疏。

定义 $\pi(x)$ 为区间 $[0, x]$ 内素数的个数。
有著名的 素数定理：

$$\lim_{x \to \infty} \frac{\pi(x)}{x / \ln x} = 1$$

由此可知：素数有无穷多个。

三、欧几里得除法（带余除法）

任意整数 $a,b$（$b > 0$）可以唯一表示为：

$$a = bq + r, \quad 0 \le r < b$$

其中：

• $q$ 称为 不完全商（商）
• $r$ 称为 余数

变形（偏移形式）

$$a = bq + r, \quad c \le r < b + c$$

等价于：

$$qb + c \le a < (q + 1)b + c$$

当 $c = 0$ 时，即为标准形式，得到最小非负余数。

另有“绝对值最小余数”版本（见课件）。

四、最大公因数（GCD）

符号表示：

• 程序设计：gcd(a, b)
• 数论中：$(a, b)$

基本性质

1. 若 $a$ 不是 $p$ 的倍数，则 $(a, p) = 1$，即 $a,p$ 互素；
2. 绝对值不影响结果：$(a_i) = (|a_i|)$；
3. $(0, b) = |b|$；
4. 若 $a = bq + c$，则

   $$(a,b) = (b,c)$$

五、辗转相除法与扩展算法（exgcd）

辗转相除法用于快速求 $(a,b)$。

扩展欧几里得算法（exgcd）还能求出整数 $s,t$，使：

$$sa + tb = (a,b)$$

这就是 贝祖等式（Bézout’s identity）。

推论

• $(a,b)=1 \iff \exists s,t\in\mathbb{Z},\ sa+tb=1$
• $(a,b)=d \iff \begin{cases} d\mid a,\, d\mid b, \\ \forall e\mid a,b \Rightarrow e\mid d \end{cases}$
• 对于任意 $m>0$：

  $$(am,bm) = m(a,b)$$

例题性质

可证：

$$(a,b)=1 \iff (2^a-1,\,2^b-1)=1$$

（证明见课件第 39 页）

六、算术基本定理

又称 唯一分解定理。

$$\forall n>1,\, n = p_1^{k_1}p_2^{k_2}\cdots p_s^{k_s}$$

每个正整数可唯一分解为素数的乘积（顺序除外）。

若

$$a = \prod p_i^{k_i}, \quad b = \prod p_i^{m_i},$$

则：

$$(a,b) = \prod p_i^{\min(k_i,m_i)}, \quad [a,b] = \prod p_i^{\max(k_i,m_i)}$$

其中 $[a,b]$ 表示最小公倍数。

七、不定方程

考虑一次不定方程：

$$ax + by = c, \quad a,b \in \mathbb{Z}^+$$

解的存在性

$$\text{方程有解} \iff (a,b) \mid c$$

若 $(a,b) = d$，则通解为：

$$\begin{cases} x = x_0 + \dfrac{b}{d}t, \\ y = y_0 - \dfrac{a}{d}t, \end{cases} \quad t \in \mathbb{Z}$$

其中 $(x_0, y_0)$ 是一组特解，可由 exgcd 求出。