promotion image of download ymail app
Promoted
? asked in 科學及數學數學 · 1 decade ago

輾轉相除的reason是什麼

輾轉相除的reason是什麼

Update:

easy d

1 Answer

Rating
  • Tinhoi
    Lv 4
    1 decade ago
    Favorite Answer

    輾轉相除法",中國古代叫作"更相減損求等",有兩個應用:

    (1)求兩數a,b的最大公因數

    (2)求不定方程式ax+by=c的整數解

    預備性質(1)若,則對任意整數m,n,

    預備性質(2)若,則

    輾轉相除法原理

    a,b是整數,則存在整數q,r,,使得a=bq+r,這叫作歐幾里德除法原理

    此時(a,b)=(b,r) 這叫作輾轉相除法原理

    證明

    假設(a,b)=d,(b,r)=d'

    因為(a,b)=d,則,由(1) ,亦即 ,由(2) ,亦即d

    又,因為(b,r)=d',則,由(1) ,亦即 ,由(2) ,亦即

    ,所以d=d',得證

    3.求最大公因數時,有兩種方法,一種是「短除法」,一種是「輾轉相除法」!

    A、短除法,將數字以橫寫方式,在畫一底線,在最左方數字旁,畫一垂直與底線的現段,再來在此線段的左方寫出可以「整除」要求的數字,要求得數字被除後的商,再繼續重複除!直到「無法再除」!而左方那些數字就是他們得公因數!全部乘起來就是最大公因數,任意乘就是公因數!

    B、輾轉相除法(注意,此法只能求最大公因數),將其中兩個數字兩旁「都劃上」往下得直線!所以有三條!以最小的數複製到最大數的下方,然後相減,減完的數再往小的地方去複製、相減!直到其中一數為「0」!而另一方的數則是最大公因數!

    輾轉相除是找出兩數是否互質的一種最常用的方法,是指有兩數 x 和y, 把它們大減小至無法減為止。若最後之數為 1, 則兩數互質;若最後之數為零, 兩數不互質。

    例:

    567, 2205

    567, 504 (2205 - 567 x 3 = 2205 - 1701)

    63 (567 - 504), 504

    63, 0 ( 504 - 63 x 8 = 504 - 504)

    so 567 and 2205 不互質, 均可被63 整除

    625, 882

    625, 257

    111, 257

    111, 35

    6, 35

    6, 5

    1, 5

    so 625 and 882 互質

    • Commenter avatarLogin to reply the answers
Still have questions? Get your answers by asking now.