Difference between revisions of "Euclidean algorithm"

Revision as of 13:34, 20 February 2007

The Euclidean algorithm (also known as the Euclidean division algorithm or Euclid's algorithm) is an algorithm that finds the greatest common divisor (GCD) of two elements of a Euclidean domain, the most common of which is the nonnegative integers $\mathbb{Z}_{\geq 0}$ , without factoring them.

Main idea and informal description

The basic idea is to repeatedly use the fact that $\gcd({a,b}) \equiv \gcd({a,a - b})$

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$

General Form

Start with any two elements $a$ and $b$ of a Euclidean Domain

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

$a (\bmod b) \equiv r_1$
$b (\bmod r_1) \equiv r_2$
$\vdots$
$r_{n-1} (\bmod r_n) \equiv 0$
Then $\gcd({a,b}) = r_n$

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

for $r_{k+1} < r_k < r_{k-1}$
$a = b \cdot q_1+r_1$
$b = r_1 \cdot q_2 + r_2$
$r_1 = r_2 \cdot q_3 + r_3$
$\vdots$
$r_{n-1} = r_n \cdot q_{n+2} +0$
and so $\gcd({a,b}) = r_n$

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 {28}$ , 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$ .

$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 elements from the same Euclidean Domain as $a$ and $b$ that can be determined using the algorithm. We can work backwards from whichever step is the most convenient.

In the previous example, we can work backwards from equation $(2)$ :

$14 = 42-1\cdot 28$
$14 = 42-1\cdot (112-2\cdot 42)$
$14 = 3\cdot 42-1\cdot 112.$

Examples

AIME 1985/13

1959 IMO Problems/Problem 1

@@ Line 44: / Line 44: @@
 == Linear Representation ==
-An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write <math>\gcd(a,b)=ax+by</math>, where <math>x,y</math> are some elements from the same [[Euclidean Domain]] as <math>a</math> and <math>b</math> that can be determined using the algorithm. We can work backwards from whichever step is the most convenient
+An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write <math>\gcd(a,b)=ax+by</math>, where <math>x,y</math> are some elements from the same [[Euclidean Domain]] as <math>a</math> and <math>b</math> that can be determined using the algorithm. We can work backwards from whichever step is the most convenient.
-In the previous example, we can work backwards from equation <math>(2)</math> from above as
+In the previous example, we can work backwards from equation <math>(2)</math>:
 <math>14 = 42-1\cdot 28</math><br>

Page

Toolbox

Search