# Difference between revisions of "Euclidean algorithm"

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

## Main idea and informal description

If we have two non-negative integers $a,b$ with $a\ge b$ and $b=0$, then the greatest common divisor is $\displaystyle{a}$. If $a\ge b>0$, then the set of common divisors of $\displaystyle{a}$ and $b$ is the same as the set of common divisors of $b$ and $r$ where $r$ is the remainder of division of $\displaystyle{a}$ by $b$. Indeed, we have $a=mb+r$ with some integer $m$, so, if $\displaystyle{d}$ divides both $\displaystyle{a}$ and $b$, it must divide both $\displaystyle{a}$ and $mb$ and, thereby, their difference $r$. Similarly, if $\displaystyle{d}$ divides both $b$ and $r$, it should divide $\displaystyle{a}$ as well. Thus, the greatest common divisors of $\displaystyle{a}$ and $b$ and of $b$ and $r$ coincide: $GCD(a,b)=GCD(b,r)$. But the pair $(b,r)$ consists of smaller numbers than the pair $(a,b)$! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes $0$

## Steps

Start with two nonnegative integers, ${a}$ and $b$.

• If $b=0$, then $\gcd(a,b)=a$.
• Otherwise take the remainder when ${a}$ is divided by $b$ ( ${a}\pmod {b}$), and find $\gcd(b,a\pmod {b})$.

Repeat this until $b=0$.

## Simple Example

To see how it works, just take an example. Say $\displaystyle a=112,b=42$. We have $112\equiv 28\pmod {42}$, so $\displaystyle{\gcd(112,42)}=\displaystyle\gcd(42,28)$. Similarly, $42\equiv 14\pmod {42}$, so $\displaystyle\gcd(42,28)=\displaystyle\gcd(28,14)$. Then $28\equiv {0}\pmod {14}$, so $\gcd(28,14)}=\gcd(14,0)} = 14$. Thus $\displaystyle\gcd(112,42)=14$.

Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:

• $112 = 2 \cdot 42 + 28 \qquad (1)}$
• $42 = 1\cdot 28+14\qquad (2)$
• $28 = 2\cdot 14+0\qquad (3)$

## Linear Representation

An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write $\gcd(a,b)=ax+by$, where $x,y$ are some integer constants that can be determined using the algorithm.

In the example, we can rewrite equation $(2)$ from above as $14 = 42-1\cdot 28$ $14 = 42-1\cdot (112-2\cdot 42)$ $14 = 3\cdot 42-1\cdot 112.$