辗转相除法完整解析：原理、步骤与例题

1. 公式
   观察依据

   白板上寫有 a ÷ $b = q$ ... r 與 a = bq + r

a

被除數

正整數

1. 公式
   观察依据

   白板上寫有 a ÷ $b = q$ ... r 與 a = bq + r

b

除數

正整數

1. 公式
   观察依据

   白板上寫有 a ÷ $b = q$ ... r

q

商

非負整數

1. 公式
   观察依据

   白板上寫有 a ÷ $b = q$ ... r 與 a = bq + r

r

餘數

非負整數

1. 公式
   观察依据

   白板上寫有 (a, b) = (b, r)

(a, b)

a 與 b 的最大公因數

正整數對

1. 公式
   观察依据

   白板上寫有 設 (a, b) = m

m

假設的 a 與 b 的最大公因數

正整數

1. 公式
   观察依据

   白板上寫有 a = mk_1

$k_1$

a 除以 m 後的整數因子

整數

1. 公式
   观察依据

   白板上寫有 b = mk_2

$k_2$

b 除以 m 後的整數因子

整數

1. 声音
   观察依据

   講者說明輾轉相除法是用來找出兩個數的最大公因數，做法是重複執行大除以小，一直到有一邊為零為止。

2. 图示
   观察依据

   畫面左側寫出 4369 與 5911 兩個數字，並畫出直線分隔欄位。

輾轉相除法是一種用於計算兩個正整數最大公因數的算法。其核心操作是將較大的數除以較小的數取得餘數，然後將原本的除數與新取得的餘數作為下一輪的被除數與除數，重複此過程直到餘數為零。此時最後一個非零的除數即為兩數的最大公因數。

1. 適用於兩個正整數

2. 每次除法取非負餘數

3. 終止條件為餘數等於零

1. 声音
   观察依据

   講者提到輾轉相除法是以除法原理為基礎去做運算。

2. 公式
   观察依据

   白板上寫出 a ÷ $b = q$ ... r 以及 a = bq + r。

對於任意整數 a 與正整數 b，存在唯一的整數 q 與 r，使得 a = bq + r 且 $0 \le r < b$。其中 q 稱為商，r 稱為餘數。這是輾轉相除法每一步驟的數學依據。

1. b 為正整數

2. r 為非負整數且小於 b

1. 声音
   观察依据

   講者說明 a 跟 b 的最大公因數會等於 b 跟 r 的最大公因數，並給出證明。

2. 公式
   观察依据

   白板上寫出 (a, b) = (b, r)，並推導出 $r = m(k_1 - k_2q)$。

1. 視頻僅證明了 m 也是 r 的因數，從而得出 (b, r) 的最大公因數至少為 m，但未嚴格證明不存在比 m 更大的公因數（即未證明另一方向的包含關係）。

若 a = bq + r，則 a 與 b 的最大公因數等於 b 與 r 的最大公因數。這意味著在求最大公因數時，可以用較小的數對 (b, r) 來替代較大的數對 (a, b)，從而逐步縮小問題規模。

1. a, b, q, r 為整數

2. a = bq + r

1. 除法原理

1. 声音
   观察依据

   講者斷言 a 跟 b 的最大公因數會等於 b 跟 r 的最大公因數。

2. 公式
   观察依据

   白板上寫出 (a, b) = (b, r)。

1. 視頻中的證明只展示了 (a,b) 的公因數也是 (b,r) 的因數，未完整雙向證明兩者集合相等，但結論本身是正確的標準定理。

對於整數 a, b, q, r 滿足 a = bq + r，有 gcd(a, b) = gcd(b, r)。

1. a = bq + r

對於所有滿足條件的整數 a, b, q, r

1. 公式
   观察依据

   白板上逐步寫出設 (a,b)=m, a=mk_1, b=mk_2, 代入 a=bq+r 得到 mk_1 = mk_2q + r，移項得到 $r = m(k_1 - k_2q)$。

1. 證明不完整，僅證明了 m | r，未證明 gcd(b,r) | m。

1. 公式

   $$\text{設 } (a, b) = m$$
   解释

   假設 a 和 b 的最大公因數為 m。

   步骤依据

   定義

   视频直接表达
2. 公式

   $$a = mk_1, \quad b = mk_2$$
   解释

   根據最大公因數的定義，a 和 b 都可以被 m 整除。

   步骤依据

   整除定義

   视频直接表达
3. 公式

   $$a = bq + r \implies mk_1 = mk_2q + r$$
   解释

   將 a 和 b 的表達式代入除法原理等式。

   步骤依据

   等量代換

   视频直接表达
4. 公式

   $$r = mk_1 - mk_2q = m(k_1 - k_2q)$$
   解释

   移項並提取公因數 m。

   步骤依据

   代數變形

   视频直接表达
5. 公式

   $$m \mid r$$
   解释

   因為 $k_1$, $k_2$, q 都是整數，所以 ($k_1 - k_2q$) 是整數，故 m 整除 r。

   步骤依据

   整除定義

   视频直接表达

視頻得出結論：m 也是 r 的因數，因此 b 和 r 的最大公因數至少包含 m（視頻表述為『就會是 m』，略去嚴謹的双向論證）。

1. 图示
   观察依据

   白板上展示了完整的豎式計算過程：5911÷4369餘1542，4369÷1542餘1285，1542÷1285餘257，1285÷257餘0。

2. 声音
   观察依据

   講者同步朗讀每一步的除法運算結果。

計算 gcd(5911, 4369)。

1. $a = 5911$

2. $b = 4369$

求出兩數的最大公因數。

1. 公式

   $$5911 = 4369 \times 1 + 1542$$
   解释

   大數除以小數，商 1 餘 1542。

   步骤依据

   除法原理

   视频直接表达
2. 公式

   $$4369 = 1542 \times 2 + 1285$$
   解释

   上一輪的除數 4369 除以餘數 1542，商 2 餘 1285。

   步骤依据

   除法原理

   视频直接表达
3. 公式

   $$1542 = 1285 \times 1 + 257$$
   解释

   上一輪的除數 1542 除以餘數 1285，商 1 餘 257。

   步骤依据

   除法原理

   视频直接表达
4. 公式

   $$1285 = 257 \times 5 + 0$$
   解释

   上一輪的除數 1285 除以餘數 257，商 5 餘 0。

   步骤依据

   除法原理

   视频直接表达

gcd(5911, 4369) = 257

餘數為 0 時的除數 257 即為最大公因數。

1. 公式
   观察依据

   白板上寫出 (5911, 4369) = (4369, 1542) = (1542, 1285) = (1285, 257) = 257。

2. 声音
   观察依据

   講者解釋如何將理論應用於剛才的具體數字，逐步替換數對。

解釋為何上述豎式計算能得到正確的最大公因數。

1. 前面的豎式計算結果

2. 定理 (a, b) = (b, r)

建立數對之間的等價鏈。

1. 公式

   $$(5911, 4369) = (4369, 1542)$$
   解释

   因為 $5911 = 4369\times 1 + 1542$。

   步骤依据

   最大公因數遞減性質

   视频直接表达
2. 公式

   $$(4369, 1542) = (1542, 1285)$$
   解释

   因為 $4369 = 1542\times 2 + 1285$。

   步骤依据

   最大公因數遞減性質

   视频直接表达
3. 公式

   $$(1542, 1285) = (1285, 257)$$
   解释

   因為 $1542 = 1285\times 1 + 257$。

   步骤依据

   最大公因數遞減性質

   视频直接表达
4. 公式

   $$(1285, 257) = 257$$
   解释

   因為 $1285 = 257\times 5 + 0$，257 整除 1285。

   步骤依据

   整除性質

   视频直接表达

257

最終結果與豎式計算一致。

1. 图示
   观察依据

   顯示標題「輾轉相除法」及卡通形象。

1. 文字：輾轉相除法

2. 卡通角色

1. 靜態畫面

引入主題。

1. 动画
   观察依据

   隨著講者解說，白板上依次出現除法豎式的數字：1, 4369, 1542; 2, 3084, 1285; 1, 1285, 257; 5, 1285, 0。

1. 數字 5911, 4369

2. 除法豎式結構

1. 餘數從 1542 變為 1285，再變為 257，最後變為 0

2. 除數隨之更新為上一輪的餘數

1. 每次運算都是 大數 ÷ 小數

視覺化展示算法的迭代過程，直到餘數為零。

1. 动画
   观察依据

   白板上逐行寫出除法原理公式及最大公因數相等的推導過程。

1. 變量 a, b, q, r, m, $k_1$, $k_2$

2. 等式

1. 從具體算式過渡到抽象符號推導

1. 邏輯順序：定義 -> 假設 -> 代換 -> 結論

展示算法背後的數論基礎。

1. 声音
   观察依据

   講者說『所以 m 也是 r 的因數之一... b 跟 r 的最大公因數就會是 m』。

僅證明 gcd(a,b) 的因數也是 gcd(b,r) 的因數，就認為兩者相等。

嚴格的證明需要雙向推導：既要證明 gcd(a,b) | gcd(b,r)，也要證明 gcd(b,r) | gcd(a,b)，才能得出兩者相等。視頻中只展示了前者（m | r），雖然結論正確，但論證過程在數學上是不完整的。

1. 声音
   观察依据

   講者明確指出輾轉相除法是以除法原理為基礎。

除法原理提供了輾轉相除法中每一步『大除以小取餘數』的數學合法性與唯一性保證。

1. 公式
   观察依据

   白板上的 (a,b)=(b,r) 直接支撐了算法的迭代邏輯。

最大公因數的遞減性質是輾轉相除法能夠通過不斷縮小數對來求解的根本原因。

1. 声音
   观察依据

   詳細的操作步驟講解與實例演算。

1. 輾轉相除法的定義與操作步驟
2. 使用輾轉相除法求 5911 與 4369 的最大公因數

1. 公式
   观察依据

   除法原理與 gcd 性質的推導。

1. 除法原理
2. 最大公因數的遞減性質
3. 最大公因數遞減性質的證明（單向）