整除理论
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! 整除。
C(m, n) = \frac{m(m-1) \cdots (m-n+1)}{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
\cdots\cdots
用 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)! .
分析：
大小 \begin{cases}1. \ 增长快,\ \frac{n!}{n^k} \to \infty\\ 2. \ (\frac{n}{e})^n < n! < e(\frac{n}{2})^n\\ 3. \ 斯特林公式 \ n! \sim \sqrt{2\pi n}(\frac{n}{e})^n\end{cases}\\ 递推（归纳）
\end{cases}
只证明：(\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! \mid (2012n)!$，$(n!, n!+1)=1
\Rightarrow \ n!(n!+1) \mid (2012n)! \Rightarrow n!(n!+1) \leqslant (2012n)!
所以 $(n!)^{2012} \mid (2012n)!
又 n!+1 \mid (2012n)!，((n!)^{2012}, n!+1) = 1
\Rightarrow \ (n!)^{2012} \cdot (n!+1) \mid (2012n)!
\Rightarrow \ (n!)^{2012}(n!+1) \leqslant (2012n)!
左边 > (n!)^{2013} > (\frac{n}{e})^{2013n}
右边 = (2012n)! < (2012n)^{2012n}
\Rightarrow (\frac{n}{e})^{2013n} < (2012n)^{2012n}
\Rightarrow n < 2012^{2012} e^{2013}
所以只有有限多个 n 满足条件 .
例题4