Difference between revisions of "Euclidean algorithm"

Revision as of 20:46, 8 May 2022

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_1$
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$ .

Problems

Introductory

https://artofproblemsolving.com/community/c1677139h2442945p20256095

Intermediate

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

@@ Line 19: / Line 19: @@
 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_1</math><br> is the same as<math>a \equiv {r} \pmod{b}</math>.
+~The congruence sign above should be replaced by the normal equal sign. It's important to note that <math>a \pmod{b} = r_1</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:

Page

Toolbox

Search