promotion image of download ymail app
Promoted
Lam 發問於 科學及數學數學 · 5 年前

find a combination of n and m

1007n+1703m=1

that n and m are integers

2 個解答

評分
  • Andrew
    Lv 6
    5 年前
    最愛解答

    The two integers are co-prime - which means we can use the Extended Euclidean Algorithm.

    By running the algorithm, we can see that

    1007 x 115 + 1703 x (-68) = 1

    So n = 115, m = -68.

    2015-03-20 23:31:31 補充:

    The Euclidean Algorithm is quite simple. It is basically,

    Assuming a > b, then GCD(a, b) = GCD(a % b, b)

    They will eventually divides, and that's the answer.

    Two examples:

    GCD(3, 7) = GCD(7, 3) = GCD(1, 3) = GCD(3, 1)

    GCD(48, 36) = GCD(12, 36) = GCD(36, 12) = 12.

    2015-03-20 23:35:41 補充:

    With that, the extended version keep tracks of the coefficients.

    Suppose we know gcd(a % b, b), m'(a%b) + n'(b), then

    gcd(a, b) = gcd(a%b, b) = m'(a - kb) + n'b = m'a + (n'-m'k)b

    For example, gcd(1, 3) = 1, 0 x 3 + 1 x 1 = 1

    Then gcd(7,3) = gcd(1,3), 0 x 3 + (7 - 3 x 2) x 1 = 1, 7 - 3 x 2 = 1.

    2015-03-24 00:49:39 補充:

    Thanks for your comments

    資料來源: Extended Euclidean Algorithm Calculator
    • Commenter avatar登入以回覆解答
  • 5 年前

    Details:

    Using Euclidean Algorithm

    1703=1×1007+696…(a)

    1007=1×696+311…(b)

    696=2×311+74…(c)

    311=4×74+15…(d)

    74=4×15+14…(e)

    15=1×14+1 or 15-14=1

    Using (e):15-(74-4×15)=1

    ⇒5×15-74=1

    Using (d):5×(311-4×74)-74=1

    ⇒5×311-21×74=1

    Using (c): 5×311-21×(696-2×311)=1

    ⇒47×311-21×696=1

    2015-03-21 12:13:49 補充:

    Using (b): 47×(1007-696)-21×696=1

    ⇒47×1007-68×696=1

    Using (a): 47×1007-68×(1703-1007)=1

    ⇒115×1007-68×1703=1

    Hence m=-68 and n=115

    • Commenter avatar登入以回覆解答
還有問題嗎?立即提問即可得到解答。