The Extended Euclidean Algorithm

Try this!! You will definitely find it interesting.
Consider two integers m and n. Find two integers a and b such that m*a + n*b = gcd(m,n)

Example 1: m = 65; n = 40

Step 1: The (usual) Euclidean algorithm:
(1) 65 = 1*40 + 25
(2) 40 = 1*25 + 15
(3) 25 = 1*15 + 10
(4) 15 = 1*10 + 5
     10 = 2*5  + 0    (Do this until remainder = 0)
Therefore: gcd(65; 40) = 5.

Step 2: Using the method of back-substitution:
5 (4) = 15 - 10
   (3) = 15 - (25 - 15) = 2*15 - 25
   (2) = 2(40 - 25) - 25 = 2*40 - 3*25
   (1) = 2*40 - 3(65 - 40) = 5*40 - 3*65

Conclusion: 65(-3) + 40(5) = 5.



Example 2: m = 1239; n = 735
Step 1: The (usual) Euclidean algorithm:
(1) 1239 = 1*735 + 504
(2)  735  = 1*504 + 231
(3)  504  = 2*231 + 42
(4)   23   = 5*42 + 21
       42   = 2*21 + 0
Therefore: gcd(1239; 735) = 21.

Step 2: Using the method of back-substitution:
21 (4) = 231 - 5*42
     (3) = 231 - 5(504 - 2*231) = 11*231 - 5*504
     (2) = 11(735 - 504) - 5*504 = 11*735 - 16*504
     (1) = 11*735 - 16(1239 - 735) = 27*735 - 16*1239

Conclusion: 1239(-16) + 735(27) = 21.