Question

（1）用輾轉(zhuǎn)相除法求9322與6903的最大公約數(shù)；
（2）用更相減損術求168與105的最大公約數(shù)．

Answer 1

考點：用輾轉(zhuǎn)相除計算最大公約數(shù)

專題：算法和程序框圖

分析：（1）根據(jù)輾轉(zhuǎn)相除法的步驟，將9322與6903代入易得到答案．
（2）根據(jù)“以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)．繼續(xù)這個操作，直到所得的減數(shù)和差相等為止．”的原則，易求出168與105的最大公約數(shù)．

解答： 解：（1）（5分）∵9322=6903×1+2419，6903=2419×2+2065，2419=2065×1+354
2065=354×5+295，354=295×1+59，295=59×5，∴9322與6903的最大公約數(shù)是59；
（2）（5分）∵168-105=63，105-63=42，63-42=21，42-21=21，
∴168與105的最大公約數(shù)是21．

點評：本題考查的知識點是輾轉(zhuǎn)相除法，對任意整數(shù)a，b，b＞0，存在唯一的整數(shù)q，r，使a=bq+r，其中0≤r＜b，這個事實稱為帶余除法定理，若c|a，c|b，則稱c是a，b的公因數(shù)．若d是a，b的公因數(shù)，且d可被a，b的任意公因數(shù)整除則稱d是a，b的最大公因數(shù)．當d≥0時，d是a，b公因數(shù)中最大者．若a，b的最大公因數(shù)等于1，則稱a，b互素．累次利用帶余除法可以求出a，b的最大公因數(shù)，這種方法常稱為輾轉(zhuǎn)相除法．更相減損術的方法和步驟是：以較大的數(shù)減較小的數(shù)，接著把所得的差與較小的數(shù)比較，并以大數(shù)減小數(shù)．繼續(xù)這個操作，直到所得的減數(shù)和差相等為止．