Question

利用輾轉相除法求兩個正數8251和6105的最大公約數。

Answer 1

解：8251＝6105×1＋2146

顯然8251的最大公約數也必是2146的約數，同樣6105與2146的公約數也必是8251的約數，所以8251與6105的最大公約數也是6105與2146的最大公約數。

6105＝2146×2＋1813

2146＝1813×1＋333

1813＝333×5＋148

333＝148×2＋37

148＝37×4＋0

則37為8251與6105的最大公約數。