初等数论第一章

整除的概念和带余除法

整除的基本性质

定义 1

• 设 ​a, b \in \mathbb{Z}，且 ​b \neq 0 . 若存在 ​q \in \Bbb{Z}，有 ​a = qb ，则称 ​b 是 ​a 的因数（或约数），或 ​a 是 ​b 的倍数，或 ​b 能整除 ​a，或 ​a 能被 ​b 整除，记作 ​b \mid a .
• 若对任意的 ​q \in \Bbb{Z}，有 ​a \neq qb ，则称 ​a 不能被 ​b 整除，记作 ​b \nmid a .

基本性质

命题1：
设 ​a,0 \neq b \in \Bbb{Z}，则：
(1) ​b \mid 0；
(2) ​1 \mid a；
(3) 当 ​a \neq 0 时，​a \mid a.

结论：

1. ​0 是任何非零整数的倍数.
2. ​1 是任何非零整数的因数.
3. 非零整数 ​a 是它自己的因数.

命题2：
设 ​a,0 \neq b, s \in \Bbb{Z}，则：
(1) 若 ​b \mid a，则 ​b \mid as；
(2) ​b \mid a 当且仅当 ​-b \mid a (即 ​a 的因数总是成对出现)；
(3) 当 ​a \neq 0 时，​a \mid |a| (即 ​a 与 ​|a| 的所有因数相同).

整除的传递性

定理1：
设 ​a, 0 \neq b, 0 \neq c \in \Bbb{Z}，则若 ​b \mid a, c \mid b，则 ​c \mid a.

定理2：
设 ​a, b \in \Bbb{Z} 都是 ​m 的倍数，则 ​a \pm b 是 ​m 的倍数.
​m \mid a, m \mid b \Rightarrow m \mid (a \pm b).

定理3：
设 ​a_1, a_2, \cdots, a_n \in \Bbb{Z} 都是 ​m 的倍数，​q_1, q_2, \cdots, q_n \in \Bbb{Z}，则 ​q_1a_1 + q_2a_2 + \cdots + q_na_n 也是 ​m 的倍数.

整除的进一步性质

命题3：
(1) 若 ​c \mid a, c \nmid b，则 ​c \nmid (a \pm b)；
(2) 若 ​b \mid a, c \neq 0，则 ​bc \mid ac；反之，若 ​bc \mid ac，则 ​b \mid a；
(3) 若 ​b \mid a, c \mid d，则 ​bc \mid ad；
(4) 若 ​a = b + c, d \mid a, d \mid b，则 ​d \mid c.

命题4： (1) 若 ​n 是正整数，​a \neq b，则 ​a - b \mid a^n - b^n；
(2) 若 ​n 是正奇数，​a \neq -b，则 ​a + b \mid a^n + b^n；
(3) 若 ​n 是正偶数，​a \neq -b，则 ​a + b \mid a^n - b^n；

• 对于此命题，有如下公式：​a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + a^{n-3}b^2 + \cdots + ab^{n-2} + b^{n-1}).

命题5： (1) 若 ​c \mid ab，且 ​(b, c) = 1，则 ​c \mid a；
(2) 若 ​b \mid a, c \mid a，且 ​(b, c) = 1，则 ​bc \mid a；
(3) 若 ​b \mid a, c \mid a，则 ​[b, c] \mid a.

1. 对于此命题中，​(b, c) = 1，可以理解为 ​b 和 ​c 的最大公因数为 ​1，即 ​gcd(b, c) = 1.
2. 对于此命题中，​[b, c] \mid a，可以理解为 ​b 和 ​c 的最小公倍数是 ​a 的因数，即 ​lcm(b, c) \mid a.

⭐定理4：
设 ​a, b \in \Bbb{Z} 且 ​b > 0，则存在唯一的两个整数 ​q 和 ​r，使得 ​a = bq + r，其中 ​0 \leq r < b.(带余除法)

推论1：
设 ​a, b \in \Bbb{Z} 且 ​b \neq 0，则存在唯一一对整数 ​q 和 ​r，使得 ​a = bq + r，其中 ​0 \leq r < |b|.

定义 2

• 在定理 ​4 中，​q 叫做 ​a 被 ​b 除的不完全商，​r 叫做 ​a 被 ​b 除的余数.

最大公因数和辗转相除法

最大公因数的基本性质

定义 1

• 设 ​a_1, a_2, \cdots, a_n 是 ​n (n \geq 2) 个整数，如果整数 ​d 是它们中每一个的因数，则称 ​d 为 ​a_1, a_2, \cdots, a_n 的公因数。
• 整数 ​a_1, a_2, \cdots, a_n 的公因数中最大的一个称为它们的最大公因数，记作 ​gcd(a_1, a_2, \cdots, a_n)，或 ​(a_1, a_2, \cdots, a_n)。
• 如果 ​(a_1, a_2, \cdots, a_n) = 1，则称 ​a_1, a_2, \cdots, a_n 互质或互素。如果 ​a_1, a_2, \cdots, a_n 中任意两个整数互质，则称它们两两互质。

命题1：
(1) ​a_1, a_2, \cdots, a_n \in \Bbb{Z} 的公因数必定存在.
(2) 若 ​a_1, a_2, \cdots, a_n 不全为零，则 ​(a_1, a_2, \cdots, a_n) 必定存在.
(3) 当 ​a_1, a_2, \cdots, a_n 不全为零时，​(a_1, a_2, \cdots, a_n) > 0.

由最大公因数的定义，我们可以得到证明最大公因数的一个方法：

设 ​a_1, a_2, \cdots, a_n 为 ​n 个不全为零的整数，则 ​(a_1, a_2, \cdots, a_n) = d 当且仅当

1. ​d \mid a_i (i = 1, 2, \cdots, n);
2. 若 ​d' \mid a_i (i = 1, 2, \cdots, n)，则 ​d' \mid d.

命题2：
若 ​b \mid a 且 ​a > 0，则 ​b \leq a.
​~~~~~~~~~~\Downarrow
推论1：
若 ​b \mid a 且 ​a > 0，则 ​|b| \leq |a|.
定理1：
设 ​a_1, a_2, \cdots, a_n 为 ​n 个不全为零的整数，则
(1) ​a_1, a_2, \cdots, a_n 与 ​|a_1|, |a_2|, \cdots, |a_n| 的公因数相同；
(2) ​(a_1, a_2, \cdots, a_n) = (|a_1|, |a_2|, \cdots, |a_n|)。

定理2：
若 ​0 < b \in \Bbb{Z}，则：
(1) ​0 与 ​b 的公因数就是 ​b 的因数，反之，​b 的因数也是 ​0 与 ​b 的公因数；
(2) ​(0, b) = b；
(3) ​(a, 0) = |a| (0 \neq a \in \Bbb{Z})。

辗转相除法

⭐定理3：（辗转相除法的理论依据）
设 ​a, b, c 是三个不全为零的整数，且 ​a = bq + c (q \neq 0)，则 ​a, b 与 ​b, c 有相同的公因数，从而有 ​(a, b) = (b, c)。

辗转相除法的推导

设 ​a, b \in \Bbb{Z_+}，由带余除法：

即：

如果其中的某一项 ​r_i 为零，则最大公因数就是 ​r_{i-1}。

定理4：
若 ​a, b \in \Bbb{Z}，则 ​(a, b) = r_n。

推论2：
​a, b 的公因数与它们的最大公因数 ​(a, b) 具有相同的因数。

辗转相除法的代码实现

使用函数递归或迭代实现辗转相除法进行两个数最大公因数的求解。

递归形式

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

迭代形式

int gcd(int a, int b) {
    while(b){
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}
// 上下两个代码原理相同，只是写法不同
int gcd_1(int a, int b) {
   while(b ^= a ^= b ^= a %= b);
   return a;
}

递归形式

def gcd(a, b) -> int:
    return a if b == 0 else gcd(b, a % b)

迭代形式

def gcd(a, b) -> int:
    while b:
        a, b = b, a % b
    return a

最大公因数相关性质

定理5：
设 ​a, b 是任意两个不全为零的整数，则
(1) 若 ​m \in \Bbb{Z_+}，则 ​(ma, mb) = m(a, b)；
(2) 若 ​\delta 是 ​a, b 的一个公因数，则 ​(\frac{a}{\delta}, \frac{b}{\delta}) = \frac{(a, b)}{|\delta|}。

对于上述定理 ​5，有一种特殊情况：​(\frac{a}{(a, b)}, \frac{b}{(a, b)}) = 1。

同时，可以推出： ​(a, b) = d 当且仅当存在唯一的一对互质的整数 ​a_1, b_1 使得 ​a = da_1, b = db_1.

多个数的最大公因数计算

设 ​a_1, a_2, \cdots, a_n 是不全为零的整数（可以假定它们都是正整数），且：

则 ​(a_1, a_2, \cdots, a_n) = d_n。

可以发现，上述式子其实与辗转相除法的计算式有着相似的形式。

整除的进一步性质与最小公倍数

辗转相除法得到的递推公式

若 ​a, b \in \Bbb{Z_+}，则

其中

裴蜀定理

若 ​(a, b) = d，则存在 ​s, t \in \Bbb{Z}，有 ​as + bt = d。

推导过程如下：

由辗转相除法的递推公式，有：​Q_n a - P_n b = (-1)^{n-1} r_n。

对于 ​a, b \in \Bbb{Z_-} 我们可以等价转换为：​(|a|, |b|)。

于是可得：

即：​(a, b) = r_n。

将上述递推公式同时乘以 ​(-1)^{n-1} 可得：

于是我们可取 ​s = (-1)^{n-1} Q_n, t = (-1)^{n}P_n。

则 ​d = r_n = as + bt，得证。

⭐推论1：
若 ​(a, b) = d，则存在 ​s, t \in \Bbb{Z}，有 ​as + bt = d。

考虑推论 ​1 的逆命题在何时成立。

命题1：
设 ​a, b, d \in \Bbb{Z}, d > 0，若存在 ​s, t \in \Bbb{Z}，有 ​as + bt = d，且 ​d 是 ​a, b 的公因数，则 ​(a, b) = d。

根据命题 ​1 我们可以推出如下结论（推论 ​2）：

⭐设 ​a, b \in \Bbb{Z}，则 ​(a, b) = 1 当且仅当存在 ​s, t \in \Bbb{Z}，有 ​as + bt = 1。

定理2：
设 ​a, b, c \in \Bbb{Z} 且 ​(a, c) = 1，则
(1) ​a 与 ​b, c 有相同的公因数；
(2) ​(ab, c) = (b, c)。
这里 ​b, c 中至少有一个不为零。