What is the Greatest Common Divisor of 963 &, 657 : 2689 & 4001 using Euclidean Algorithm?

Question

I don't just want the answers.... I need the formula that goes with the answers! Thanks

Answer 1

gcd (a, b) = gcd (b, a mod b), where a mod b indicates the remainder after a is divided by b. Repeatedly iterate this formula until you get gcd (x, 0), for some x, at which point you know the gcd is x. Here's the intermediate numbers for 963 & 657.

963
657
306
45
36
9
0

so gcd (963, 657) is 9. Repeating for 4001 and 2689:

4001
2689
1312
65
12
5
2
1
0

so gcd (2689, 4001) = 1