Difference between revisions of "Euclidean algorithm"
m (→Simple Example) |
(→Problems) |
||
(56 intermediate revisions by 27 users not shown) | |||
Line 1: | Line 1: | ||
− | The '''Euclidean algorithm''' | + | 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. |
− | |||
− | + | ==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> | ||
+ | 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>. | |
+ | * 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> | ||
− | = | + | 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> | ||
− | + | 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> | |
− | + | <math>3 = (14k + 5) \cdot 93 + (-31k - 11) \cdot 42</math> | |
− | |||
− | |||
− | + | for any integer <math>k</math>. | |
− | + | == Problems == | |
+ | yoooo wassuppp | ||
− | + | ===Introductory=== | |
+ | https://artofproblemsolving.com/community/c1677139h2442945p20256095 | ||
− | + | ===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]] | ||
− | == | + | ===Olympiad=== |
− | + | ==See Also== | |
+ | *[[Divisibility]] | ||
− | + | [[Category:Algorithms]] | |
+ | [[Category:Number theory]] |
Latest revision as of 10:00, 18 July 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 , without factoring them.
Contents
Main idea and Informal Description
The basic idea is to repeatedly use the fact that
If we have two non-negative integers with
and
, then the greatest common divisor is
. If
, then the set of common divisors of
and
is the same as the set of common divisors of
and
where
is the remainder of division of
by
. Indeed, we have
with some integer
, so, if
divides both
and
, it must divide both
and
and, thereby, their difference
. Similarly, if
divides both
and
, it should divide
as well. Thus, the greatest common divisors of
and
and of
and
coincide:
. But the pair
consists of smaller numbers than the pair
! So, we reduced our task to a simpler one. And we can do this reduction again and again until the smaller number becomes
.
General Form
Start with any two elements and
of a Euclidean Domain
- If
, then
.
- Otherwise take the remainder when
is divided by
, and find
.
- Repeat this until the remainder is 0.
Then
~The congruence sign above should be replaced by the normal equal sign. It's important to note that
is the same as .
Usually the Euclidean algorithm is written down just as a chain of divisions with remainder:
for
and so
Example
To see how it works, just take an example. Say .
We have , so
.
Similarly, , so
.
Continuing, , so
.
Then , so
.
Thus .
Extended Euclidean Algorithm
An added bonus of the Euclidean algorithm is the "linear representation" of the greatest common divisor. This allows us to write , where
are some elements from the same Euclidean Domain as
and
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 and
such that
We can work backwards from equation
since
appears there:
We currently have as a linear combination of
and
. Our goal is to replace
and
so that we have a linear combination of
and
only. We start by rearranging
to
so we can substitute
to express
as a linear combination of
and
:
Continuing, we rearrange to substitute
:
We have found one linear combination. To find others, since , dividing both sides by
gives
. We can add
times this equation to
, so we can write
as a linear combination of
and
for any integer .
Problems
yoooo wassuppp
Introductory
https://artofproblemsolving.com/community/c1677139h2442945p20256095
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