第1章 整除与同余
整除与同余是数论中*基本的概念， 本章将介绍整除的性质， 包括带余除法定理、裴蜀 (Bézout) 定理及 p 进制表示; 介绍同余的性质及其应用， 包括欧拉(Euler) 定理、费马 (Fermat) 小定理、中国剩余定理. 这些都是数论中*基本的性质与定理.
1.1 整除
整除是数论中*基本的概念， 本节将介绍整除的概念及相关内容.
定义 1.1.1 设 a， b 为整数， a .= 0， 若存在整数 k， 使得 b = ak， 则称 b 能被a 整除， 或 a 能整除 b， 记为 a | b. 若这样的 k 不存在， 则称 b 不能被 a 整除， 或a 不能整除 b， 记为 a . b. 若 a | b， 则称 a 为 b 的因数， b 为 a 的倍数.
基本性质
(1) 若 a | b， b | c， 则 a | c.
(2) 若 m | a1， ，m | an， k1， ， kn 为整数， 则
定理 1.1.1(带余除法定理) 设 a， b 为整数， a .= 0， 则存在唯一的整数对 q， r，
使得
我们称 r 为 b 被 a 除所得的余数.
证明 存在性. 不妨设 a > 0. 设 q 是使得 aq . b 成立的*大的整数， 则，即.令 r = b-aq， 我们有
唯一性. 设
则 aq1 + r1 = aq2 + r2， 即
(1.1.1)
假设 q1 .= q2， 则 |a(q1.q2)| . |a|. 又 0 . r1， r2 < |a|， 故 |r2.r1| < |a|， 与 (1.1.1) 矛盾. 因此， q1 = q2. 再由 (1.1.1) 知 r1 = r2.
定理 1.1.1 得证.
例 1 证明: 对任何整数 n， 总有 5 | n5-n.
证明 对于整数 n， 由带余除法定理知， 存在整数 q， r， 使得. 由于
其中 K 为一个整数， 故只要验证: 当 r = 0， 1， 2， 3， 4 时， 5 | r5-r. 经过验证， 这确实成立. 所以， 5 | n5-n.
定义 1.1.2 设 a1， ， an 为不全为 0 的整数， 若 d | a1， ， d | an， 则称 d 为 a1， ， an 的一个公约 (因) 数. a1， ， an 的公约数中*大的一个称为 a1， ， an 的*大公约 (因) 数， 记为 (a1， ， an).
若 (a1， ， an) = 1， 则称 a1， ， an 互素. 特别地， 若 (a， b) = 1， 则称整数 a 与 b 互素.
定理 1.1.2 设 a， b 为不全为零的整数， 则对任何整数 k， 总有
(a， b) = (a-bk， b).
证明 令 d1 = (a， b)， d2 = (a-bk， b). 由整除的性质及*大公约数的定义知
因此， d1 = d2， 即 (a， b) = (a-bk， b).
定理 1.1.2 得证.
辗转相除法 设 a， b 为正整数， a > b， 由带余除法定理知
由于 b > r1 > r2 > 及不超过 b 的正整数只有 b 个， 故上述过程一定会终止.
由定理 1.1.2 知
即辗转相除法的*后一个非零余数就是 a， b 的*大公约数.
由辗转相除法的关系式可得
特别地， (a， b) = aun + bvn. 由此很容易得到如下定理.
定理 1.1.3 (裴蜀定理) 对于任给的不全为零的整数 a， b， 总存在整数 u， v， 使得
au + bv = (a， b).
证明 若 a， b 中有一个为零， 不妨设 b = 0， 则取 u ∈ {.1， 1}， 使得 au = |a|.
这样， 对任何整数 v， 有
au + bv = |a| = (a， 0) = (a， b).
下设 a， b 均不为零. 由辗转相除法知， 存在整数 s， t， 使得 |a|s + |b|t = (|a|， |b|).
由*大公约数的定义知， (|a|， |b|) = (a， b). 取 u ∈ {.s， s}， v ∈ {.t， t}， 使得 |a|s = au， |b|t = bv. 这样， au + bv = (a， b).
裴蜀定理得证.
例 2 求 1491 与 3619 的*大公约数， 并求整数 u， v， 使得
1491u + 3619v = (1491， 3619).
解 首先对 1491 与 3619 进行辗转相除法:
3619 = 1491 × 2 + 637， 1491 = 637 × 2 + 217， 637 = 217 × 2 + 203，
217 = 203 × 1 + 14， 203 = 14 × 14 + 7， 14 = 7 × 2.
因此， (1491， 3619) = 7，
所以， 可取 u = -250， v = 103.
附注 例 2 中的 u， v 不唯一.
一般地， 有如下定理.
定理 1.1.4 对于任给的不全为零的整数 a1， ， an， 总存在整数 u1， ， un， 使得
证明 由于 a1a1 + + anan > 0， 故存在形如的正整数， 设是这样的正整数中*小的一个， 下证是 a1， ， an 的*大公约数， 即
令 d = a1u1 + + anun. 根据*大公约数的定义， 需要证明如下两点.
第一点: d 是 a1， ， an 的公约数.
第二点: a1， ， an 的公约数均不超过 d.
首先证明: d 为 a1， ， an 的公约数. 对每个 i， 由带余除法定理知. 由此知
简单整理后知， ri 也具有形式
又， 故由 d 的定义知， ri = 0， 即 d | ai. 这就证明了: d 为 a1， ， an 的公约数.
其次， 设 d′ 为 a1， ， an 的一个公约数， 则 d′ 为 a1u1 + + anun 的因数.
又 a1u1 + + anun > 0， 故
综上， d 为 a1， ， an 的*大公约数. 所以
定理 1.1.4 得证.
定理 1.1.3 的证明是构造性的证明， 给定 a， b 后， 由辗转相除法可得到 u， v. 定理 1.1.4 的证明是存在性的证明， 给定 a1， ， an， 不能利用证明得到 u1， ， un.
定理 1.1.5 对于任给的正整数 k 及不全为零的整数 a1， ， an， 总有
证明 只要证明: k(a1， ， an) 是 ka1， ， kan 的*大公约数.
根据*大公约数的定义， 只要证明如下两点.
(1) k(a1， ， an) 为 ka1， ， kan 的一个公约数.
(2) ka1， ， kan 的公约数均不超过 k(a1， ， an).
由于
故
即 k(a1， ， an) 为 ka1， ， kan 的一个公约数.
现设 d 为 ka1， ， kan 的一个公约数. 试图证明: d . k(a1， ， an).
由定理 1.1.4 知， 存在整数 u1， ， un， 使得
由此得
由于 d | kai (1 . i . n)， 故
即 d | k(a1， ， an). 从而 d . k(a1， ， an).
综上， k(a1， ， an) 为 ka1， ， kan 的*大公约数， 即
定理 1.1.5 得证.
定理 1.1.6 设 a1， ， an 是不全为零的整数， 则 d | a1， ， d | an 的充要条件是 d | (a1， ， an).
证明 充分性. 设
由于
故
必要性. 设. 由定理 1.1.4 知， 存在整数 u1， ， un， 使得
由知
即 d | (a1， ， an).
定理 1.1.6 得证.
定理 1.1.7 若 (a， b) = 1， 则 (a， bc) = (a， c).
证明 由 (a， c) | a， (a， c) | c 知
根据*大公约数的定义得 (a， c) . (a， bc). 由定理 1.1.3 知， 存在整数 u， v， 使得au + bv = (a， b) = 1. 由此得 acu + bcv = c. 因此， (a， bc) | c. 又 (a， bc) | a， 故根据*大公约数的定义得 (a， bc) . (a， c). 综上， (a， bc) = (a， c).
定理 1.1.7 得证.
定理 1.1.8 若 a | bc， (a， b) = 1， 则 a | c.
证明 由条件及定理 1.1.7 知， (a， c) = (a， bc) = |a|. 因此， |a| | c， 即 a | c.
定理 1.1.8 得证.
定理 1.1.9 若， 则 (a， b1 bn) = 1.
证明 反复利用定理 1.1.7 得
定理 1.1.9 得证.
下面介绍 p 进制， 通常我们用十进制表示数， 如 125 表示 102 + 2 10 + 5， 计算机使用的是二进制.
展开
