正如我们在高中数学中了解的那样，对整数进行加减乘产生的结果仍属于整数。与之不同，除法产生的结果有时不属于整数，比如 \(7\) 除以 \(3\) 的结果不属于整数。但是如果使用带余除法(division with a remainder)进行除法，产生的结果属于整数。比如，\(7\) 除以 \(3\) 等于 \(2\) ，余数为 \(1\)，因为\( 7 = 2 \cdot 3 + 1\) 。
在本节内，我们将介绍整数带余除法，也被称为欧几里得除法(Euclidean Division) 。带余除法是本书中许多概念的基础技术。下面给出了一个对带余除法的精确定义：
假设存在整数 \(a \in \Bbb{Z}\) 和整数 \(b \in \Bbb{Z}\) 且 \(b \neq 0 \) ，另存在 整数 \( m \in \Bbb{Z} \) 和自然数 \(r \in \Bbb{N} \) 且 \( 0 \leq r <|b| \) 满足以下条件：
\[a = m \cdot b + r \]
上述使用 \(b\) 对 \(a\) 的分解被称为欧几里得除法。在此除法中，我们称 \(a\) 为被除数(dividend)，\(b\) 为除数(divisor)，\(m\) 为商(quotient)，而 \(r\) 被称为余数(remainder)。可以证明，只要除数不为 \(0\) ，对于一个整数进行带余除法产生的商和余数都是唯一的。
符号 1
假设数 \(a\) 、 \(b\) 、 \(m\) 和 \(r\) 符合上述公式。我们使用以下符号表示带余除法的商和余数：
\[ \begin{align*} a\ div\ b: = m && a\ mod\ b: = r \end{align*} \]
如果 \(a\ mod\ b = 0\) 成立，我们可以称整数 \(a\) 可以被另一个整数 \(b\) 整除。 在这种情况下，我们写成\(b|a\) ，并且称整数 \(a\ div\ b\) 是 \(b\) 对 \(a\) 的共因子(cofactor)。
简而言之，带余除法是一个整数除以另一个整数的产生商和非负的余数的过程。其中余数小于除数的绝对值。
示例 2
因为 \(-17 = -5 \times 4 + 3 \) 是 \(-17\) 对 \(4\) 的带余除法。使用上文定义的符号和定义， \(-17\) 是被除数，而 \(4\) 是除数。可以使用以下表示：
\[ \begin{align*} {-17}\ div\ 4 = {-5} && {-17}\ mod\ 4 = 3 \end{align*} \]
根据定义，余数是非负数。根据上述运算，我们也可以知道 \(-17\) 不能被 \(4\) 整除，因为余数不为 \(0\) 。这意味着表达式 \(4|{-17}\) 的真值为 False 。当然，\(4|12\) 的真值为True，因为 \(12\) 可以被 \(4\) 整除，即 \(12\ mod\ 4 = 0\)。我们也可以使用sage进行实现：
sage: ZZ(-17) // ZZ(4) # 整数商
-5
sage: ZZ(-17) % ZZ(4) # 余数
3
sage: ZZ(4).divides(ZZ(-17)) # 整除测试
False
sage: ZZ(4).divides(ZZ(12))
True
备注 1
在上文中，我们根据带余除法定义了 a div b 和 a mod b 符号。但是，需要注意的是在很多编程语言(如Python和Sage)以不同方式实现了 / 和 % 符号。程序员需要特别注意数学符号和编程实现的差异，这可能导致进行密码学实现时出现细微的错误。
举一个例子，考虑被除数 \(-17\) 和 除数 \(-4\) 。注意，与上文的例子不同，此处的除数为负数。根据我们的定义，有：
\[ \begin{align*} {-17}\ div\ {-4} = {5} && {-17}\ mod\ {-4} = 3 \end{align*} \]
\({-17} = 5 \times (-4) + 3\) 是 \(-17\) 除以 \(-4\) 的带余除法结果(根据定义，余数是一个非负数)。但是，在Sage中使用 / 和 % 进行计算会获得一个不同的结果：
sage: ZZ(-17) // ZZ(-4) #商
4
sage: ZZ(-17) % ZZ(-4) # 余数
-1
sage: ZZ(-17).quo_rem(ZZ(-4))
(4, -1)
计算整数带余除法的方法被称为整数除法算法(integer division algorithms)。最著名的算法被称为长除法(long division) 。很多人可能在学校内学习过此算法。简而言之，长除法算法从左到右依次循环计算出除数的每一位，在每次循环减去除数的最大可能倍数(在位数层面)。倍数成为商的位数，余数是被除数的第一位。
长除法这段翻译的比较垃圾，可能是因为直译的原因，但考虑到读者应该都学习过长除法，所以暂且不再修改。
由于长除法是进行十进制数字进行纸笔除法运算的标准方法，在本书的大量进行纸笔计算的例子中，我们会经常使用长除法，所以读者应该熟悉此方法。但是，我们没有给出长除法的标准定义而是使用提供了一系列计算示例，因为这样可以使过程更加清晰。
示例 3
举一个长除法计算的示例，我们计算 \(a = 143785\) 除以 \(b=17\) 的结果。我们希望获得带余除法的标注形式，即 \(143785 = m \cdot 17 + r\) 的形式。竖式计算过程如下：
$$ \begin{array}{r} 8457 \\ 17 {\overline{\smash{\big)} 143785} } \\ \underline{136\phantom{000} } \\ 77\phantom{00} \\ \underline{ 68 } \phantom{00}\\ 98 \phantom{0}\\ \underline{ 85 } \phantom{0} \\ 135 \\ \underline{ 119 } \\ 16 \end{array} $$
由此，我们计算得到了 \(m = 8457\) 而 \(r = 16 \)，即 \(143785 = 8457 \times 17 + 16 \)。我们可以通过Sage进行验算：
sage: ZZ(143785).quo_rem(ZZ(17))
(8457, 16)
sage: ZZ(143785) == ZZ(8457)*ZZ(17) + ZZ(16)
True
练习 5. 长除法
找到 \(m \in \Bbb{Z} \) 和 \(r \in \Bbb{N} \) ，要求 \( 0 \leq r < |b| \) 使得 \(a = m \cdot b + r \) 对以下数组成立：
- \( (a, b) = (27, 5) \)
- \( (a,b)=(27,-5) \)
- \( (a,b)=(127,0) \)
- \( (a,b)= (-1687, 11) \)
- \( (a,b)= (0, 7) \)
在哪种情况下您的结果是唯一的？
练习 6. 长除法算法
使用您熟悉的编程语言实现整数的长除法算法并正确处理边缘情况。
练习 7. 二进制表示
编写一个算法以实现计算任何非负整数的二进制表示