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}$.
-
- Active Topics
-
-
- by Eli 2 hours ago Re: What is in Your Mind? View the latest post Replies 700 Views 293013
- by Eli 2 days ago Russia Invades Ukraine View the latest post Replies 661 Views 228664
- by Eli 3 days ago President Museveni's Speech During International Development Association (IDA) Summit View the latest post Replies 1 Views 96
- by Eli 3 days ago From Simple Linear Regression Analysis to Covariance & Correlation to Independent Determinant, and R-Squared View the latest post Replies 11 Views 24465
- by Eli 3 days ago All in One: YouTube, TED, X, Facebook and Instagram Reels, Videos, Images and Text Posts View the latest post Replies 323 Views 27612
- by Eli 6 days ago Collection of Greatest Christian Hymns of all Times View the latest post Replies 34 Views 61272
- by Eli 1 week ago Pondering Big Cosmology Questions Through Lectures and Dialogues View the latest post Replies 34 Views 57707
- by Eli 1 week ago Programmatically Manipulate Files: Renaming, Reading, Writing, Deleting, and Moving Files Between Folders View the latest post Replies 7 Views 10162
- by Eli 1 week ago Iran Launches Retaliatory Attack Against Israel, and Israel Retaliates by Attacking Iranian Isfahan Millitary Base View the latest post Replies 28 Views 9960
- by Eli 2 weeks ago Python Packages for Scientific Computing View the latest post Replies 8 Views 16302
-
The Euclidean Algorithm
-
- Information
-
Who is online
Users browsing this forum: No registered users and 0 guests