2.2　除法定理

除法定理也称带余除法。设，且。如果存在，使得，则称整除，记作。此时，叫作的因数，叫作的倍数。

如果不能整除，则记作。由于不能整除，这个时候就需要引入余数，即除法定理[8]。

定理2.2.1　除法定理（Division Theorem）

设且，这样存在唯一的整数使得:

并且。被称为商(Quotient)，被称为余数(Remainder)。

除法定理是整除的基本定理，是数论的证明中最基本、最常用的工具。例如，在证明与整数不同进制表示相关的定理时，就需要用到除法定理。下面尝试证明除法定理。

证明

设且。考虑整数序列:

则必在上述序列某相邻的两项之间。假设：

于是，令，则。因此，当时，就有，证明了的存在性。

假设存在另一组，使得，，则：

因此，从而，即，，证明了q,r具有唯一性。

结合存在性和唯一性，除法定理得证。

例2.2.1　当，。计算除以的商和余数。

解：，那么现在就可以知道商。余数就可以很容易计算得到。

例2.2.2　当，。计算除以的商和余数。

解：，那么现在就可以知道商。余数就可以很容易计算得到。