歐幾里得120、什么叫做輾轉(zhuǎn)相除法？舉幾個例子

?

什么叫做輾轉(zhuǎn)相除法？舉幾個例子——網(wǎng)友提問

?

…

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

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

?

…小學(xué)數(shù)學(xué)用“a÷b=商……C（a除以b余c）”表示有余數(shù)的除法…

…（a，b）=（b，c）：（被除數(shù)，除數(shù)）=（除數(shù)，余數(shù)）；被除數(shù)、除數(shù)的最大公約數(shù)=除數(shù)、余數(shù)的最大公約數(shù)…

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

2019-11-05，苗征宇發(fā)送視頻。

視頻內(nèi)容：

“上個視頻，我們學(xué)習(xí)了如何用分解質(zhì)因數(shù)法求最大公因數(shù)和最小公倍數(shù)。在使用這個方法時，需要先將每個數(shù)分解質(zhì)因數(shù)。例如90=2×3^2（90=2×3的平方），105=3×5×7…”主持人說。

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

“遇到這種情況，分解質(zhì)因數(shù)法也無能為力，這怎么辦？”主持人繼續(xù)說。

“不用擔(dān)心，這種情況就是輾轉(zhuǎn)相除法大顯身手的時刻…”主持人最后說。

?

“輾轉(zhuǎn)相除法主要用來計算兩個數(shù)的最大公因數(shù)。在使用時，先用較大的除以較小的，算出余數(shù)。然后用除數(shù)繼續(xù)除以余數(shù)，求出新的余數(shù)。接著再用除數(shù)除以余數(shù)…不停循環(huán)…直到余數(shù)為0?！敝鞒秩苏f。

“此時的除數(shù)就是最大公因數(shù)?！敝鞒秩私又f。

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

“此時的除數(shù)73，就是3139和2117的最大公因數(shù)?！敝鞒秩俗詈笳f。

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

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

?

2020-07-12，183*****858：除數(shù)除以余數(shù)得0后，除數(shù)就是最大公因數(shù)。

?

?

輾轉(zhuǎn)相除法，其計算原理依賴于下面的定理：

…輾、轉(zhuǎn)、輾轉(zhuǎn)、輾轉(zhuǎn)相除法：見《歐幾里得119》…

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

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

?

定理：兩個整數(shù)的最大公約數(shù)等于其中較小的那個數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。

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

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

?

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

證法一

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

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

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

…Operation（英語）：n.操作；經(jīng)營；[外科]手術(shù)；[數(shù)][計]運算…

（…[數(shù)]：數(shù)學(xué)行業(yè)…

…[計]：計算機行業(yè)…）

…Module Operation：取模運算…

?

“取模運算是求兩個數(shù)相除的余數(shù)。

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

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

歡迎關(guān)注嗶哩號“中國崛起呀”