Euclidean algorithm
The Euclidean algorithm allows us to find the greatest common divisor of any two nonnegative integers.
Contents
[hide]Main idea and informal description
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
Steps
Start with two nonnegative integers, and .
- If , then .
- Otherwise take the remainder when is divided by (), and find .
Repeat this until .
Simple Example
To see how it works, just take an example. Say . We have , so . Similarly, , so . Then , so . Thus .
Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:
Linear Representation
An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write , where are some integer constants that can be determined using the algorithm.
In the example, we can rewrite equation from above as