Euclidean Algorithm

The Euclidean algorithm is a method for finding the greatest common factor (or greatest common divisor or GCD) between two integers using the division algorithm ("long division".) In particular, when the greatest common factor is one, the integers are relatively prime. [Note that the GCD may also be found using a prime factorization of each of the numbers.]

Here's how it works. Recall the the division algorithm states that for two integers n and m (assume nm we may write m = nq + r, where q is called the quotient and r is called the remainder and satisfies the condition 0 r < n . The Euclidean algorithm states: to find the greatest common factor between n and m, divide m by n. If the remainder is zero, then m is a multiple of n and we are done, the least common multiple being n. If not, divide the divisor (n) by the remainder. Continue this process, dividing the last divisor by the last remainder, until the remainder is zero. The last non-zero remainder is then the greatest common factor of the integers m and n. The algorithm is illustrated by the following example.