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"

(reorganized)
(→‎Problems)
 
(63 intermediate revisions by 34 users not shown)
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 of which is the [[nonnegative]] [[integer]]s <math>\mathbb{Z}{\geq 0}</math>, without [[factoring]] them.
  
−
== Steps ==
+
==Main idea and Informal Description==
 +
The basic idea is to repeatedly use the fact that <math>\gcd({a,b}) \equiv \gcd({b,a - b})</math>
  
−
Start with two nonnegative integers, <math>{a}</math> and <math>b</math>.
+
If we have two non-negative integers <math>a,b</math> with <math>a|b</math> and <math>b\ne0</math>, then the greatest common divisor is <math>{a}</math>. If <math>a\ge b>0</math>, then the set of common divisors of <math>{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>{a}</math> by <math>b</math>. Indeed, we have <math>a=mb+r</math> with some integer <math>m</math>, so, if <math>{d}</math> divides both <math>{a}</math> and <math>b</math>, it must divide both <math>{a}</math> and <math>mb</math> and, thereby, their difference <math>r</math>. Similarly, if <math>{d}</math> divides both <math>b</math> and <math>r</math>, it should divide <math>{a}</math> as well. Thus, the greatest common divisors of <math>{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>.
 +
 
 +
== General Form ==
 +
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 \pmod{b}</math>, and find <math>\gcd(a,a \bmod {b})</math>.
 +
* Repeat this until the remainder is 0.<br>
 +
 
 +
<math>a \pmod{b} \equiv r_1</math><br>
 +
<math>b \pmod {r_1} \equiv r_2</math><br>
 +
<math> \vdots</math> <br>
 +
<math>r_{n-1} \pmod {r_n} \equiv 0</math><br>
 +
Then <math>\gcd({a,b}) = r_n</math><br>
 +
 
 +
~The congruence sign above should be replaced by the normal equal sign. It's important to note that <math>a \pmod{b} = r</math><br>is the same as <math>a \equiv {r} \pmod{b}</math>.
 +
 
 +
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+1} +0</math><br>
 +
and so <math>\gcd({a,b}) = r_n</math><br>
 +
 
 +
==  Example ==
 +
To see how it works, just take an example. Say <math>a = 93, b=42</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 6 \pmod{9}</math>, so <math>\gcd(42,9) = \gcd(9,6)</math>. <br/>
 +
Continuing, <math>9 \equiv 3 \pmod{6}</math>, so <math>\gcd(9,6) = \gcd(6,3)</math>. <br/>
 +
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>93 = 2 \cdot 42 + 9 \qquad (1)</math>
 +
* <math>42 = 4 \cdot 9 + 6 \qquad (2)</math>
 +
* <math>9 = 1 \cdot 6 + 3 \qquad (3)</math>
 +
* <math>6 = 2 \cdot 3 + 0 \qquad (4)</math>
 +
 
 +
== 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.
 +
 
 +
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>.  Our goal is to replace <math>6</math> and <math>9</math> so that we have a linear combination of <math>42</math> and <math>93</math> only.  We start by rearranging <math>(2)</math> to <math>6 = 42 - 4 \cdot 9</math> so we can substitute <math>6</math> to express <math>3</math> as a linear combination of <math>9</math> and <math>42</math>:
 +
 
 +
<math>3 = 9 - 1 \cdot (42 - 4 \cdot 9)</math> <br>
 +
<math>3 = -1 \cdot 42 + 5 \cdot 9.</math> <br>
  
−
Repeat this until <math>b=0</math>.
+
Continuing, we rearrange <math>(1)</math> to substitute <math>9 = 93 - 2 \cdot 42</math>:
  
−
== Simple Example ==
+
<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>
  
−
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 {42}</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>.
+
We have found one linear combination.  To find others, 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>
  
−
Usually the Euclidean algorithm is written down just as a chain of divisions:
+
<math>3 = (14k + 5) \cdot 93 + (-31k - 11) \cdot 42</math>
  
−
* <math>{\displaystyle 112 = 2 \cdot 42 + 28 \qquad (1)}</math>
+
for any integer <math>k</math>.
−
* <math>42 = 1\cdot 28+14\qquad (2)</math>
 
−
* <math>28 = 2\cdot 14+0\qquad (3)</math>
 
  
−
== 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 constants to be determined.
+
===Introductory===
 +
https://artofproblemsolving.com/community/c1677139h2442945p20256095
  
−
In the example, we can rewrite equation <math>(2)</math> from above as
+
===Intermediate===
 +
* [[2020 AMC 10A Problems/Problem 24]]
 +
* [[1985 AIME Problems/Problem 13]]
 +
* [[1959 IMO Problems/Problem 1]] (Note: this problem is widely regarded as the easiest problem ever asked in the IMO)
 +
* [[2021 AIME I Problems/Problem 10]]
  
−
<math>14 = 42-1\cdot 28</math><br>
+
===Olympiad===
−
<math>14 = 42-1\cdot (112-2\cdot 42)</math><br>
 
−
<math>14 = 3\cdot 42-1\cdot 112.</math><br>
 
  
−
== Examples ==
+
==See Also==
 +
*[[Divisibility]]
  
−
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=1985&p=453677 AIME 1985/13]
+
[[Category:Algorithms]]
 +
[[Category:Number theory]]

Latest revision as of 16:39, 30 September 2024

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|b$ and $b\ne0$, 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 \pmod {r_1} \equiv r_2$
$\vdots$
$r_{n-1} \pmod {r_n} \equiv 0$
Then $\gcd({a,b}) = r_n$

~The congruence sign above should be replaced by the normal equal sign. It's important to note that $a \pmod{b} = r$
is the same as $a \equiv {r} \pmod{b}$.

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+1} +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)$

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$. Our goal is to replace $6$ and $9$ so that we have a linear combination of $42$ and $93$ only. We start by rearranging $(2)$ to $6 = 42 - 4 \cdot 9$ so 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)$

We have found one linear combination. To find others, 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$.


Introductory

https://artofproblemsolving.com/community/c1677139h2442945p20256095

Intermediate

Olympiad

See Also

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