【數學】不好意思，我想問一下輾轉相除法

[陽明的黑炭 10]

輾轉相除法我會計算，但我看不懂= = ，兩個數一直相除怎麼能找到最大公因數勒??

可以解釋一下原理嗎??謝謝

[我不是打獵的 10]

輾轉相除法我會計算，但我看不懂= = ，兩個數一直相除怎麼能找到最大公因數勒??

可以解釋一下原理嗎??謝謝

設a=bq+r

a是被除數。

b是除數。

q是商。

r是餘數。

假設(a,b)=d

(b,r)=e

只要證明d=e就可以解答你的問題。

因為d│a且d│b

所以d│a-bq=>d│r。

故d小於等於e

因為e│b且e│r

所以e│a

故e小於等於d

所以d=e

得證。

沒記錯的話應該是這樣證明...

有錯請跟我說...

a/b=q...r

這時候用b當被除數。

r當除數

b/r=新的商...新的餘數。

因為(a,b)=(b,r)....

應該是這樣吧...

[藍色月全蝕 10]

設a=bq+r

a是被除數。

b是除數。

q是商。

r是餘數。

假設(a,b)=d

(b,r)=e

只要證明d=e就可以解答你的問題。

因為d│a且d│b

所以d│a-bq=>d│r。

故d小於等於e

因為e│b且e│r

所以e│a

故e小於等於d

所以d=e

得證。

沒記錯的話應該是這樣證明...

有錯請跟我說...

a/b=q...r

這時候用b當被除數。

r當除數

b/r=新的商...新的餘數。

因為(a,b)=(b,r)....

應該是這樣吧...

請愛用除法定理跟線性組合.

[DUM 10]

要問原理很簡單

反正減掉倍數不影響公因數

就一直不斷來回的減

壤兩個數越來越小

最後沒辦法減時 就是最大公因數