The Euclidean algorithm (also known as the Euclidean division algorithm or Euclid's algorithm) is an algorithm that finds the greatest common divisor (GCD) of two elements of a Euclidean domain, the most common of which is the nonnegative integers , without factoring them.
Main idea and Informal Description
The basic idea is to repeatedly use the fact that
If we have two non-negative integers with and , then the greatest common divisor is . If , then the set of common divisors of and is the same as the set of common divisors of and where is the remainder of division of by . Indeed, we have with some integer , so, if divides both and , it must divide both and and, thereby, their difference . Similarly, if divides both and , it should divide as well. Thus, the greatest common divisors of and and of and coincide: . But the pair consists of smaller numbers than the pair ! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes
Start with any two elements and of a Euclidean Domain
- If , then .
- Otherwise take the remainder when is divided by , and find .
- Repeat this until the remainder is 0.
Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:
To see how it works, just take an example. Say .
We have , so .
Similarly, , so .
Continuing, , so .
Then , so .
Extended Euclidean Algorithm
An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write , where are some elements from the same Euclidean Domain as and that can be determined using the algorithm. We can work backwards from whichever step is the most convenient.
Continuing the previous example, our goal is to find and such that We can work backwards from equation since appears there:
We currently have as a linear combination of and . Our goal is to replace and so that we have a linear combination of and only. We start by rearranging to so we can substitute to express as a linear combination of and :
Continuing, we rearrange to substitute :
We have found one linear combination. To find others, since , dividing both sides by gives . We can add times this equation to , so we can write as a linear combination of and
for any integer .
- 1985 AIME Problems/Problem 13
- 1959 IMO Problems/Problem 1 (Note: this problem is widely regarded as the easiest problem ever asked in the IMO)