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

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

例如：  3139÷2117=1……1022

              2117÷1022=2……73

              1022÷73=14

              (3139,2117)=73

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

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

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

先一起來(lái)看一道題目。

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

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

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

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

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

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

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

     第一步：在長(zhǎng)和寬分別是2703和1113的長(zhǎng)方形里，2703可以分出2個(gè)1113，還余477。

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

      第二步：在長(zhǎng)和寬分別是1113和477的長(zhǎng)方形里，1113可以分出2個(gè)477，還余159。

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

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

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

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

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