彤彤 發問時間: 教育與參考其他:教育 · 1 0 年前

有關數論公因數公倍數求解的問題

我在做評量的時候寫了這堤 可是他只付答案...所以我不知怎算ㄉ...請告訴我過程!!

已知a和b屬於N且滿足

a=b‧2+1540

b=1540‧3+616

找一組整數(m,n)=?

使得ma+nb=(a,b)

1 個解答

評分
  • 1 0 年前
    最佳解答

    ★輾轉相除法原理:a,b,q,r皆為整數,其中a,b不等於0

    若a=bq+r,則(a,b)=(b,r)

    [解法]

    (1)先求(a,b):

    根據輾轉相除法原理,

    a=b*2+1540 => (a,b) = (b,1540)

    b=1540*3+616 => (b,1540) = (1540,616)

    另外,

    1540=616*2+308 => (1540,616) = (616,308)

    616=308*2 => (616,308)=308

    ∴(a,b) = 308

    (2)從(a,b)逆推,求一組(m,n):

    (a,b) = 308

       = 1540 - 616*2

       = 1540 - (b-1540*3)*2 = 7*1540 - 2b

       = 7*(a-2b) - 2b = 7a -16b

    即 7a-16b=(a,b)

    故(m,n)=(7,16)為其中一組整數解

還有問題?馬上發問,尋求解答。