請 AI 小老師教我輾轉相除法(歐幾里得算法，Euclidean algorithm)
感謝 GPT 4 小老師教我輾轉相除法。
請教我輾轉相除法
輾轉相除法是一種尋找兩數最大公因數的方法，也叫做歐幾里得演算法。以下是它的基本步驟：
- 給定兩個非零整數a和b，並讓a >= b。
- 將a除以b取得商數和餘數 (a = bq + r)。
- 如果餘數r等於0，那麼b就是a和b的最大公因數。
- 如果餘數r不等於0，那麼讓a = b，b = r，並回到第二步繼續運算，直到找到最大公因數。
舉個例子：
假設我們要找72和90的最大公因數。
首先，90比72大，所以我們將90換成a，72換成b。
90 ÷ 72 = 1 餘 18
然後將72變成a，18變成b。
72 ÷ 18 = 4餘0
所以，72和90的最大公因數是18。
我是一個五歲的小朋友，請教我輾轉相除法
輾轉相除法是一種找兩個數的最大公因數的方法。最大公因數就是兩個數最大的公共數字。那麼我們就來學習輾轉相除法怎麼做吧！
首先，讓我們用兩個簡單的數字作為例子，比如說12和15。
步驟如下：
- 把兩個數中的大數除以小數。在這個例子中，我們把15除以12，我們發現不能整除，剩下的數字是3（15–12）。
- 然後我們再用原來的小數（也就是12）除以這個剩下的數字3，這次可以整除，結果是4。
- 因為現在可以整除了，我們就找到了這兩個數的最大公因數，這個例子中，最大公因數就是3。
輾轉相除法就是這樣，不停的除，直到能夠整除為止，最後能整除的那個數，就是我們要找的最大公因數。
用 table format 說明輾轉相除法
用 mermaid 說明輾轉相除法，以數字 12 和 15 為例
舉一個最大公因數是 1 的例子
當兩個數的最大公因數（GCD）為1時，我們說這兩個數是互質的。舉個例子，我們來找7和5的最大公因數。
我將使用表格形式來說明：
用 mermaid 說明輾轉相除法
sequenceDiagram
participant 開始
participant 較大的數字
participant 較小的數字
participant 餘數
participant 結果
開始->>較大的數字: 選擇兩個數字中較大的一個
較大的數字->>較小的數字: 選擇兩個數字中較小的一個
較小的數字->>餘數: 較大的數字除以較小的數字，算出餘數
餘數->>結果: 如果餘數為0，則較小的數字就是最大公因數
結果->>較大的數字: 如果餘數不為0，則較小的數字成為新的較大的數字
結果->>較小的數字: 如果餘數不為0，則餘數成為新的較小的數字
較小的數字-->>開始: 繼續這個過程，直到找到最大公因數為止
為什麼這樣可以找出最大公因數
這是基於數的因數的性質。如果你有兩個數 a 和 b（其中 a > b），並且你把 a 除以 b 得到商數 q 和餘數 r，所以 a = bq + r。
讓我們看看兩者的因數：
假設有一個數字 d 是 a 和 b 的公因數，那麼 d 可以整除 a 和 b。也就是說，a 和 b 都可以寫成 d 的倍數。
因此，我們可以寫 a = md 和 b = nd，其中 m 和 n 是某些整數。
我們知道 a = bq + r，代換之前的等式，我們可以得到 md = ndq + r。將等式移項得到 r = md — ndq = d(m — nq)。
這個等式告訴我們 r 也可以寫成 d 的倍數，所以 d 是 r 的因數。因此，所有 a 和 b 的公因數 d 也都是 b 和 r 的公因數。
同理，我們也可以證明所有 b 和 r 的公因數也都是 a 和 b 的公因數。
因此，兩組數字 a, b 和 b, r 的最大公因數是相同的。這就是輾轉相除法可以找到兩個數字的最大公因數的原因。
