歐幾里得120、什麼叫做輾轉相除法？舉幾個例子

什麼叫做輾轉相除法？舉幾個例子——網友提問

…

2019-09-15，angela韓雪倩（qiàn）：輾轉相除法最大的用途就是用來求兩個數的最大公約數。

用（a，b）來表示a和b的最大公約數。有定理：已知a，b，c為正整數，若a除以b餘c（a÷b=商……C），則（a，b）=（b，c）。（證明過程請參考其它資料）

…小學數學用“a÷b=商……C（a除以b餘c）”表示有餘數的除法…

…（a，b）=（b，c）：（被除數，除數）=（除數，餘數）；被除數、除數的最大公約數=除數、餘數的最大公約數…

…被除數、除數的最大公因數=除數、餘數的最大公因數：例如，15、8的最大公因數為1，15除以8餘7（15÷8=1……7），8、7的最大公因數是1，15、8的最大公因數=8、7的最大公因數=1…

2019-11-05，苗徵宇傳送影片。

影片內容：

“上個影片，我們學習瞭如何用分解質因數法求最大公因數和最小公倍數。在使用這個方法時，需要先將每個數分解質因數。例如90=2×3^2（90=2×3的平方），105=3×5×7…”主持人說。

“但並不是每個數都那麼好分解。比如下面兩個數就很難分解：3139=？2117=？…”主持人接著說。

“遇到這種情況，分解質因數法也無能為力，這怎麼辦？”主持人繼續說。

“不用擔心，這種情況就是輾轉相除法大顯身手的時刻…”主持人最後說。

“輾轉相除法主要用來計算兩個數的最大公因數。在使用時，先用較大的除以較小的，算出餘數。然後用除數繼續除以餘數，求出新的餘數。接著再用除數除以餘數…不停迴圈…直到餘數為0。”主持人說。

“此時的除數就是最大公因數。”主持人接著說。

“比方說這兩個數：3139，2117…”主持人繼續說，“首先用3139除以2117，商1，餘1022。然後用除數2117除以1022，商2餘73。接著繼續用1022除以73，商14餘0。餘數為0，就此打住…”

“此時的除數73，就是3139和2117的最大公因數。”主持人最後說。

“無論兩個數多大，用輾轉相除法都可以方便的求出最大公因數。是不是很厲害！”主持人說。

“這個方法，大家以後在學計算機程式設計的時候還會見到。到時，你可以讓電腦快速計算最大公因數。是不是很帥！”主持人最後說。

2020-07-12，183*****858：除數除以餘數得0後，除數就是最大公因數。

輾轉相除法，其計算原理依賴於下面的定理：

…輾、轉、輾轉、輾轉相除法：見《歐幾里得119》…

…原、理、原理：見《歐幾里得41》…

…定、理、定理：見《歐幾里得2》…

定理：兩個整數的最大公約數等於其中較小的那個數和兩數相除餘數的最大公約數。

…其它表述為：被除數、除數、餘數是整數，被除數除以除數，得到餘數，則（被除數，除數）=（除數，餘數）；a、b、c是整數，a除以b餘c，則（a，b）=（b，c）；a、b、c是整數，a÷b=商……c，則（a，b）=（b，c）…

[…（a，b）：整數a與整數b的最大公約數…]

“a、b、c是整數，a÷b=商……c，則（a，b）=（b，c）”有多種證法：

證法一

a可以表示成a = kb + r（a，b，k，r皆為正整數，且r<b），則r = a mod b

…mod：“Module Operation”的首字母縮寫（取前三個字母）…

…module（英語）：n.（名詞）單元（尤指英國大學課程的一部分）；模組；功能塊；程式塊；元件；配件…

…Operation（英語）：n.操作；經營；[外科]手術；[數][計]運算…

（…[數]：數學行業…

…[計]：計算機行業…）

…Module Operation：取模運算…

“取模運算是求兩個數相除的餘數。

請看下集《歐幾里得121、取、模，運、算、運算，取模運算》”

若不知曉歷史，便看不清未來