歐幾里德算法

習題預習

1. 求出最大公因數(GCD)為何，輸入數字為6和8?
2. 如果我有輸入數字為28和35，求出最大公因數(GCD)為何?
3. 輸入數字為210和45，求出最大公因數(GCD)為何?
4. 如果我要求出104和910的最大公因數(GCD)，應該怎麼做?
5. 如果我有輸入數字為22和121，求出最大公因數(GCD)為何?

說明知識

Euclid’s Algorithm是一個用來找到兩個正整數的最大公因數的快速方法。這個演算法最早由古希臘數學家歐幾里德所發明，因此得名Euclid’s Algorithm。

這個演算法基於以下的觀察：如果a和b是兩個數，且a>b，那麼

1. 將a除以b，得到商q和餘數r。
2. 如果r=0，那麼b是a和b的最大公因數。
3. 否則，將原本的b設為a，將原本的r設為b，並回到第1步。

我們可以用一個例子來說明這個演算法：

舉例來說，我們想找到84和18的最大公因數。

1. 84除以18，得到商4和餘數12。
2. 12不是0，所以把原本的b設為18，把原本的r設為12，並回到第1步。
3. 18除以12，得到商1和餘數6。
4. 6不是0，所以把原本的b設為12，把原本的r設為6，並回到第1步。
5. 12除以6，得到商2和餘數0。
6. 因為餘數為0，所以最大公因數為6。

因此，我們可以快速地找到84和18的最大公因數為6。這個演算法非常有用，不僅可用於解題，還被廣泛應用於加密和資訊安全領域。

彙總重點

1. Euclid’s Algorithm是求兩個正整數最大公因數的方法。
2. 求法是用除法求餘數，將較小的數不斷與餘數進行除法求餘數，直到餘數為零，那麼最後被除數即為兩數的最大公因數。
3. Euclid’s Algorithm可以用遞迴或循環的方法實現。
4. 堆棧或遞歸空間的使用可以通過在每次遞迴或循環中保留較小數和餘數來控制。
5. Euclid’s Algorithm的時間複雜度為O(log n)，其中n為輸入數的位數。

知識測驗

1. 使用Euclid’s Algorithm求最大公因數(gcd)和最小公倍數(lcm)：

數字1：108，數字2：72

答案：gcd為36，lcm為216

2. 使用Euclid’s Algorithm求解ax + by = gcd(a,b)的整數解，其中a = 42，b = 30。

答案：x = 1，y = -1

3. 使用Euclid’s Algorithm求最大公因數(gcd)和最小公倍數(lcm)：

數字1：125，數字2：85

答案：gcd為5，lcm為425

4. 使用Euclid’s Algorithm求解ax + by = gcd(a,b)的整數解，其中a = 16，b = 10。

答案：x = -3，y = 5

5. 使用Euclid’s Algorithm求最大公因數(gcd)和最小公倍數(lcm)：

數字1：270，數字2：192

答案：gcd為6，lcm為1,440