除法算法

在本课程中，我们将把除法算法作为一个原理加以展开，该原理形式化地刻画了整数情形下的唯一分解 b=qa+r，其中 0\le r<|a|。首先证明商与余数的存在性，随后证明其唯一性。最后，将解释余数的意义，把理论与作为计算过程的长除法算法联系起来，并预示其与模算术及计算应用之间的自然联系。

学习目标

完成本课程后，学生将能够：

1. 识别整数除法的基本概念与角色（被除数、除数、商、余数），以及作为精确情形的可除性概念。
2. 解释欧几里得除法算法/定理的表述，包括用于确定余数的条件（0\le r<|a|）及其避免歧义的目的。
3. 应用欧几里得分解 b=qa+r 在具体示例中求出 q 与 r，并验证余数的界限。
4. 分析根据被除数与除数符号划分的情形，论证为何欧几里得约定保持余数非负。
5. 执行基于位值表示的长除法算法，作为一种机械化过程来得到 q 与 r。

内容索引:
除法与可除性
欧几里得除法定理
欧几里得除法的证明
商与余数的解释
长除法算法
结论
建议与已解习题

除法与可除性

在算术中，可除性描述的是“精确”的情形：a\mid b 表示 b 可以恰好写成 a 的倍数。然而，尽管任意两个整数之间并不总是存在可除性，我们仍然可以提出这样的问题：“一个数在另一个数中能容纳多少次？如果不能恰好容纳，剩下的是什么？”正是在这一背景下产生了除法算法，它保证任意整数 b 都可以表示为 a 的一个倍数加上一个“余数”。

例如，考虑 a=3 与 b=16。显然，3 不能整除 16。然而，仍然可以为该除法运算找到一个商和一个余数，因为

16 = 5\cdot 3 + 1

因此，将 b=16 除以 a=3（其中 b 为被除数，a 为除数），可表示为 16/3 或 16\div 3，其商为 q=5，余数为 r=1。一般而言，除法算法断言：对于任意整数 a（除数）与 b（被除数），且满足 a\neq 0，存在唯一的整数 q 与 r 使得

b=qa+r,\qquad 0\le r<|a|

在该示例中，16=3\cdot 5+1，且条件 0\le r<|a| 得到满足，因为 0\le 1<3。这种表述在除数（或被除数）可能为负的情况下避免了歧义，并保证余数始终非负且严格小于除数的绝对值。

欧几里得除法定理

应用除法算法所得的结果称为欧几里得除法，其依据如下所示的结果。

定理：设 a,b\in\mathbb{Z} 且 a\neq 0。则存在唯一的 q,r\in\mathbb{Z} 使得

b=qa+r,\qquad 0\le r<|a|.

整数 q 称为商，r 称为将 b 除以 a 所得的余数。

欧几里得除法的证明

该证明分为两部分：首先证明商与余数的存在性；随后，在其存在的前提下，证明它们的唯一性。

存在性

设 a,b\in\mathbb{Z} 且 a\neq 0，并定义 d=|a|，从而有 d>0。我们首先证明 b\ge 0 的情形：将说明存在 q,r\in\mathbb{Z} 使得 b=dq+r 且 0\le r<d。随后再处理 b<0 的情形。最后，用 |a| 取代 d，从而得到形式 b=qa+r 且满足 0\le r<|a|。

对于满足 b\in\mathbb{Z} 且 b\ge 0 的情形，我们建立命题 P(b)：“存在 q,r\in\mathbb{Z} 使得 b=dq+r 且 0\le r<d”。我们将通过数学归纳法证明，对于所有 b\ge 0，P(b) 都成立。

基例：当 b=0 时，取 q=0 与 r=0，得到 0=d\cdot 0+0 且 0\le 0<d。因此，P(0) 为真。

归纳步骤：设 k\ge 0，并假设 P(k) 为真。则存在 q,r\in\mathbb{Z} 使得

k=dq+r,\qquad 0\le r<d.

对等式两边同时加上 1，得到

k+1=dq+(r+1).

此外，由 0\le r<d 可知 r+1\le d。因此，只可能出现 r+1<d 或 r+1=d 两种情况。

情形 1：若 r+1<d，定义 q'=q 与 r'=r+1。则

k+1=dq'+r',\qquad 0\le r'<d.

情形 2：若 r+1=d，则 k+1=dq+d=d(q+1)+0。定义 q'=q+1 与 r'=0，并满足

k+1=dq'+r',\qquad 0\le r'<d.

在两种情形下，我们都构造了整数 q',r'，使得 k+1=dq'+r' 且 0\le r'<d。因此，P(k+1) 为真。由归纳法可得，对于所有 b\ge 0，P(b) 都成立。

现在考虑 b<0 的情形。此时有 -b>0。将上述结果应用于 -b，存在 q,r\in\mathbb{Z} 使得

-b=dq+r,\qquad 0\le r<d.

两边同乘以 -1，得到

b=-dq-r.

若 r=0，只需取 q_1=-q 与 r_1=0，则有 b=dq_1+r_1 且 0\le r_1<d。

若 r>0，定义 q_1=-q-1 与 r_1=d-r。由于 0<r<d，可得 0<d-r<d，即 0\le r_1<d。此外，

dq_1+r_1=d(-q-1)+(d-r)=-dq-d+d-r=-dq-r=b.

因此，对于所有 b\in\mathbb{Z}，都存在 q_1,r_1\in\mathbb{Z}，使得 b=dq_1+r_1 且 0\le r_1<d。

最后，回顾 d=|a|。若 a>0，则 d=a，等式 b=dq_1+r_1 可写为 b=aq_1+r_1，并且满足 0\le r_1<|a|。

若 a<0，则 d=-a，并且 b=dq_1+r_1=(-a)q_1+r_1=a(-q_1)+r_1。定义 q=-q_1 与 r=r_1，即可得到

b=qa+r,\qquad 0\le r<|a|.

由此，对于任意满足 a,b\in\mathbb{Z} 且 a\neq 0 的情形，q 与 r 的存在性得证。

唯一性

设存在 q,q',r,r'\in\mathbb{Z}，使得

b=qa+r=q'a+r',\qquad 0\le r,r'<|a|.

对上述两个等式相减，得到

a(q-q')=r'-r.

由于 0\le r,r'<|a|，可得 |r'-r|<|a|。另一方面，左侧是 a 的倍数，因此也是 |a| 的倍数。绝对值严格小于 |a| 的 |a| 的唯一整数倍是 0；事实上，若 |a| m \neq 0 且 m\in\mathbb{Z}，则 \big| |a| m \big| \ge |a| 。因此，r'-r=0，即 r=r'；代入 b=qa+r，可推出 q=q'。由此可知，该分解是唯一的。

商与余数的解释

• “余数”的含义。 若 b=qa+r，则 r=b-qa 表示从 b 中去除倍数 qa 后所“剩余”的部分。换言之，r 是将 b 调整到 a 的倍数组成的网格上时所产生的剩余量。
• 为何要求 0\le r<|a|。若没有该条件，成对的 (q,r) 将不再唯一。事实上，若 b=qa+r，则同样可以写成 b=a(q+1)+(r-a)。条件 0\le r<|a| 将余数限制在固定区间 \{0,1,2,\dots,|a|-1\} 内，从而阻断了对同一整数进行无限次“重新标记”的可能性。
• 当 a 为负时会发生什么。 定理在不作任何修改的情况下依然成立：余数保持非负，并受 |a| 的上界约束。这一点很重要，因为某些编程语言采用向零截断，可能产生负余数；而在数学中则采用约定 0\le r<|a|，使余数成为一个“标准”的代表。

  此外，当 a>0 时，商与下取整函数一致：

  q=\left\lfloor \frac{b}{a}\right\rfloor,\qquad r=b-a\left\lfloor \frac{b}{a}\right\rfloor.

长除法算法

基于欧几里得除法，可以利用数字的位值表示来实现长除法算法。该算法是一种计算技术，当需要计算 b\div a 且 a,b\in\mathbb{Z} 并满足 a\neq 0 时，它能够快速求得 q 与 r 的值。

为描述该算法，我们首先回顾一些示例，以说明算法执行过程中的步骤以及可能出现的情况。

1. 假设我们要计算 57\div 4。其中 57 是被除数，4 是除数。为此，我们将执行如下计算序列：

   \begin{array}{rll} (1) & \color{red}57 \div 4 =\color{black} \\ & \text{写出除法运算。} \\ \\ (2) & \color{red}5'\color{black}7 \div 4 = \\ & \text{从左侧分离出被除数的第一个前缀，使其}\\ &\text{大于或等于除数，本例中为 5。} \\ \\ (3) & 5'7 \div 4 = \color{red}1\color{black} \\ & \text{思考一个最大的数，使其与 $4$ 相乘后}\\ &\text{小于或等于 $5$，并将其写在等号右侧。该数为 1。} \\ \\ (4) & \begin{array}{ll}\phantom{-|}5'7 \div 4 &= 1 \\ \color{red}-|\underline{4}\color{black} & \\ \color{red}\phantom{-|}1\color{black} & \end{array} \\ & \text{将结果乘以除数，并从所选数中减去。} \\ \\ (5) & \begin{array}{ll}\phantom{-|}5'\color{red}7'\color{black} \div 4 &= 1 \\ -|\underline{4} & \\ \phantom{-|}1\color{red}7\color{black} & \end{array} \\ & \text{选择并“下移”下一个数字。} \\ \\ (6) & \begin{array}{ll}\phantom{-|}5'7' \div 4 &= 1\color{red}4\color{black} \\ -|\underline{4} & \\ \phantom{-|}17 & \\ \color{red}-|\underline{16}\color{black} & \\ \color{red}\phantom{-|}1\color{black} \end{array} \\ & \text{用最后得到的数重复上述步骤。} \end{array}

   当没有更多数字可以“下移”时，算法结束，所得结果为商 q=14 和余数 r=1。特别地，余数始终小于除数。

2. 假设我们要计算 132\div 5。为此，将执行如下计算序列：

   \begin{array}{rl} (1) &1'32 \div 5 = \\ & \text{分离被除数的第一个前缀，并寻找一个自然数，}\\ & \text{使其与 5 相乘后小于或等于该前缀。若无法做到，}\\ & \text{则并入下一个数字，直到可以为止。} \\ \\ (2) &\begin{array}{ll}\phantom{-|}13'2 \div 5 &= 2 \\ -|\underline{10} & \\ \phantom{-|1}3 & \end{array}\\ & \text{一旦上述步骤可行，即按常规执行算法。} \\ \\ (3) &\begin{array}{ll}\phantom{-|}13'2' \div 5 &= 26 \\ -|\underline{10} & \\ \phantom{-|1}32 & \\ \phantom{\,} -|\underline{30} & \\ \phantom{-|30} 2 & \end{array} \end{array}

3. 若被除数具有更多位数，则以相同方式执行该过程。例如，计算 3521\div 12 时，得到：

   \begin{array}{ll} \phantom{-|}35'2'1' \div 12 & = 293 \\ -|\underline{24} & \\ \phantom{-|}112 & \\ -|\underline{108} & \\ \phantom{-|10}41 & \\ \phantom{0}-|\underline{36} & \\ \phantom{10-|}5 & \\ \end{array}

4. 若其中一个数为负，则存在两种可接受的结果表示方式。然而，在数论中采用的标准形式是余数为正的表示方式，从而与欧几里得除法保持一致。例如，若计算 -598\div 21，可得到如下两种展开形式，二者作为恒等式均是正确的：

   • 带负余数： 该形式通过在运算开始时去掉符号，并在最后恢复符号得到。

     \begin{array}{ll} \phantom{-}59'8' \div 21 &= 28 \\ -|\underline{42} & \\ \phantom{-|'}178 & \\ \phantom{\,}-|\underline{168} & \\ \phantom{-|00}10 & \\ \end{array}

     由此可得：

     598 = 21 \times 28 + 10

     随后，将整个等式乘以 -1，得到：

     -598 = 21 \times (-28) - 10

     因此，在该表示下，-598\div 21 的结果为商 q=-28，余数 r=-10。

     若再次将整个等式乘以 -1，则得到：

     598 = (-21)\times(-28) + 10

     因此，598\div (-21) 的结果为商 q=-28，余数 r=10。

   • 带正余数并与欧几里得除法一致： 基于上述展开，可得：

     -598 = 21 \times (-28) - 10

     随后，在等式右侧加上 0=21-21，得到：

     -598 = 21 \times (-28) - 10 \color{red}+ 21 - 21\color{black} = 21\times(-29) + 11

     因此，若与欧几里得除法保持一致，计算 -598\div 21 的结果为商 q=-29，余数 r=11。

   就欧几里得除法中的约定而言，只有余数为正的结果才对应于欧几里得意义下的商与余数。然而，这两种表达形式都是正确的恒等式，并且在不同语境中可能具有实用价值。尽管长除法算法可能产生负余数，但这在机械化地获得结果以及进行代数运算而无需额外步骤时是便利的。另一方面，与欧几里得除法一致、余数为正的结果能够为每一个剩余类确定一个规范代表（例如，在 \{0,1,\dots,n-1\} 中），从而使整数的标记更加精确且避免歧义。需要指出的是，一旦规则被固定，也还存在其他同样有效的代表约定，例如对称余数。

结论

除法算法保证任何整数除法都可以唯一地表示为 b=qa+r，并满足 0\le r<|a|，从而确立了一个标准准则，用以解释即使在涉及负数时的商与余数。长除法算法不过是这种分解在实践中的一种实现，它依托于位值表示，使得 q 与 r 可以通过机械方式计算得到。最后，这种欧几里得形式不仅避免了歧义，而且还自然地与模算术相联系：余数 r 充当了 b 模 a 的剩余类的规范代表，这是数论中许多技术以及计算应用的基础，这些内容将在后续章节中加以讨论。

习题（含示例解答）

欧几里得除法

1. （已解） 求 q 与 r，使得

   137 = 9q + r,\qquad 0\le r\lt 9.

   解：寻找一个最大的数，使其与 9 相乘后不超过 137。我们有 15\times 9 = 135，而 16\times 9 = 144，因此所求的商为 q=15。接着计算余数 r=137-9q，并验证 0\le r\lt 9。计算得到：

   r=137-9\cdot 15=137-135=2.

   因此，137=9\cdot 15+2，并满足 0\le 2\lt 9。

2. （已解） 求 q 与 r，使得

   2025 = 37q + r,\qquad 0\le r\lt 37.

   解：寻找一个最大的数，使其与 37 相乘后不超过 2025。注意到 37\times 54 = 1998，而 37\times 55 = 2035，因此所求的商为 q=54。接着计算余数 r=2025-37q，并验证 0\le r\lt 37。计算得到：

   r=2025-37\cdot 54=2025-1998=27.

   因此，2025=37\cdot 54+27，并满足 0\le 27\lt 37。

3. 求 q 与 r，使得

   745 = 23q + r,\qquad 0\le r\lt 23.

4. 求 q 与 r，使得

   -314 = 11q + r,\qquad 0\le r\lt 11.

5. 求 q 与 r，使得

   598 = (-21)q + r,\qquad 0\le r\lt |-21|.

6. 固定余数与整数的寻找。 设 a=12。

   (a) 描述所有整数 b 的集合，使其除以 12 的欧几里得除法余数为 r=5。

   (b) 求满足上述条件且 b\gt 1000 的最小整数，并确定相应的商 q。

长除法算法

在每一种情形中，应用长除法算法来计算商 q 和余数 r。当算法给出负余数时，将结果转换为欧几里得除法的形式。

1. 84\div 6.
2. 197\div 8.
3. 1256\div 7.
4. -3521\div 12.
5. -98765\div 24.
6. 845\div -13.
7. -12345\div -37.