Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Euclidean algorithm"

(→‎Example)
(→‎Linear Representation)
Line 30: Line 30:
  
 
==  Example ==
 
==  Example ==
−
To see how it works, just take an example. Say <math>a = 93, b = 42</math>. <br />
+
To see how it works, just take an example. Say <math>a=112,b=42</math>. <br />
−
We have <math>93 \equiv 9 \pmod{42}</math>, so <math>\gcd(93,42) = \gcd(42,9)</math>. <br />  
+
We have <math>112\equiv 28\pmod {42}</math>, so <math>{\gcd(112,42)}=\gcd(42,28)</math>. <br />  
−
Similarly, <math>42 \equiv 6 \pmod{9}</math>, so <math>\gcd(42,9) = \gcd(9,6)</math>. <br />
+
Similarly, <math>42\equiv 14\pmod {28}</math>, so <math>\gcd(42,28)=\gcd(28,14)</math>.  
−
Continuing, <math>9 \equiv 3 \pmod{6}</math>, so <math>\gcd(9,6) = \gcd(6,3)</math>.
+
<br />Then <math>28\equiv {0}\pmod {14}</math>, so <math>{\gcd(28,14)}={\gcd(14,0)} = 14</math>. <br />
−
Then <math>6 \equiv 0 \pmod{3}</math>, so <math>\gcd(6,3) = \gcd(3,0) = 3</math>. <br />
+
Thus <math>\gcd(112,42)=14</math>.
−
Thus <math>\gcd(93,42) = 3</math>.
 
  
−
* <math>93 = 2 \cdot 42 + 9 \qquad (1)</math>
+
* <math>{112 = 2 \cdot 42 + 28 \qquad (1)}</math>
−
* <math>42 = 4 \cdot 9 + 6 \qquad (2)</math>
+
* <math>42 = 1\cdot 28+14\qquad (2)</math>
−
* <math>9 = 1 \cdot 6 + 3 \qquad (3)</math>
+
* <math>28 = 2\cdot 14+0\qquad (3)</math>
−
* <math>6 = 2 \cdot 3 + 0 \qquad (4)</math>
 
  
−
== Linear Representation ==
+
== Extended Euclidean 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.
 
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>:
+
Continuing the previous example, our goal is to find <math>a</math> and <math>b</math> such that <math>93a + 42b = \gcd(93,42) = 3.</math>  We can work backwards from equation <math>(3)</math> since <math>3</math> appears there:
 +
<math>3 = 9 - 1 \cdot 6</math>
 +
We currently have <math>3</math> as a linear combination of <math>6</math> and <math>9</math>.  Rearranging <math>(2)</math> to <math>6 = 42 - 4 \cdot 9</math>, we can substitute <math>6</math> to express <math>3</math> as a linear combination of <math>9</math> and <math>42</math>:
  
−
<math>14 = 42-1\cdot 28</math><br>
+
<math>3 = 9 - 1 \cdot (42 - 4 \cdot 9)</math> <br>
−
<math>14 = 42-1\cdot (112-2\cdot 42)</math><br>
+
<math>3 = -1 \cdot 42 + 5 \cdot 9.</math> <br>
−
<math>14 = 3\cdot 42-1\cdot 112.</math><br>
+
 
 +
Continuing, we rearrange <math>(1)</math> to substitute <math>9 = 93 - 2 \cdot 42</math>:
 +
 
 +
<math>3 = -1 \cdot 42 + 5 \cdot (93 - 2 \cdot 42)</math> <br>
 +
<math>3 = -11 \cdot 42 + 5 \cdot 93. \qquad (5)</math> <br>
 +
 
 +
Furthermore, since <math>42 \cdot 93 - 93 \cdot 42 = 0</math>, dividing both sides by <math>\gcd(93,42) = 3</math> gives <math>14 \cdot 93 - 31 \cdot 42 = 0</math>.  We can add <math>k</math> times this equation to <math>(5)</math>, so we can write <math>3</math> as a linear combination of <math>93</math> and <math>42</math>
 +
 
 +
<math>3 = (14k + 5) \cdot 93 + (-31k - 11) \cdot 42</math>
 +
 
 +
for any integer <math>k</math>.
  
 
== Problems ==
 
== Problems ==

Revision as of 14:48, 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=112,b=42$.
We have $112\equiv 28\pmod {42}$, so ${\gcd(112,42)}=\gcd(42,28)$.
Similarly, $42\equiv 14\pmod {28}$, so $\gcd(42,28)=\gcd(28,14)$.
Then $28\equiv {0}\pmod {14}$, so ${\gcd(28,14)}={\gcd(14,0)} = 14$.
Thus $\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)$

Extended Euclidean Algorithm

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.

Continuing the previous example, our goal is to find $a$ and $b$ such that $93a + 42b = \gcd(93,42) = 3.$ We can work backwards from equation $(3)$ since $3$ appears there: $3 = 9 - 1 \cdot 6$ We currently have $3$ as a linear combination of $6$ and $9$. Rearranging $(2)$ to $6 = 42 - 4 \cdot 9$, we can substitute $6$ to express $3$ as a linear combination of $9$ and $42$:

$3 = 9 - 1 \cdot (42 - 4 \cdot 9)$
$3 = -1 \cdot 42 + 5 \cdot 9.$

Continuing, we rearrange $(1)$ to substitute $9 = 93 - 2 \cdot 42$:

$3 = -1 \cdot 42 + 5 \cdot (93 - 2 \cdot 42)$
$3 = -11 \cdot 42 + 5 \cdot 93. \qquad (5)$

Furthermore, since $42 \cdot 93 - 93 \cdot 42 = 0$, dividing both sides by $\gcd(93,42) = 3$ gives $14 \cdot 93 - 31 \cdot 42 = 0$. We can add $k$ times this equation to $(5)$, so we can write $3$ as a linear combination of $93$ and $42$

$3 = (14k + 5) \cdot 93 + (-31k - 11) \cdot 42$

for any integer $k$.

Problems

Introductory

Intermediate

Olympiad

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Euclidean_algorithm&oldid=72188"