Question

利用輾轉(zhuǎn)相除法求兩個正數(shù)8251和6105的最大公約數(shù)。

Answer 1

解：8251＝6105×1＋2146

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

6105＝2146×2＋1813

2146＝1813×1＋333

1813＝333×5＋148

333＝148×2＋37

148＝37×4＋0

則37為8251與6105的最大公約數(shù)。