數學/數論/基本結果（可除性）著名定理

可除性的定義

如果一個整數 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| 個整數的集合，使得每個整數都與集合中的一個整數同餘。這個特定的餘數集合非常方便，但它不是唯一的選擇。