The traditional Euclidean algorithm

Given two integers a and b, not both zero, their greatest common divisor (or highest common factor)is the largest integer that divides both a and b, and is denoted gcd(a,b). Another way to define it is as the only positive integer d that divides both a and b and is divisible by any other divisor of both a and b.

If you have the prime factorization of both numbers then the gcd can be found by taking the prime factors that appear in both numbers raised to the minimum of the two exponents; however, finding the prime factorization of large numbers is costly.

By the Quotient-Remainder Theorem it is possible to divide a by b obtaining a quotient and a remainder , with

We can do the same with b and ,

Next, we divide by getting

We keep on dividing the next to last remainder by the last remainder, obtaining new quotients and remainders. Since each new remainder is nonnegative and strictly smaller than the previous one we will reach a remainder of zero in a finite number of steps. When that happens we stop.

Each remainder (including the last non-zero remainder) divides its predecessor and it also divides a and b; to see this, observe the last equation, substitute in the previous one and work your way up until you get expressions for a and  b in terms of . Also, from the previous equations we can see that if a number divides both a and b, then it will divide all the remainders including the last non-zero remainder. Thus, this remainder is the greatest common divisor. Since at each step the divisor becomes the dividend and the dividend is the remainder of the division we can write the algorithm recursively as follows:

The remainders are monotonically decreasing at a fast rate. Namely, we claim that <. To see this, first observe that if ≤, then immediately we have <≤. So suppose that >. In that case the next division gives: =1×+, and =-<, just as we claimed.
Every two steps the remainder's size is reduced by a factor of at least , and since the last nonzero remainder never gets below 1, there are at most 2⌊a⌋ divisions. Each division operates on numbers no larger than a, so each takes O(a)bit operations. Therefore, since the number of divisions is also O(log a) the complexity bound is O(a). If the decreasing size of the remainders is taken into account this bound may be improved to O(a).

Created by Mathematica  (June 3, 2006)