一、带余除法的定义

• **【带余除法】**设 $a, b \in \Z$ 且 $b > 0$，那么存在唯一的两个整数 $q$ 和 $r$ 使得：

  1. $a= qb + r$（称作带余除法式）；
  2. $r \in [0, b)$。

  这里 $q$ 叫做不完全商，$r$ 叫做余数。

  证明：

  • 存在性：
    • 构建集合 $R = \{ a-qb \mid q \in \Z, a-qb \ge 0 \}$。
    • 说明 $R$ 非空。存在足够小的 $q$（保证 $q \le a/b$ 且 $q \in \Z$ 即可）对应的 $a-qb \in R$，因而 $R$ 非空。
    • 又 $R \subseteq \N$，根据良序原理（自然数集的非空子集一定存在最小元素），$R$ 存在最小元，记为 $r^$，对应的 $q$ 为 $q^$。那么就有 $r^* = a-q^*b$ 即 $a= q^b + r^$。
    • 反证法证 $r^* \in [0, b)$。假设 $r^* \ge b$，那么记 $\hat r = r^-b$，有 $\hat r \ge0$ 和 $\hat r=a-q^b-b = a-(q^+1)b$。故 $\hat r \in R$ 且 $\hat r \le r^$，与 $r^*$ 是 $R$ 的最小元矛盾。
  • 唯一性：
    • 假设除了题设 $q,r$ 外还存在 $\tilde q, \tilde r \in \Z$ 使得 $a= \tilde qb + \tilde r$ 且 $\tilde r \in [0, b)$。
    • 有 $a = qb + r = \tilde qb + \tilde r$，即 $(q - \tilde q)b = \tilde r - r$。右侧取值范围 $(-b, b)$，左侧取值范围是 $b$ 的整数倍，因而唯一解是 $q-\tilde q = 0$ 且 $\tilde r - r = 0$，即 $q = \tilde q$，$r = \tilde r$。

• 【带余除法推论】设 $a, b \in \Z$ 且 $b \neq 0$，那么存在唯一的两个整数 $q$ 和 $r$ 使得：$a= qb + r$，$r \in [0, |b|)$。

  证：

  • $b > 0$ 时用上述定理即得。
  • $b < 0$ 时，存在唯一的两个整数 $q, r$ 使得 $a= q(-b) + r$，$r \in [0, -b)$，即 $a= (-q)b + r$，$r \in [0, |b|)$，即得唯一的 $q'=-q$ 和 $r$ 满足题意。

二、使用带余除法给出证明

1. 连续整数与整除

• 任何 $n$ 个连续整数中必有一个是 $n$ 的倍数。

  证：

  • 设这 $n$ 个数为 $m, m+1, m+2, \cdots, m+n-1$。
  • 作带余除法式 $\exists \, q, r \in \Z$，$m = qn + r$，$r \in [0, n)$，变换为 $m + n - r = (q+1)n$。
  • 这 $n$ 个数可以写为 $m + n - n, m+n - (n-1), m+n - (n-2), \cdots, m+n-1$。分类讨论 $r$。
    • 如果 $r \neq 0$，因为 $r \in (0, n)$，那么显然这 $n$ 个数中有一个是 $m + n - r$，故它是 $n$ 的倍数。
    • 如果 $r = 0$，那么 $m = qn$，$m$ 就是 $n$ 的倍数。

2. 一些恒整除式

• $\forall n \in \Z, \, 3 \mid n(n+1)(2n+1)$。

  **证明：**分类讨论。

  • 当 $n = 3k$ 时，马上有 $3 \mid n$，根据倍数线性性质即得证。
  • 当 $n=3k+1$ 时，$2n + 1 = 6k + 3 = 3(2k + 1)$，有 $3 \mid 2n+1$，同上。
  • 当 $n=3k+2$ 时，$n + 1 = 3k+3 = 3(k+1)$，有 $3 \mid n+1$，同上。

• $\forall n \in \Z, \, 6 \mid n(n+1)(n+2)$。

  证明：

  • 任何 $2$ 个连续整数中必有一个是 $2$ 的倍数。因而 $2 \mid n(n+1)$，故 $2 \mid n(n+1)(n+2)$。
  • 任何 $3$ 个连续整数中必有一个是 $3$ 的倍数。因而 $3\mid n(n+1)(n+2)$。
  • 因为 ${\rm GCD}(2, 3)=1$，有 $(2\times 3)\mid n(n+1)(n+2)$ 得证。

  • 类似地，有：$\forall n \in \Z, \, 12 \mid n(n+1)(n+2)(n+3)$。

• $\forall n \in \Z, \, 30 \mid n^5 - n$。

  证明：

  • $n^5 - n = n(n^4 - 1) = n(n^2 + 1)(n^2 - 1) = n(n^2 + 1)(n + 1)(n - 1)$。
  • 注意到 $n^2 + 1 = (n + 2) (n + 3) - 5(n+1)$。
  • $n^5 - n = (n-1)n(n+1)(n+2)(n+3) - 5(n-1)^2n(n+1)$。
  • 任何 $5$ 个连续整数中必有一个是 $5$ 的倍数，故 $5 \mid (n-1)n(n+1)(n+2)(n+3)$。又 $5 \mid 5(n-1)^2n(n+1)$，根据倍数的线性变换，有 $5 \mid n^5 - n$。
  • 已经证明 $6 \mid (n-1)n(n+1)$ 得 $6 \mid n^5 - n$。因 ${\rm GCD}(5, 6)=1$，有 $(5\times 6)\mid n^5 - n$ 得证。

3. 一些其他命题或题目

**例题：**求使得 $n - 1 \mid n^2 + 3n + 2$ 的所有整数 $n$。

• 解答：作 $m = n-1$，得到整除式成立的充要条件 $m \mid m^2 + 5 m + 6$，此整除式的充要条件是 $\frac {m^2 + 5m + 6}{m} = m + 5 + \frac 6 m$ 是整数，即 $\frac 6 m$ 是整数，充要条件是 $m \mid 6$ 即 $m=\pm 1, \pm 2, \pm 3, \pm 6$ 即 $n= -5, -2, -1, 0, 2, 3, 4, 7$。
• 如需形式化证明，需要避免出现除式和xx是不是整数的描述，可以利用下面这个定理：
  • 对于 $a, b, m \in \Z$，若 $m \mid a$，那么 $m \mid b \Leftrightarrow m \mid (a \pm b)$。
  • 这样，已知 $m \mid m^2 + 5 m$，那么 $m \mid m^2 + 5 m + 6$ 成立的充要条件是 $m \mid 6$。
  • 或者直接写成这样一个逆天的注意到：注意到 $n^2 + 3n + 2 = (n-1)(n+4) + 6$。由于 $n-1 \mid n-1$ 得 $n-1 \mid (n-1)(n+4)$，根据定理知道原整除式成立的充要条件是 $n - 1 \mid 6$。由于 $6$ 的因数有且仅有 $\pm 1, \pm 2, \pm 3, \pm 6$，因而 $n= -5, -2, -1, 0, 2, 3, 4, 7$ 是所有让 $n - 1 \mid 6$ 成立的取值。

三、多项式带余除法

• **【多项式的定义】**设 $n \in \N$，$a_0, a_1, \cdots, a_n \in {\mathbb P}$（${\mathbb P}$ 是任意数域），$a_n \neq 0$，那么称 $P(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$ 为一个 $n$ 次多项式。
• **【多项式的带余除法】**对于多项式 $P(x), M(x)$，且 $P(x)$ 的次数大于 $M(x)$ 的次数，那么存在唯一的一对多项式 $Q(x), R(x)$ 使得 $P(x) = M(x) Q(x) + R(x)$，其中 $R(x)$ 的次数要小于 $M(x)$ 的次数。

四、辗转相除/减法求解 GCD

1. 辗转相除/减法原理

• 【辗转相除/减法理论依据】对于 $a,b,c \in \Z$，如果 $\exists \, q \in \Z$ 使得 $a = bq + c$（或者 $a = bq - c$）成立，那么有：

  • ① ${\rm CD} (a, b) = {\rm CD} (b, c)$；
  • ② 如果 $a, b, c$ 不全为零，有 ${\rm GCD} (a, b) = {\rm GCD} (b, c)$。

  证：

  • 下面证①。
    • $\subseteq$：对于所有 $p \in \Z, \, p \neq 0$ 使得 $p \mid a$ 和 $p \mid b$，由于 $c = a - bq$（$c = bq - a$），由于倍数的线性性质，有 $p \mid c$，因而 ${\rm CD} (a, b) \subseteq {\rm CD} (b, c)$。
    • $\supseteq$：对于所有 $p \in \Z, \, p \neq 0$ 使得 $p \mid b$ 和 $p \mid c$，由于 $a = bq+c$（$a = bq-c$），由于倍数的线性性质，有 $p \mid a$，因而 ${\rm CD} (a, b) \supseteq {\rm CD} (b, c)$。
  • 证得①后，②就显然成立：假设有一个数不为零，那么等号至少一边的 ${\rm GCD}$ 就存在，根据 ${\rm CD}$ 的相等，另一头就也存在。

• **【辗转相除法】**对于两个不全为零的整数 $c_0, c_1$（$c_1 \ge 0$），如果一者为零，GCD 即为另一者的绝对值（根据 ${\rm GCD} (0, n) \equiv |n|$），否则它们均不为零，这时可以连续作带余除法：

  $$ \begin{align*} c_0 &= q_1c_1 + c_2, \ c_2 \in [0, c_1) \\ c_1 &= q_2c_2 + c_3, \ c_3 \in [0, c_{2}) \\ & \ \ \vdots \\ c_{n-2} &= q_{n-1}c_{n-1} + c_n, \ c_n \in [0, c_{n-1}) \\ & \ \ \vdots \\ \end{align*}

  $$

  • 其中每一步，都能推导 ${\rm CD}$ 的保持：

    $$ \begin{matrix}

    {\rm CD}(c_0, c_1) = {\rm CD}(c_1, c_2) \\

    {\rm CD}(c_1, c_2) = {\rm CD}(c_2, c_3) \\

    \vdots \\

    {\rm CD}(c_{n-2}, c_{n-1}) = {\rm CD}(c_{n-1}, c_n) \\

    \vdots \\ \end{matrix} $$

  • 设算法在出现 $c_N = 0$ 时终止（$N \ge 2$）。这时就立即获得 ${\rm GCD}(c_0, c_1) = {\rm GCD} (c_{N-1}, 0) = c_{N-1}$。算法一定会在有限步后终止，因为每一步 $c_n$ 都会降低，而下界是 $0$，算法一定会在 $c_1$ 步内终止。

  • 举例：求解 114 和 514 的最大公因数。

    114 514 114 58 56 2 0