Find integers x, y so that 963x + 657y = GCD(963,657).

x y g r s t q
1 0 963 0 1 657 1
0 1 657 1 -1 306 2
1 -1 306 -2 3 45 6
-2 3 45 13 -19 36 1
13 -19 36 -15 22 9 4
-15 22 9 ? ? 0 -

So 963(-15) + 657(22) = 9 = GCD(963,637).

---------------------------------------------------------------------------

An example of the Chinese Remainder Theorem.

Solve the three simultaneous congruences:

x == 5 (mod 7)
x == 7 (mod 11)
x == 3 (mod 13)

Solution: In the statement and proof of the theorem we have a1 = 5, a2 = 7, a3 = 3, n1 = 7, n2 = 11, n3 = 13, n = 7*11*13 = 1001. Now GCD(n2*n3, n1) = GCD(11*13, 7) = 1; the extended Euclidean algorithm produces (n2*n3)*(-2) + n1*41 = 1, so be may take b1 = -2. Similarly, (n1*n3)*4 + n2*(-33) = 1, so we may take b2 = 4. Also (n1*n2)*(-1) + n3*6 = 1, so we may take b3 = -1. Then

x0 = n2*n3*b1*a1 + n1*n3*b2*a2 + n1*n2*b3*a3
= 11*13*(-2)*5 + 7*13*4*7 + 7*11*(-1)*3 = 887

is a solution, so the complete solution is x == x0 (mod n) or x == 887 (mod 1001).