Difference between revisions of "Euclidean algorithm"

m (Simple Example)
(Example)
Line 30: Line 30:
  
 
==  Example ==
 
==  Example ==
To see how it works, just take an example. Say <math>a=112,b=42</math>. <br />
+
To see how it works, just take an example. Say <math>a = 93, b = 42</math>. <br />
We have <math>112\equiv 28\pmod {42}</math>, so <math>{\gcd(112,42)}=\gcd(42,28)</math>. <br />  
+
We have <math>93 \equiv 9 \pmod{42}</math>, so <math>\gcd(93,42) = \gcd(42,9)</math>. <br />  
Similarly, <math>42\equiv 14\pmod {28}</math>, so <math>\gcd(42,28)=\gcd(28,14)</math>.  
+
Similarly, <math>42 \equiv 6 \pmod{9}</math>, so <math>\gcd(42,9) = \gcd(9,6)</math>. <br />
<br />Then <math>28\equiv {0}\pmod {14}</math>, so <math>{\gcd(28,14)}={\gcd(14,0)} = 14</math>. <br />
+
Continuing, <math>9 \equiv 3 \pmod{6}</math>, so <math>\gcd(9,6) = \gcd(6,3)</math>.
Thus <math>\gcd(112,42)=14</math>.
+
Then <math>6 \equiv 0 \pmod{3}</math>, so <math>\gcd(6,3) = \gcd(3,0) = 3</math>. <br />
 +
Thus <math>\gcd(93,42) = 3</math>.
  
* <math>{112 = 2 \cdot 42 + 28 \qquad (1)}</math>
+
* <math>93 = 2 \cdot 42 + 9 \qquad (1)</math>
* <math>42 = 1\cdot 28+14\qquad (2)</math>
+
* <math>42 = 4 \cdot 9 + 6 \qquad (2)</math>
* <math>28 = 2\cdot 14+0\qquad (3)</math>
+
* <math>9 = 1 \cdot 6 + 3 \qquad (3)</math>
 +
* <math>6 = 2 \cdot 3 + 0 \qquad (4)</math>
  
 
== Linear Representation ==
 
== Linear Representation ==

Revision as of 13:25, 26 September 2015

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({b,a - b})$

If we have two non-negative integers $a,b$ with $a\ge b$ and $b=0$, then the greatest common divisor is ${a}$. If $a\ge b>0$, then the set of common divisors of ${a}$ and $b$ is the same as the set of common divisors of $b$ and $r$ where $r$ is the remainder of division of ${a}$ by $b$. Indeed, we have $a=mb+r$ with some integer $m$, so, if ${d}$ divides both ${a}$ and $b$, it must divide both ${a}$ and $mb$ and, thereby, their difference $r$. Similarly, if ${d}$ divides both $b$ and $r$, it should divide ${a}$ as well. Thus, the greatest common divisors of ${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 \pmod{b}$, and find $\gcd(a,a \bmod {b})$.
  • Repeat this until the remainder is 0.

$a \pmod{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$

Example

To see how it works, just take an example. Say $a = 93, b = 42$.
We have $93 \equiv 9 \pmod{42}$, so $\gcd(93,42) = \gcd(42,9)$.
Similarly, $42 \equiv 6 \pmod{9}$, so $\gcd(42,9) = \gcd(9,6)$.
Continuing, $9 \equiv 3 \pmod{6}$, so $\gcd(9,6) = \gcd(6,3)$. Then $6 \equiv 0 \pmod{3}$, so $\gcd(6,3) = \gcd(3,0) = 3$.
Thus $\gcd(93,42) = 3$.

  • $93 = 2 \cdot 42 + 9 \qquad (1)$
  • $42 = 4 \cdot 9 + 6 \qquad (2)$
  • $9 = 1 \cdot 6 + 3 \qquad (3)$
  • $6 = 2 \cdot 3 + 0 \qquad (4)$

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.$

Problems

Introductory

Intermediate

Olympiad

See Also