4.6: Euclidean Algorithm
- Page ID
- 163885
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)The Euclidean Algorithm: An Ancient Method for Finding the Greatest Common Factor
Another way to calculate the Greatest Common Factor (GCF) is the Euclidean Algorithm. It is an efficient method, especially for larger numbers. The algorithm is based on a simple yet powerful principle: the GCF of two numbers is the same as the GCF of the smaller number and the remainder of the larger number divided by the smaller number.
This elegant method has a rich history that stretches back over two millennia. The algorithm is named after the ancient Greek mathematician Euclid, who first described it in his seminal work "Elements" around 300 BCE. This makes the Euclidean Algorithm one of the oldest numerical algorithms still in use today, a testament to the enduring power of mathematical thinking across the ages.
Euclid of Alexandria, often referred to as the "Father of Geometry," was a mathematician who lived in Egypt during the reign of Ptolemy I. While little is known about his life, his works have had a profound impact on mathematics. "Elements," his most famous treatise, is a comprehensive compilation of mathematical knowledge of his time, covering topics from plane geometry and number theory to irrational numbers.
The inclusion of the GCF algorithm in this ancient text highlights its fundamental importance in mathematics. The fact that we still use this algorithm today, over 2300 years later, in fields ranging from basic arithmetic to computer science and cryptography, showcases the timeless nature of mathematical discoveries.
As students apply this algorithm, they are not just solving a mathematical problem; they are participating in a tradition of logical thinking that spans civilizations and centuries. The Euclidean Algorithm serves as a beautiful example of how a simple idea, when properly formulated, can have incredible longevity and wide-ranging applications.
Steps of the Euclidean Algorithm:
- Divide the larger number by the smaller number.
- Take the remainder from step 1 and divide the smaller number by this remainder.
- Repeat step 2, each time dividing the previous divisor by the previous remainder.
- Continue this process until the remainder is zero.
- The last non-zero remainder is the GCF.
Find the \(GCF\) of 48 and 72 using the Euclidean Algorithm
Step 1: \(72 \div 48\)
\(72 = 1 * \mathbf{48} + \mathbf{24}\) <-- use 42 and 24 for Step 2
Quotient: 1, Remainder: 24
Step 2: \(48 \div 24\)
\(48 = 2 * \mathbf{24} + \mathbf{0}\) <-- stop since the remainder is 0
Quotient: 2, Remainder: 0
Since the remainder is now 0, we stop. The last non-zero remainder was 24. Therefore, \(GCF(48, 72) = 24\)
Let's try a more complex example to better illustrate the process.
Example: Find the \(GCF\) of 270 and 192
Step 1: \(270 ÷ 192\)
\(270 = 1 * \mathbf{192} + \mathbf{78}\) <-- use these numbers for Step 2
Quotient: 1, Remainder: 78
Step 2: \(192 ÷ 78\)
\(192 = 2 * \mathbf{78} + \mathbf{36}\) <-- use these numbers for Step 3
Quotient: 2, Remainder: 36
Step 3: \(78 ÷ 36\)
\(78 = 2 * \mathbf{36} + \mathbf{6}\) <-- use these numbers for Step 3
Quotient: 2, Remainder: 6
Step 4: \(36 ÷ 6\)
\(36 = 6 * \mathbf{6} + \mathbf{0}\) <-- stop since the remainder is 0
Quotient: 6, Remainder: 0
The process stops here as the remainder is 0. The last non-zero remainder was 6. Therefore, \(GCF(270, 192) = 6\).