find a combination of n and m

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

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