• Active Topics 

The Euclidean Algorithm

Post Reply
User avatar
Eli
Senior Expert Member
Reactions: 183
Posts: 5214
Joined: 9 years ago
Location: Tanzania
Has thanked: 75 times
Been thanked: 88 times
Contact:

#1

The Euclidean Algorithm uses the Division Algorithm repeatedly to find the greatest common divisor (gcd) of two numbers.

Division Algorithm states that

For any two integers $a$ and $b$ with $b>0$, there exist unique integers $q$ (the quotient) and $r$ (the reminder) such that $a = bq + r$, $0\le r<b$.

The Euclidean Algorithm

This algorithm asserts that, If $a = bq + r$, then $(a, b) = (b, r)$. Thus given $a, \ b >0$, the Euclidean Algorithm goes as follows:

$a = bq_1 + r_1, \ 0\le r_1 < b$

$b = r_1q_2 + r_2, \ 0\le r_2 < r_1$

$r_1 = r_2q_3 + r_3, \ 0\le r_3 < r_2$

$\vdots$

$r_n = r_{n+1}q_{n+2} + r_{n+2}, \ 0\le r_{n+2} < r_{n+1}$

Then we have $r_1 > r_2 > r_3 \ \dots \ > r_{n+1} > r_{n+2} = 0$ and thus

$\text{gcd}(a,b) = \text{gcd}(b, r_1) = \dots = r_{n+1}$


Example: Find $(2171, \ 2613)$

$2613 = 1.2171 + 442$
$2171 = 4.442 + 403$
$442 = 1.403 + 39$
$403 = 10.39 + 13$
$39 = 3.13 + 0$

Then $(2171, 2613) = (2171, 442) = (442, 403) = (403, 39) = (39, 13) = 13$

See Python implementation here.

Furthermore, from $(a, \ b) = d$, $d$ can always be written as a linear combination of $a$ and $b$, i.e.,
$d = ma + nb,$ where $m, \ n \in \mathbb{Z}$.

So,

\begin{align}\nonumber
\begin{split}
13 & = 403 - 10(39) \\
& = 403 - 10(442-403) \\
& = 11(2171 - (4)(442)) - 10(2613-2171) \\
& = 11(2171 - (4)(2613-2171)) - 10(2613 -2171) \\
& = 65(2171) - 54(2613)
\end{split}
\end{align}

Note that, this linear combination is not unique.

Warm up your brain:

Write a code, preferably in C++, Java or Python to implement $d = ma + nb$, where d is a gcd of arbitrary $a$ and $b$, such that $m, \ n \in \mathbb{Z}$.
0
TSSFL -- A Creative Journey Towards Infinite Possibilities!
Post Reply

Return to “Abstract Algebra”

  • Information
  • Who is online

    Users browsing this forum: No registered users and 0 guests