Euclidean algorithm
Walk through the algorithm with examples: A = 40, B =15.
A = 2B + 10 ? A = 15 ; B = 10
A = 1B + 5 ? A = 10 ; B = 5
A = 2B + 0 ? A = 5 ; B = 0
1. Let A and B be integers with A > B ? 0.
2. If B = 0, then the gcd is A and the algorithm ends.
3. Otherwise, find q and r such that
A = qB + r where 0 ? r < B
Note that we have 0 ? r < B < A and gcd(A,B) = gcd(B,r).
Replace A by B, B by r. Go to step 2.