整除理论

SpeedStar · 2025-01-13 19:44:31 · 个人记录

整除

素材1

（一）整除：设 a, b 为整数，并且 b \neq 0，若存在整数 c，使得 a = bc，则称 b 整除 a，记为 b | a，并称 b 是 a 的一个约数（或者因子），a 是 b 的倍数。如果不存在上述的整数 c，则称 b 不整除 a，记为 b \nmid a。

一些常见的整除性质：

(1) 若 b | c 且 c|a，则 b|a。

(2) 若 b|a 且 b|c，则有 b|(a \pm c)。

(3) 若 b|a，则或者 a = 0，或者 |a| \geqslant |b|；从而若 a|b 且 b|a，则 |a| = |b|。（\color{red}{\text{重点}}）

(4) (带余除法)：设 a, b 是整数且 b > 0，则若存在唯一整数对 q, r，使 a = bq+r(0 \leqslant r \lt b) 成立。

(5) 若 p 为质数且 p|ab，则 p|a 或者 p|b。

证明：若 p \nmid a，则 (p, a) = 1，根据性质(7)可得 p|b

这条性质可以推出算术基本定理的唯一性

(6) 若 p 为质数且 p | a^m，则 p|a。

(7) 设 b|ac，若 b, c 互质，则 b|a。

需要用裴蜀定理来证

设 ub+vc = 1，\Rightarrow \ uab + vac = a，\Rightarrow b \mid a

(8) 若 b_1, b_2, \cdots, b_n 是两两互质的正整数，并且 b_i \mid a(i = 1, 2, \cdots, m)，则 b_1b_2 \cdots b_n \mid a 。

(9) n 个连续整数乘积能被 n! 整除。

是个整数

(二) 最大公约数与最小公倍数

最大公约数：设 a_1, a_2, \cdots, a_n 是不全为 0 的整数，能同时除尽它们的整数叫做它们的公约数，其中必有一个最大的，称为它们的最大公约数，记为 (a_1, a_2, \cdots, a_n)。

最小公倍数：设 a_1, a_2, \cdots, a_n 是不全为 0 的整数，能同时被它们除尽的整数叫做它们的公倍数，其中必有一个最小的正数，称为它们的最小公倍数，记为 [a_1, a_2, \cdots, a_n]。

最大公约数与最小公倍数的一些常见性质：

(1) (a, b) = b \ \Leftrightarrow \ b \mid a \ \Leftrightarrow \ [a, b] = a

(2) 对任意整数 q，有 (a, b) = (a+bq, b) （\color{red}{\text{重点}}）

(3) 若 m 为 a, b 的公约数，则有 m \mid (a, b)；若 m 为 a, b 的公倍数，则有 [a, b] \mid m

(4) 设 a, b 均与 m 互质，则 ab 也与 m 互质

(5) 设 (a, b) = d，则 (\dfrac{a}{d}, \dfrac{b}{d}) = 1

注：这条性质在莫反题里常用

(6) 设 m 为整数，则 (ma, mb) = m(a, b)，[ma, mb] = m[a, b]

(7) (a, b)[a, b] = |ab|。特别地，若 (a, b) = 1，则 [a, b] = |ab| （\color{red}{\text{重点}}）

上面 7 条性质都可以由算术基本定理得证

（三）欧几里得算法与裴蜀定理

欧几里得（Euclid）算法（又称为辗转相除法）：设 a, b 为整数且 b > 0，按照下述方式做带余除法，有限步之后必然停止（即余数为 0）：

用 b 除 a：a = bq_0 + r_0，0 < r_0 < b

用 r_0 除 b：b = r_0q_1 + r_1，0 < r_1 < r_0

用 r_1 除 r_0：r_0 = r_1q_2 + r_2，0 < r_2 < r_1

用 r_{n-1} 除 r_{n-2}：r_{n-2} = r_{n-1}q_n + r_n，0 < r_n < r_{n-1}

用 r_n 除 r_{n-1}：r_{n-1} = r_nq_{n+1}

则 (a, b) = (bq_0+r_0, b) = (b, r_0) = (r_0, r_1) = \cdots = (r_{n-1}, r_n) = (r_nq_{n+1}, r_n) = r_n

裴蜀（Bezout）定理：设 a, b, d 是整数，则 (a, b) = d \Leftrightarrow d \mid a, d \mid b 且存在整数 u, v，使得 ua+vb = d 成立，这可以由欧几里得算法倒推得到。（\color{red}{\text{重点}}）

还有另一种证法：

设 d = \min\{ua+vb\}，且 u, v \in \mathbb{Z}, ua+vb > 0

设 d = ua+vb 最小，则显然 (a, b) \mid d

若 d \nmid a，设 a = qd+r，0 < r < d，那么 0 < r = a-qd = a - q(ua+vb) = u'a + v'b < d，与 d 最小矛盾。所以 d \mid a。同理 d \mid b。所以 d \mid (a, b)

所以 d = (a, b)

裴蜀定理的几个推论：

（1）(a, b) = 1 的充要条件是存在整数 u, v，使得 ua + vb = 1 成立

（2）a, b 均为正整数，(a, b) = 1 的充要条件是存在正整数 u, v，使得 ua - vb = 1

（3）当 (a, b) = 1，ua+vb 可以表示所有整数

（4）对于任意的正整数 a_1, a_2, \cdots, a_n，存在整数 k_1, k_2, \cdots, k_n，使得：k_1a_1 + k_2a_2 + \cdots + k_na_n = (a_1, a_2, \cdots, a_n) 成立

例题1.

求满足下列性质的最小的正整数 n：对于任意的 n 个整数 a_1, \cdots, a_n，一定存在不同的 a_i, a_j，使得 2017 \mid a_i +a_j 或 2017 \mid a_i-a_j .

分析：

可以从余数的角度去考虑

考虑 a_1, \cdots, a_n 被 2017 除的余数

若 n 不满足要求，则这些余数各不相同且 \{0\}, \{1, 2016\}, \cdots, \{2, 2015\}, \{1008, 1009\} 每个集合中至多有一个余数，所以至多 1009 个数

所以，若 n \geqslant 1010，则有矛盾，从而 n 满足要求

取 0, 1, \cdots, 1008，则这 1009 个数不满足要求

所以，n 最小为 1010 .

例题2. 2007CMO

设 2n-1 是素数，对于任意 n 个互不相同的正整数 a_1, \cdots, a_n，都存在 i, j \in \{1, 2, \cdots, n\}，使得 \dfrac{a_i + a_j}{(a_i, a_j)} \geqslant 2n-1 .

分析：

设 2n-1 = p，不妨设 (a_1, \cdots, a_n) = 1（否则设 d = (a_1, \cdots, a_n)，考虑 \dfrac{a_1}{d}, \cdots, \dfrac{a_n}{d})

Case 1: 若存在 i 使 p \mid a_i，看 \dfrac{a_i}{(a_i, a_j)}

则存在 j 使 p \nmid a_j，则 p \nmid (a_i, a_j) \Rightarrow \ p \Big| \dfrac{a_i}{(a_i, a_j)} \Rightarrow \dfrac{a_i}{(a_i, a_j)} \geqslant p

下设 p \nmid a_i, \ \forall \ i

Case 2: 若有 a_i, a_j 模 p 余数相同且不为 0，则 p \mid a_i - a_j

又 p \nmid (a_i, a_j) \ \Rightarrow \ p \Big| \dfrac{a_i - a_j}{(a_i, a_j)} \Rightarrow \ \dfrac{a_i + a_j}{(a_i, a_j)} > \dfrac{a_i - a_j}{(a_i, a_j)} \geqslant p

Case 3: 若 a_1, \cdots, a_n 模 p 互不同余且不余 0，由抽屉原理，\exist \ i \neq j 使 p \mid a_i+a_j，另外显然 p \nmid (a_i, a_j)，\Rightarrow \ p {\Bigg|} \dfrac{a_i+a_j}{(a_i, a_j)} \ \Rightarrow \dfrac{a_i+a_j}{(a_i, a_j)} \geqslant p

例题3. 2012IMC

是否有无穷多个 n，使得 n!+1 \mid (2012n)! .

分析：

只证明：(\frac{n}{e})^n < n! < e(\frac{n}{2})^n

对于右边的不等式：

由 e > (1+\frac{1}{n})^n

只需证 (1+\frac{1}{n})^n \cdot (\frac{n}{2})^n > n! \Leftrightarrow (\frac{n+1}{2})^n > n!

由均值不等式，n! = 1 \cdot 2 \cdots n < (\frac{1+2+\cdots + n}{n})^n = (\frac{n+1}{2})^n 即得

对于左边的不等式：

归纳，

假设对 n 成立，即 e^n > \frac{n^n}{n!}，要证 e^{n+1} > \frac{(n+1)^{n+1}}{(n+1)!}

只需证 e > \frac{(n+1)^{n+1}}{n^n} \cdot \frac{1}{n+1} \Leftrightarrow e > (1+\frac{1}{n}) 成立 .

回到原题

又 n!+1 \mid (2012n)!，((n!)^{2012}, n!+1) = 1

左边 > (n!)^{2013} > (\frac{n}{e})^{2013n}

右边 = (2012n)! < (2012n)^{2012n}

所以只有有限多个 n 满足条件 .

例题4