# Euclidean algorithm

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