輾轉相除法

能否細說輾轉相除法的應用並舉出一點類題讓我參考另外能否一步一步來解題
a

b是整數

則存在整數q

r

使得a=bq r

這叫作歐幾里德除法原理 此時gcd(a

b)=gcd(b

r) 這叫作輾轉相除法原理所以被除數跟除數的最大公因數會等於除數跟餘數的最大公因數亦即

(被除數

除數)=(除數

餘數).................與商無關1.例如：以輾轉相除法求出1280

1620的最大公因數？ 先用1620除以1280

得到1餘340 再用1280除以340

得到3餘260 如此輾轉相除

最後整除前是除以20

20便是最大的公因數1| 1620 | 1280 | 3_| 1280 | 1020 |------------------------1| 340 | 260 | 3_| 260 | 240 |-----------------------4| 80 | 20 |_| 80 |_____ |-----------------------0所以由上面算式可知最大公因數為20 2.輾轉相除法是用來求最大公因數通常是用在數字較大的地方例如:以(5320

4389)為例步驟一:用兩數中較大的數去除以較小的數 商寫於外

餘數直接列於下一列步驟二 :用步驟一的餘數(931)當除數

原除數(4389)當成被除數再進行除法相除

方式與步驟一相同.步驟三:重複步驟二的方式進行除法直到餘數為0為止則最後一次的除數(133)即為各數的最大公因數 3.例如:如何快速的分解多項式的除法

求取最大公因數大部分[可以分解]的多項式幾乎可以用底下方法:1. [牛頓法]---先搜尋他的一次因式2.如果可以將次數降到2次以下.3.套用乘法公式至於求取最大公因式

除了分解以外

還可用輾轉相除法.4.