数学/数论/基本结果（可除性）著名定理

可除性的定义

如果一个整数 b 可被一个非零整数 a 整除，则存在一个整数 x 使得 b = ax，我们写作 $a|b$ 。如果 b 不能被 a 整除，我们写作 $a\nmid b$ 。例如 $3|6$ 和 $4\nmid 6$ 。

如果 $a|b$ 且 0 < a < b，则 a 称为 b 的真因子。符号 $a^{k}||b$ 用于表示 $a^{k}|b$ 但 $a^{k+1}\nmid b$ 。例如 $3||6$ 。

基本性质

$a|b$ 意味着 $a|bc$ 对于任何整数 c 来说。
$a|b$ 和 $b|c$ 意味着 $a|c$ 。
$a|b$ 和 $a|c$ 意味着 $a|(bx+cy)$ 对于任何整数 x 和 y 来说。
$a|b$ 和 $b|a$ 意味着 $a=\pm b$ .
$a|b$ , a > 0, b > 0, 意味着 $a\leq b$ .
如果 $m\neq 0$ , $a|b$ 意味着且被 $ma|mb$ 意味着。

证明:

显然，如果 $a|b$ 那么 $\exists$ x 使得 b = ax。那么 bc = a(xc) = ay，因此 $a|bc$ .
$a|b$ 和 $b|c$ 意味着存在 m,n 使得 b = am 且 c = bn。那么显然 c = bn = (am)n = ap，因此 $a|c$ .
$a|b$ 和 $a|c$ 意味着存在 m,n 使得 b = am 且 c = an，因此 bx + cy = amx + any = az，所以 $a|bx+cy$ .
$a|b$ 和 $b|a$ 意味着存在 m,n 使得 b = am 且 a = bn。那么 a = bn = amn，因此 mn = 1。m 和 n 的唯一选择是同时为 1 或 -1。无论哪种情况，我们都有结果。
b = ax 对于某个 x > 0，否则 a 和 b 将具有相反的符号。所以 b = (a + a + ...) x 次 $\geq$ a。
$a|b$ 意味着存在一个 x 使得 b = ax，这暗示 mb = amx，即 $ma|mb$ 。反之， $ma|mb$ 意味着 mb = max，由此可知 b = ax，因此 $a|b$ 得证。

备注:

性质 2 和 3 可以通过数学归纳法扩展到任意有限集。也就是说， $a_{1}|a_{2}$ ， $a_{2}|a_{3}$ ， $a_{3}|a_{4}\cdots a_{k-1}|a_{k}$ 意味着 $a_{1}|a_{k}$ ；并且 $a|b_{1}$ ， $a|b_{2}\cdots a|b_{n}$ 意味着 $a|\sum _{j=1}^{n}b_{j}x_{j}$ ，对于任意整数 $x_{j}$ 。
性质 4 利用了整数集中唯一的单位是 1 和 -1。（环中的单位是指具有乘法逆元的元素。）

除法算法

具体来说，除法算法指出，给定两个整数 *a* 和 *d*，其中 *d* ≠ 0

存在唯一的整数 *q* 和 *r* 使得 *a* = *qd* + *r* 且 0 ≤ *r* < | *d* |，其中 | *d* | 表示 *d* 的绝对值。

注意：整数

q 称为 **商**
r 称为 **余数**
d 称为 **除数**
a 称为 **被除数**

证明：证明分为两部分——首先证明 *q* 和 *r* 的存在性，其次证明 *q* 和 *r* 的唯一性。

我们首先考虑存在性。

考虑集合

S=\left\{a-nd:n\in \mathbb {Z} \right\}

我们断言 *S* 至少包含一个非负整数。需要考虑两种情况。

如果 *d* < 0，则 -*d* > 0，根据阿基米德原理，存在一个非负整数 *n* 使得 (-*d*)*n* ≥ -*a*，即 *a* - *dn* ≥ 0。
如果 *d* > 0，则根据阿基米德原理，存在一个非负整数 *n* 使得 *dn* ≥ -*a*，即 *a* - *d*(-*n*) = *a* + *dn* ≥ 0。

无论哪种情况，我们都证明了 *S* 包含一个非负整数。这意味着我们可以应用良序原理，并推断出 *S* 包含一个 *最小* 非负整数 *r*。如果我们现在令 *q* = (*a* - *r*)/*d*，则 *q* 和 *r* 是整数，且 *a* = *qd* + *r*。

剩下的工作就是证明 0 ≤ *r* < |*d*|。第一个不等式成立，因为我们选择 *r* 为一个 *非负* 整数。为了证明最后一个（严格）不等式，假设 *r* ≥ |*d*|。由于 *d* ≠ 0，所以 *r* > 0，并且 *d* > 0 或 *d* < 0。

如果 *d* > 0，则 *r* ≥ *d* 意味着 *a*-*qd* ≥ *d*。这意味着 *a*-*qd*-*d* ≥0，进一步意味着 *a*-(*q*+1)*d* ≥ 0。因此，*a*-(*q*+1)*d* 属于 *S*，并且由于 *a*-(*q*+1)*d*=*r*-*d*，*d*>0，我们知道 *a*-(*q*+1)*d*<*r*，这与 *r* 是 *S* 中最小的非负元素的假设相矛盾。
如果d<0，则r ≥ -d，这意味着a-qd ≥ -d。这表明a-qd+d ≥0，进一步表明a-(q-1)d ≥ 0。因此，a-(q-1)d 在S中，并且由于a-(q-1)d=r+d 且d<0，我们知道a-(q-1)d<r，这与r是S中最小的非负元素的假设相矛盾。

无论哪种情况，我们都证明了r > 0 实际上并不是S中最小的非负整数。这是一个矛盾，因此我们必须有r < |d|。这完成了对q和r存在性的证明。

现在让我们考虑唯一性。

假设存在q，q' ，r，r' ，其中 0 ≤ r，r' < |d|，使得a = dq + r 且 a = dq' + r' 。不失一般性，我们可以假设q ≤ q' 。

减去这两个方程得到：d(q' - q) = (r - r' )。

如果d > 0，则r' ≤ r 且r < d ≤ d+r' ，因此 (r-r' ) < d。类似地，如果d < 0，则r ≤ r' 且r' < -d ≤ -d+r，因此 -(r- r' ) < -d。将这些组合起来得到 |r- r' | < |d|。

原始方程表明 |d| 除 |r- r' |；因此要么 |d| ≤ |r- 'r' |（如果 |r- r' | > 0，使得 |d| 也 > 0，并且上述基本属性的性质 5 成立），要么 |r- r' |=0。因为我们刚刚确定 |r-r' | < |d|，我们可以得出第一个可能性不成立的结论。因此，r=r' 。

将此代入原始两个方程中很快得出 dq = dq' ，并且由于我们假设d不为 0，因此必须是q = q' ，证明了唯一性。

备注:

除法算法这个名字有点误导，因为它是一个定理，而不是一个算法，即一个为完成特定任务而定义明确的过程。
关于余数集合 {0, 1, ..., |d| − 1} 没有什么特别之处。我们可以使用任何包含 |d| 个整数的集合，使得每个整数都与集合中的一个整数同余。这个特定的余数集合非常方便，但它不是唯一的选择。