Euclidean algorithm

Revision as of 11:35, 20 June 2006 by Fedja (talk | contribs) (restored a part of the older version, kept the new organization intact)

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 ${\displaystyle \gcd(28,14)}={\displaystyle \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:

  • ${\displaystyle 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.$

Examples