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

Euclidean algorithm

Revision as of 13:24, 19 June 2006 by Chess64 (talk | contribs) (reorganized)

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"