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"

m (proofreading)
(reorganized)
Line 1: Line 1:
−
The Euclidean algorithm allows to find the [[greatest common divisor]] of any two non-negative integers. The main idea is very simple: 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>. 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. We can do this reduction again and again until the smaller number becomes <math>0</math>.  
+
The '''Euclidean algorithm''' allows us to find the [[greatest common divisor]] of any two [[nonnegative]] [[integer]]s.
−
<br>
+
 
−
To see how it works, just take an example <math>\displaystyle a=112</math>, <math>b=42</math>. We have <math>112=2\cdot 42+ 28</math>, so the pair <math>(112,42)</math> can be replaced by <math>(42,28)</math>. Similarly, <math>42=1\cdot 28+14</math>, so we get the pair <math>(28,14)</math>. Now, <math>28=2\cdot 14+0</math>, so we get the pair <math>(14,0)</math>, which has the greatest common divisor <math>14</math>. Thus <math>GCD(112,42)=14</math>.
+
== Steps ==
−
Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:
+
 
−
<br>
+
Start with two nonnegative integers, <math>{a}</math> and <math>b</math>.
−
<math>112=2\cdot 42+ 28</math>
+
 
−
<br>
+
* If <math>b=0</math>, then <math>\gcd(a,b)=a</math>.
−
<math>42=1\cdot 28+14</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>.
−
<br>
+
 
−
<math>28=2\cdot 14+0</math>
+
Repeat this until <math>b=0</math>.
−
<br>
+
 
−
The Euclidean algorithm has one nice bonus: the so called linear representation of the greatest common divisor. To see how it works, let's use our equations backwards starting with the last one:
+
== Simple Example ==
−
<br>
+
 
−
<math>14=42-1\cdot 28=42-1\cdot(112-2\cdot 42)=3\cdot 42-1\cdot 112</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 {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>.
−
<br>
+
 
−
i.e., <math>14</math> is expressed as a sum of <math>112</math> and  <math>42</math> with integer coefficients.
+
Usually the Euclidean algorithm is written down just as a chain of divisions:
−
<br>
+
 
−
How fast is the Euclidean algorithm? One can prove that if the larger of two numbers does not exceed the <math>n</math>-th [[Fibonacci number]], then the required number of steps does not exceed <math>n</math>, so the number of steps is logarithmic in the size of the initial numbers (i.e., the number of steps is not much more than the number of digits in the largest of the two numbers).
+
* <math>{\displaystyle 112 = 2 \cdot 42 + 28 \qquad (1)}</math>
−
===Practice Problems===
+
* <math>42 = 1\cdot 28+14\qquad (2)</math>
−
*'''AIME 1985 #13''' Let <math>f(n)</math> be the greatest common divisor of <math>100 + n^{2}</math> and <math>100 + (n+1)^{2}</math> for <math>n = 1, 2, 3, \ldots</math> . What is the maximum value of <math>f(n)</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.
 +
 
 +
In the example, we can rewrite equation <math>(2)</math> from above as
 +
 
 +
<math>14 = 42-1\cdot 28</math><br>
 +
<math>14 = 42-1\cdot (112-2\cdot 42)</math><br>
 +
<math>14 = 3\cdot 42-1\cdot 112.</math><br>
 +
 
 +
== Examples ==
 +
 
 +
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=1985&p=453677 AIME 1985/13]

Revision as of 14:24, 19 June 2006

The Euclidean algorithm allows us to find the greatest common divisor of any two nonnegative integers.

Steps

Start with two nonnegative integers, ${a}$ and $b$.

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

Repeat this until $b=0$.

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

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

  • ${\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 constants to be determined.

In the example, we can rewrite 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

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