Difference between revisions of "Euclidean algorithm"

m (Simple Example)
(Transferred content from "Euclidean Division Algorithm")
Line 1: Line 1:
The '''Euclidean algorithm''' allows us to find the [[greatest common divisor]] of any two [[nonnegative]] [[integer]]s.
+
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 is ℤ<sup>+</sup>[0], the set of non-negative integers) without factoring them.
 +
 
 
==Main idea and informal description==
 
==Main idea and informal description==
  
 +
The basic idea is that <math>\gcd({a,b}) \equiv \gcd({a,a - b})</math>
 +
 +
The following applies to ℤ<sup>+</sup>[0]<br>
 
If we have two non-negative integers <math>a,b</math> with <math>a\ge b</math> and <math>b=0</math>, then the greatest common divisor is <math>\displaystyle{a}</math>. If <math>a\ge b>0</math>, then the set of common divisors of <math>\displaystyle{a}</math> and <math>b</math> is the same as the set of common divisors of <math>b</math> and <math>r</math> where <math>r</math> is the [[remainder]] of division of <math>\displaystyle{a}</math> by <math>b</math>. Indeed, we have <math>a=mb+r</math> with some integer<math>m</math>, so, if <math>\displaystyle{d}</math> divides both <math>\displaystyle{a}</math> and <math>b</math>, it must divide both <math>\displaystyle{a}</math> and <math>mb</math> and, thereby, their difference <math>r</math>. Similarly, if <math>\displaystyle{d}</math> divides both <math>b</math> and <math>r</math>, it should divide <math>\displaystyle{a}</math> as well. Thus, the greatest common divisors of <math>\displaystyle{a}</math> and <math>b</math> and of <math>b</math> and <math>r</math> coincide: <math>GCD(a,b)=GCD(b,r)</math>. But the pair <math>(b,r)</math> consists of smaller numbers than the pair <math>(a,b)</math>! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes <math>0</math>
 
If we have two non-negative integers <math>a,b</math> with <math>a\ge b</math> and <math>b=0</math>, then the greatest common divisor is <math>\displaystyle{a}</math>. If <math>a\ge b>0</math>, then the set of common divisors of <math>\displaystyle{a}</math> and <math>b</math> is the same as the set of common divisors of <math>b</math> and <math>r</math> where <math>r</math> is the [[remainder]] of division of <math>\displaystyle{a}</math> by <math>b</math>. Indeed, we have <math>a=mb+r</math> with some integer<math>m</math>, so, if <math>\displaystyle{d}</math> divides both <math>\displaystyle{a}</math> and <math>b</math>, it must divide both <math>\displaystyle{a}</math> and <math>mb</math> and, thereby, their difference <math>r</math>. Similarly, if <math>\displaystyle{d}</math> divides both <math>b</math> and <math>r</math>, it should divide <math>\displaystyle{a}</math> as well. Thus, the greatest common divisors of <math>\displaystyle{a}</math> and <math>b</math> and of <math>b</math> and <math>r</math> coincide: <math>GCD(a,b)=GCD(b,r)</math>. But the pair <math>(b,r)</math> consists of smaller numbers than the pair <math>(a,b)</math>! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes <math>0</math>
  
  
== Steps ==
+
== General Form ==
  
Start with two nonnegative integers, <math>{a}</math> and <math>b</math>.
+
Start with any two elements <math>a</math> and <math>b</math> of a [[Euclidean Domain]]
  
 
* If <math>b=0</math>, then <math>\gcd(a,b)=a</math>.
 
* If <math>b=0</math>, then <math>\gcd(a,b)=a</math>.
* Otherwise take the remainder when <math>{a}</math> is divided by <math>b</math> (<math>{a}\pmod {b}</math>), and find <math>\gcd(b,a\pmod {b})</math>.
+
* Otherwise take the remainder when <math>{a}</math> is divided by <math>a (\bmod {b})</math>, and find <math>\gcd(a,a \bmod {b})</math>.
 +
* Repeat this until the remainder is 0.<br>
 +
 
 +
<math>a (\bmod b) \equiv r_1</math><br>
 +
<math>b (\bmod r_1) \equiv r_2</math><br>
 +
<math> \vdots</math> <br>
 +
<math>r_{n-1} (\bmod r_n) \equiv 0</math><br>
 +
Then <math>\gcd({a,b}) = r_n</math><br>
 +
 
 +
 
 +
Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:
 +
 
 +
for <math>r_{k+1} < r_k < r_{k-1}</math><br>
 +
<math>a = b \cdot q_1+r_1</math><br>
 +
<math>b = r_1 \cdot q_2 + r_2</math><br>
 +
<math>r_1 = r_2 \cdot q_3 + r_3</math><br>
 +
<math>\vdots</math><br>
 +
<math>r_{n-1} = r_n \cdot q_{n+2} +0</math><br>
 +
and so <math>\gcd({a,b}) = r_n</math><br>
  
Repeat this until <math>b=0</math>.
 
  
 
== Simple Example ==
 
== Simple Example ==
  
 
To see how it works, just take an example. Say <math>\displaystyle a=112,b=42</math>. We have <math>112\equiv 28\pmod {42}</math>, so <math>\displaystyle{\gcd(112,42)}=\displaystyle\gcd(42,28)</math>. Similarly, <math>42\equiv 14\pmod {28}</math>, so <math>\displaystyle\gcd(42,28)=\displaystyle\gcd(28,14)</math>. Then <math>28\equiv {0}\pmod {14}</math>, so <math>{\displaystyle \gcd(28,14)}={\displaystyle \gcd(14,0)} = 14</math>. Thus <math>\displaystyle\gcd(112,42)=14</math>.
 
To see how it works, just take an example. Say <math>\displaystyle a=112,b=42</math>. We have <math>112\equiv 28\pmod {42}</math>, so <math>\displaystyle{\gcd(112,42)}=\displaystyle\gcd(42,28)</math>. Similarly, <math>42\equiv 14\pmod {28}</math>, so <math>\displaystyle\gcd(42,28)=\displaystyle\gcd(28,14)</math>. Then <math>28\equiv {0}\pmod {14}</math>, so <math>{\displaystyle \gcd(28,14)}={\displaystyle \gcd(14,0)} = 14</math>. Thus <math>\displaystyle\gcd(112,42)=14</math>.
 
Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:
 
  
 
* <math>{\displaystyle 112 = 2 \cdot 42 + 28 \qquad (1)}</math>
 
* <math>{\displaystyle 112 = 2 \cdot 42 + 28 \qquad (1)}</math>
Line 26: Line 45:
 
== Linear Representation ==
 
== 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 integer constants that can be determined using the algorithm.
+
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 example, we can rewrite equation <math>(2)</math> from above as
+
In the previous example, we can work backwards from equation <math>(2)</math> from above as
  
 
<math>14 = 42-1\cdot 28</math><br>
 
<math>14 = 42-1\cdot 28</math><br>

Revision as of 13:00, 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 is ℤ+[0], the set of non-negative integers) without factoring them.

Main idea and informal description

The basic idea is that $\gcd({a,b}) \equiv \gcd({a,a - b})$

The following applies to ℤ+[0]
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$.

  • ${\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 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)$ from above as

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

Examples