# Difference between revisions of "Euclidean algorithm"

(restored a part of the older version, kept the new organization intact) |
m (Removed duplicate "remainder" inner link) |
||

Line 10: | Line 10: | ||

* If <math>b=0</math>, then <math>\gcd(a,b)=a</math>. | * If <math>b=0</math>, then <math>\gcd(a,b)=a</math>. | ||

− | * Otherwise take the | + | * Otherwise take the remainder when <math>{a}</math> is divided by <math>b</math> (<math>{a}\pmod {b}</math>), and find <math>\gcd(b,a\pmod {b})</math>. |

Repeat this until <math>b=0</math>. | Repeat this until <math>b=0</math>. |

## Revision as of 22:39, 22 June 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