# Difference between revisions of "Euclidean algorithm"

m (Removed duplicate "remainder" inner link) |
(Added an example problem) |
||

Line 37: | Line 37: | ||

* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=1985&p=453677 AIME 1985/13] | * [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=1985&p=453677 AIME 1985/13] | ||

+ | |||

+ | * [[1959 IMO Problems/Problem 1]] |

## Revision as of 18:31, 26 July 2006

The **Euclidean algorithm** allows us to find the greatest common divisor of any two nonnegative integers.

## Contents

## 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