Euclidean algorithm
First documented algorithm by Euclid (300 B.C.) to compute greatest common divisor (gcd). Examples: gcd(3,21) = 3; gcd(15,40) = 5.
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.