第一章 整除

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

一、整除的概念

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

$$a÷b=q\dots r⟺a=bq+r$$

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

定义

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

默认 $b\ne 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\ne 0,\pm 1,且仅有\pm 1,\pm p为因子⟹p是素数$$

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

性质与分布

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

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

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

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

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

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

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

其中：

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

变形（偏移形式）

$$a=bq+r,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⟺\exists s,t\in \mathbb{Z},sa+tb=1$
• $(a,b)=d⟺\{\begin{array}{l}d\mid a,d\mid b,\\ \forall e\mid a,b\Rightarrow e\mid d\end{array}$
• 对于任意 $m>0$： $$(am,bm)=m(a,b)$$

例题性质

可证：

$$(a,b)=1⟺(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},b=\prod p_i^{m_i},$$

则：

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

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

七、不定方程

考虑一次不定方程：

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

解的存在性

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

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

$$\{\begin{array}{l}x=x_0+\frac{b}{d}t,\\ y=y_0-\frac{a}{d}t,\end{array}t\in \mathbb{Z}$$

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