整除进阶

· · 算法·理论

前言

这是我和盟友两位五年级蒟蒻合作的数论合集第五篇文章，大佬们不喜勿喷，感谢您的收看。

定义与性质

定义

对于非零整数 a 和整数 b，若存在整数 q，使得 b = aq，则称 a \mid b，读作 a 整除 b。

性质

传递性

若 a \mid b，b \mid c，则 a \mid c。 ::::success[证明]{open}

\because a \mid b, b \mid c \therefore \exists p, q \in \Z, b = ap, c = bq \therefore c = bq = apq = a(pq), pq \in \Z \therefore a \mid c

::::

可加减性

若 a \mid b，a \mid c，则 a \mid b \pm c。 ::::success[证明]{open}

\because a \mid b, a \mid c \therefore \exists p, q \in \Z, b = ap, c = aq \therefore p \pm c = ap \pm aq = a(p \pm q), p \pm q \in \Z \therefore a \mid b \pm c

::::

可乘性

若 a \mid b，c \mid d，则 ac \mid bd。 ::::success[证明]{open}

\because a \mid b, c \mid d \therefore \exists p, q \in \Z, b = ap, d = cq \therefore bd = (ac)(pq), pq \in \Z \therefore ac \mid bd

::::

线性性质

这里的线性不是线性 DP 求最长上升子序列

若 a \mid b，a \mid c，则 \forall x, y \in \Z, a \mid bx \pm cy。 ::::success[证明]{open}

\because a \mid b, 1 \mid x \therefore a \mid bx

同理

a \mid cy \therefore a \mid bx + cy

::::

可消性

若 ma \mid mb，则 a \mid b。 ::::success[证明]{open}

\because ma \mid mb \therefore \exists p \in \Z, mb = map b = ap \therefore a \mid b

::::

性质 6

连续 n 个数中有且仅有一个数被 n 整除。 ::::success[证明]{open} 设 n 个数为

a - n + 1, a - n + 2, \cdots, a

令

q = \left[\frac{a}{n}\right] \therefore q \le \frac{a}{n} < q + 1 \therefore a - n < nq \le a \therefore a - n + 1 \le nq \le a \therefore nq \in \{a - n + 1, a - n + 2, \cdots, a\}

又

1 \mid q, n \mid n \therefore n \mid nq

若 \exists -n < i < j < 0, n \mid (a + i), (a + j)

\therefore a \mid j - i j - i > n

矛盾，\therefore 连续 n 个数中有且仅有一个数被 n 整除。 ::::

性质 7

::::success[证明]{open} 设 $n$ 个数为 $$ a, a + 1, \cdots, a + n - 1 $$ --- 若 $0 < a \therefore n! \times C_{a + n - 1}^{n} = a(a + 1) \cdots (a + n - 1)

而 C_{a + n - 1}^{n} \in \Z

\therefore n! \mid a(a + 1) \cdots (a + n - 1)

若 a \le 0 \le a + n - 1

\therefore n! \mid a(a + 1) \cdots (a + n - 1) = 0

若 a + n - 1 < 0
令 b = -(a + n - 1)

\therefore b(b + 1) \cdots (b + n - 1) = (-1)^n \cdot a(a + 1) \cdots (a + n - 1) \therefore n \mid b(b + 1) \cdots (b + n - 1), 1 \mid (-1)^n \therefore n \mid a(a + 1) \cdots (a + n - 1)

::::

例题

例题一

::::info[题目]{open} 求证： 3 \mid x, 7 \mid x \Rightarrow 21 \mid x :::: 首先，通过可乘性，又 21 \mid 7x, 3x，再用线性性质，就有 21 \mid 7x - 2 \times 3x = x。 ::::success[完整解答]{open}

\because 3 \mid x, 7 \mid 7 \therefore 21 \mid 7x \because 7 \mid x, 3 \mid 3 \therefore 21 \mid 3x \therefore 21 \mid 7x - 2 \times 3x = x

::::

例题二

::::info[题目]{open} 已知 27 \mid \overline{abc}，求证 27 \mid \overline{bca}，27 \mid \overline{cab} :::: 其实题目只有两个未知数，a 和 \overline{bc}，通过可乘性得到 27 \mid 1000a + 10 \times \overline{bc} 和 27 \mid 999a，相减即可。 ::::success[完整解答]{open}

\because 27 \mid \overline{abc}, 1 \mid 10 27 \mid 1000a + 10 \times \overline{bc} \because 27 \mid 999, 1 \mid a \therefore 27 \mid 999a \therefore 27 \mid 1000a + 10 \times \overline{bc} - 999a = \overline{bca}

同理

27 \mid \overline{cab}

::::

例题三

::::info[题目]{open} 设 a, b, c, d \in \N，且满足 ad - bc > 1，求证：a, b, c, d 中至少有一个数不能被 ad - bc 整除。 :::: 考虑反证，假设全部能被 ad - bc 整除，能够推出 (ad - bc)^2 \mid (ad - bc)，通过可消性得到 ad - bc \mid 1，即 ad - bc \le 1，矛盾。 ::::success[完整解答]{open} 若 ad - bc \mid a, b, c, d

\therefore (ad - bc)^2 \mid ad, bc \therefore (ad - bc)^2 \mid (ad - bc)

又

ad - bc \ne 0 \therefore ad - bc \mid 1 \therefore ad - bc \le 1

矛盾

\therefore a, b, c, d \text{ 中至少有一个数不能被 } ad - bc \text{ 整除。}

::::

因式分解与整除

例题一

::::info[题目]{open} 求证：8 \mid 3^{2n+1} + 5, n \in \N。 :::: 发现 3^{2n+1} 和 5 关系不大，通过性质只需证 8 \mid 3^{2n+1} - 3，因式分解即可。 ::::success[完整解答]{open}

3^{2n+1} - 3 = 3(3^{2n} - 1) = 3(9^n - 1) = 3 \times (9 - 1) \times (9^{n-1} + 9^{n-2} + \cdots + 1) \because 8 \mid 9 - 1 = 8, 1 \mid 3 \times (9^{n-1} + 9^{n-2} + \cdots + 1) \therefore 8 \mid 3 \times (9 - 1) \times (9^{n-1} + 9^{n-2} + \cdots + 1) = 3^{2n+1} - 3 \because 8 \mid 8 \therefore 8 \mid 3^{2n+1} - 3 + 8 = 3^{2n+1} + 5

::::

例题二

::::info[题目]{open} 求证：对于所有正整数 n：

$(2)$ 若 $2^n + 1$ 为质数，则 $n = 2^k$。 :::: ::::info[Hint] - 高次方差（奇数次方和）是个好东西。 - 如何分解 $2^6 - 1$。 - 证明一个数是 $2^k$ 时，可设一个数为 $2^k \cdot l$，其中 $l$ 为奇数，证明 $l = 1$，或假设 $l \ne 1$，证矛盾。 :::: 对于第一问，如果 $n$ 是合数，可以设 $n = ab$，按照高次方差得到 $2^a - 1 \mid 2^n - 1$，矛盾了。对于第二问，用 Hint 的设法再小小换个元也有矛盾。 ::::success[完整解答]{open} $$ n = 1 $$ $$ \therefore 2^n - 1 = 1 \not\in \mathbb{P} $$ 若 $n \not\in \mathbb{P}$，设 $n = ab$，$a, b \in [2, \infty) \cap \Z$。 $$ \therefore 2^n - 1 = 2^{ab} - 1 = (2^a)^b - 1 = (2^a - 1)(\cdots) $$ $$ 1 < 2^a - 1 < 2^n - 1, 2^a - 1 \mid 2^n - 1 $$ 矛盾。 $$ \therefore n \in \mathbb{P} $$ --- 若 $n \ne 2^k$，设 $n = 2^k \cdot l$，$l$ 为大于 $1$ 的奇数。 $$ 2^n + 1 = 2^{2^k \cdot l} + 1 = (2^{2^k})^l + 1 $$ 设 $a = 2^{2^k}$。 $$ \therefore 2^n + 1 = a^l + 1 = (a + 1)(\cdots) $$ $$ \therefore 1 < a + 1 < a^l + 1 = 2^n + 1, a + 1 \mid 2^n + 1 $$ 矛盾。 $$ \therefore n = 2^k $$ :::: ### 例题三 ::::info[题目]{open} 已知 $f(x)$ 为整系数多项式，且 $f(5) = 2005$，试问：$f(2005)$ 是否为完全平方数？ :::: 对于整系数多项式，我们只有 $a - b \mid f(a) - f(b)$，能够得到 $2000 \mid f(2005) - 2005$，容易得到 $5 \mid f(2005), 25 \nmid f(2005)$，即 $f(2005)$ 不为完全平方数。 ::::success[完整解答]{open} 当 $a = b$ 时，$f(a) - f(b) = 0$，由因式定理 $\forall a, b \in \Z, a - b \mid f(a) - f(b)$。 $$ \therefore 2005 - 5 = 2000 \mid f(2005) - f(5) = f(2005) - 2005 $$ $$ \because 5 \mid 2000 $$ $$ \therefore 5 \mid f(2005) - 2005 $$ $$ \because 5 \mid 2005 $$ $$ \therefore 5 \mid f(2005) $$ $$ \because 25 \mid 2000 $$ $$ 25 \mid f(2005) - 2005 $$ $$ \because 25 \nmid 2005 $$ $$ \therefore 25 \nmid f(2005) $$ 又 $$ 5 \mid f(2005) $$ $$ \therefore f(2005) \text{ 不为完全平方数。} $$ :::: # 降次与范围估计 对于 $g(x) \mid f(x)$ 的问题，可做带余除法 $f(x) \div g(x) \cdots r(x)$，得到 $g(x) \mid r(x)$。 1. $r(x)$ 为常数时，只需通过分解质因数得到 $r$ 的全体因数，再解 $g(x) = r$ 的方程的解，从而得出 $x$ 的值。 2. 由于 $\deg g(x) > \deg r(x)$，则能得到不等式 $|g(x)| \le |r(x)|$ 或 $r(x) = 0$，且解的范围是有限的，根据第一讲的知识，可以得到 $x$ 的范围即值，逐一代入检验即可。 3. 如果 $|g(x)| \le |r(x)|$ 或 $r(x) = 0$ 的范围太大，可以进一步做带余除法 $g(x) \div r(x) \cdots r_1(x)$，根据整除的性质得到 $g(x) \mid r_1(x)$，也就是说，只要有 $g(x)$ 和 $f(x)$，就可以得到 $g(x) \mid \text{常数}$ 的局面，就可以回到 1，并且不用检验。 ### 例题一 ::::info[题目]{open} 已知 $n + 10 \mid n^3 + 10$，求 $n$ 的最大值。 :::: 做带余除法得到 $(n^3 + 10) \div (n + 10) = (n^2 - 10n + 100) \cdots 990$，得到 $n + 10 \mid 990$，即 $(n + 10)_{\max} = 990$。 ::::success[完整解答]{open} $$ \because n + 10 \mid (n + 10)(n^2 - 10n + 100) $$ $$ \therefore n + 10 \mid n^3 + 10 - (n + 10)(n^2 - 10n + 100) = 990 $$ $$ \therefore (n + 10)_{\max} = 990 $$ $$ n_{\max} = 980 $$ :::: ### 例题二 ::::info[题目]{open} 已知 $n^2 + 10 \mid n^3 + 10$，求 $n$ 的最大值。 :::: 直接根据刚才的知识模拟即可。 ::::success[完整解答]{open} $$ \because n^2 + 10 \mid n(n^2 + 10) $$ $$ \therefore n^2 + 10 \mid 10n - 10 $$ $$ n^2 + 10 \le |10n - 10| \text{ 或 } 10n - 10 = 0 $$ 当 $10n - 10 = 0$ 时必然成立，所以 $n_{\max} \ge 1$，不妨设 $n \ge 1$。 $$ \therefore n^2 + 10 \le 10n - 10 $$ 解得 $$ n = 3, 4, 5, 6, 7 $$ 经检验 $n_{\max} = 1$。 :::: ### 例题三 ::::info[题目]{open} 求所有的 $1 < a < b < c$，使 $(a - 1)(b - 1)(c - 1) \mid abc - 1$。 :::: 一看整除的左边这么复杂，考虑换元 $x = a - 1, y = b - 1, z = c - 1$。代入化简得到 $xyz \mid xy + yz + zx + x + y + z$。令 $xy + yz + zx + x + y + z = kxyz$，同除 $xyz$ 后，变成了第一讲的多元对称有序枚举。 ::::success[完整解答]{open} 令 $x = a - 1, y = b - 1, z = c - 1$。 $$ \therefore x, y, z \ge 1 $$ $$ \therefore xyz \mid (x + 1)(y + 1)(z + 1) - 1 $$ $$ \therefore xyz \mid xy + yz + zx + x + y + z $$ 设 $$ xy + yz + zx + x + y + z = kxyz $$ $$ k = \sum_{cyc} \frac{1}{x} + \sum_{cyc} \frac{1}{xy} < 3 $$ $$ k = 1, 2 $$ （省略中间枚举过程，不会的去[第一讲](https://www.luogu.com.cn/article/ijfqsqnr)） 易得 $(x, y, z) = (1, 3, 7)$ 或 $(2, 4, 14)$，即 $(a, b, c) = (2, 4, 8)$ 或 $(3, 5, 15)$。 :::: ## 后记 **原创不易，点个赞再走吧~~** **求管理员通过qwq** [更多精彩，关注我们的合集](https://www.luogu.me/article/4y3zfcw5)