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 補充：

資料來源： Extended Euclidean Algorithm Calculator
• 登入以回覆解答
• 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

• 登入以回覆解答