歡迎訪問我的主頁: https://heeheeaii.github.io/

輾轉相除法是一種用于計算兩個非負整數最大公約數的有效算法。它的證明主要分為兩個部分：

• 證明核心引理： gcd(a,b)=gcd(b,amodb)
• 證明算法的收斂性： 證明算法一定會在有限步內結束。

輾轉相除法簡介

在開始證明之前，先回顧一下輾轉相除法的步驟。對于任意兩個正整數 a 和 b (不妨設 a>b)：

1. 用 a 除以 b，得到商 q 和余數 r。即 a=qb+r，其中 0≤r<b。
2. 如果余數 r 為 0，那么 b 就是 a 和 b 的最大公約數。
3. 如果余數 r 不為 0，則將原來的除數 b 作為新的被除數，將余數 r 作為新的除數，重復第一步。

如此循環，直到余數為 0。此時，最后一次計算中的除數就是原始 a 和 b 的最大公約數。

引理： 設 a,b 為兩個正整數，且 a=qb+r（其中 q 為商， r 為余數，0≤r<b），那么 a 和 b 的最大公約數等于 b 和 r 的最大公約數。即：gcd(a,b)=gcd(b,r)。

證明過程：

為了證明這個等式，只需要證明 (a,b) 的公約數集合與 (b,r) 的公約數集合是完全相同的。如果兩個集合完全相同，那么它們各自的最大元素（即最大公約數）也必然相等。

1. 證明：任何 (a,b) 的公約數 d，也一定是 (b,r) 的公約數。

假設 d 是 a 和 b 的一個任意公約數。根據公約數的定義，有 d∣a 和 d∣b。（這里的 ∣ 表示“整除”）。

因為 d 能整除 a 和 b，所以 d 也能整除它們的任意線性組合。將算法中的等式 a=qb+r 變形為 r=a?qb。因為 d∣a 且 d∣b，所以 d 必然能整除 a?qb。因此，得到 d∣r。

既然已知 d∣b 且證明了 d∣r，那么 d 就是 b 和 r 的一個公約數。

2. 證明：任何 (b,r) 的公約數 d′，也一定是 (a,b) 的公約數。

假設 d′ 是 b 和 r 的一個任意公約數。根據定義，有 d′∣b 和 d′∣r。

因為 d′ 能整除 b 和 r，所以 d′ 也能整除它們的任意線性組合。從算法等式 a=qb+r 中，可以看到 a 正是 b 和 r 的一個線性組合。因為 d′∣b（所以 d′∣qb）且 d′∣r，所以 d′ 必然能整除 qb+r。因此，得到 d′∣a。

既然已知 d′∣b 且證明了 d′∣a，那么 d′ 就是 a 和 b 的一個公約數。

1. 算法為什么一定會終止？

在輾轉相除法的每一步中，都有一個等式： ri?1=qi?ri+ri+1

其中 ri?1 是被除數，ri 是除數，ri+1 是余數。根據整數除法的性質，余數必須嚴格小于除數，且不能為負數。所以得到一個余數序列： b>r1>r2>r3>?>rn≥0

這是一個由非負整數組成的嚴格遞減序列。任何由非負整數組成的嚴格遞減序列最終必然會達到 0。因此，算法一定會在有限步內終止，即一定會出現某一步的余數 rn+1=0。

2. 為什么余數為 0 時，當時的除數就是最大公約數？

根據核心引理，可以將求 gcd(a,b) 的過程轉化為一個鏈條： gcd(a,b)=gcd(b,r1)=gcd(r1,r2)=?=gcd(rn?1,rn)

當算法進行到最后一步時，余數為 0。假設這一步的表達式為： rn?1=qn+1?rn+0

這表示 rn 能夠整除 rn?1。那么，需要求解的就是 gcd(rn?1,rn)。根據最大公約數的定義，一個數 (rn?1) 和它的約數 (rn) 的最大公約數就是那個約數本身 (rn)。 所以，gcd(rn?1,rn)=rn。

將這個結果代入上面的等式鏈條，得到： gcd(a,b)=gcd(rn?1,rn)=rn

這里的 rn 正是算法終止前的最后一個非零余數，也就是最后一步計算中的除數。

舉例說明：

用 gcd(1071,462) 來演示這個過程：

• 1071=2?462+147 根據引理：gcd(1071,462)=gcd(462,147)
• 462=3?147+21 根據引理：gcd(462,147)=gcd(147,21)
• 147=7?21+0 根據引理：gcd(147,21)=gcd(21,0) 此時余數為 0，算法終止。最后一步的除數是 21。

把整個鏈條連起來： gcd(1071,462)=gcd(462,147)=gcd(147,21)=21

所以，1071 和 462 的最大公約數是 21。