昨天我們講了求兩個較大數(shù)的最大公因數(shù)時，用輾轉(zhuǎn)相除法來求比較簡單。這種方法是古希臘數(shù)學(xué)家歐幾里德最先提出來的，所以也叫歐幾里德算法（Euclidean algorithm），這個算法最早出現(xiàn)在公元前300年古希臘著名數(shù)學(xué)家歐幾里得的《幾何原本》(第VII卷,命題i和ii)中。而在中國則可以追溯至東漢出現(xiàn)的《九章算術(shù)》。

       輾轉(zhuǎn)相除法是先用兩個數(shù)中較大的數(shù)除以較小的數(shù)，如果有余數(shù)，則用較小的那個數(shù)繼續(xù)除以余數(shù)，按照這樣的方法一直除下去，除到余數(shù)為0為止。那么最后的除數(shù)就是兩個數(shù)的最大公因數(shù)。

例如：  3139÷2117=1……1022

              2117÷1022=2……73

              1022÷73=14

              (3139,2117)=73

為什么用輾轉(zhuǎn)相除法可以求最大公因數(shù)呢？道理是什么？

這個我也不知道，要不我們一起去問問老師吧。老師，您能跟我們講講用輾轉(zhuǎn)相除法為什么可以求最大公因數(shù)嗎？

真是兩位愛學(xué)習(xí)的好孩子！那就讓我跟你們說道說道吧。

先一起來看一道題目。

     有一張長方形紙，長是2703厘米，寬是1113厘米，要把它裁成若干個大小相同的正方形，要使正方形的邊長盡可能大且紙張沒有剩余，正方形邊長是多少厘米?

老師，紙張不能有剩余也就是說這個正方形的邊長既是長方形長的因數(shù)，又能長方形寬的因數(shù)，也就是長方形長和寬的公因數(shù)。而正方形的邊長又要盡可能大，阿，這道題實際上就是在求2703和1113的最大公因數(shù)。可以用輾轉(zhuǎn)相除法來求。

天天可真會分析！沒錯，就是求2703和1113的最大公因數(shù)。今天老師帶你們用畫圖的方法來解決這個問題，請看視頻，并思考這個過程跟輾轉(zhuǎn)相除法有什么關(guān)系？

視頻中聰聰說159是477、1113和2073的公因數(shù)，這句話你們能理解嗎？為什么這樣畫出來后，就能說159是2073和1113的公因數(shù)了呢？

477里面有3個159，所以477能被159整除；1113里面有2個447和1個159，477能被159整除，159也能被159整除，所以1113也一能被159整除；2703里面有2個1113和1個477，1113能被159整除，477能被159整除，所以2703也一定能被159整除。因此證明159是1113和2703的公因數(shù)，而且是最大。

美美分析得真是太有道理了！老師把你的說得意思畫下來，就是下圖。

從上圖中是不是很直觀地看出159是1113和2703的最大公因數(shù)了呀！那么這個“畫”最大公因數(shù)的過程跟輾轉(zhuǎn)相除法有什么關(guān)系呢？你有看出來嗎？讓我們一起來把這個過程用除法算式表示出來看看吧！

     第一步：在長和寬分別是2703和1113的長方形里，2703可以分出2個1113，還余477。

      用較大數(shù)除以較小數(shù)：2703÷1113=2……477

      第二步：在長和寬分別是1113和477的長方形里，1113可以分出2個477，還余159。

        用除數(shù)除以余數(shù)：1113÷477=2……159

        第三步：在長和寬分別是477和159的長方形里，477剛好可以分出3個159，沒有余數(shù)。

        用除數(shù)除以余數(shù)：477÷159=3

        上面算式，先用較大數(shù)除以較小數(shù)，如有余數(shù)，再依次用除數(shù)除以余數(shù)，直到余數(shù)為0，此時的除數(shù)就是最大公因數(shù)。這個“畫”最大公因數(shù)的過程用算式表示就是輾轉(zhuǎn)相除法。

天天、美美，現(xiàn)在你們明白為什么用輾轉(zhuǎn)相除法可以求最大公因數(shù)嗎？