Skip to main content
Contents
Search Book
Search Results:
No results.
Read aloud Readability settings Prev Up Next \(\def\ds{\displaystyle}
\def\d{\displaystyle}
\def\N{\mathbb N}
\def\B{\mathbf{B}}
\def\Z{\mathbb Z}
\def\Q{\mathbb Q}
\def\R{\mathbb R}
\def\C{\mathbb C}
\def\F{\mathbb F}
\def\pow{\mathcal P}
\def\inv{^{-1}}
\def\iff{\leftrightarrow}
\def\Iff{\Leftrightarrow}
\def\land{\wedge}
\def\And{\bigwedge}
\def\entry{\entry}
\def\AAnd{\d\bigwedge\mkern-18mu\bigwedge}
\def\Vee{\bigvee}
\def\VVee{\d\Vee\mkern-18mu\Vee}
\def\imp{\rightarrow}
\def\Imp{\Rightarrow}
\def\Fi{\Leftarrow}
\def\var{\mbox{var}}
\def\Th{\mbox{Th}}
\def\entry{\entry}
\def\sat{\mbox{Sat}}
\def\con{\mbox{Con}}
\def\iffmodels{\bmodels\models}
\def\dbland{\bigwedge \!\!\bigwedge}
\def\dom{\mbox{dom}}
\def\rng{\mbox{range}}
\def\isom{\cong}
\def\st{\mid}
\def\divides{\mid}
\def\and{\text{ and }}
\def\lcm{\text{lcm}}
\def\modulus{\mathbin{\%}}
\newcommand{\vtx}[2]{node[fill,circle,inner sep=0pt, minimum size=4pt,label=#1:#2]{}}
\newcommand{\va}[1]{\vtx{above}{#1}}
\newcommand{\vb}[1]{\vtx{below}{#1}}
\newcommand{\vr}[1]{\vtx{right}{#1}}
\newcommand{\vl}[1]{\vtx{left}{#1}}
\renewcommand{\v}{\vtx{above}{}}
\def\circleA{(-.5,0) circle (1)}
\def\circleAlabel{(-1.5,.6) node[above]{$A$}}
\def\circleB{(.5,0) circle (1)}
\def\circleBlabel{(1.5,.6) node[above]{$B$}}
\def\circleC{(0,-1) circle (1)}
\def\circleClabel{(.5,-2) node[right]{$C$}}
\def\twosetbox{(-2,-1.4) rectangle (2,1.4)}
\def\threesetbox{(-2.5,-2.4) rectangle (2.5,1.4)}
\def\ansfilename{practice-answers}
\def\shadowprops{{fill=black!50,shadow xshift=0.5ex,shadow yshift=0.5ex,path fading={circle with fuzzy edge 10 percent}}}
\newcommand{\hexbox}[3]{
\def\x{-cos{30}*\r*#1+cos{30}*#2*\r*2}
\def\y{-\r*#1-sin{30}*\r*#1}
\draw (\x,\y) node{#3};
}
\renewcommand{\bar}{\overline}
\newcommand{\card}[1]{\left| #1 \right|}
\newcommand{\twoline}[2]{\begin{pmatrix}#1 \\ #2 \end{pmatrix}}
\newcommand{\fixspacing}{\vspace{0pt plus 1filll}\mbox{}}
\usepackage{cancel}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 3.3 GCDs and The Euclidean Algorithm
In this section we explore what factors that pairs of numbers can have in common. It will turn out that numbers that have only 1 as a common divisor are especially useful to encryption methods, so we give an algorithm to find the greatest common divisor and how to write it in a particularly helpful way.
Subsection
Definition 3.3.1 . Greatest Common Divisor (gcd).
Let
\(a \and b\) be integers, not both zero. The largest integer
\(d\) such that
\(d\divides a\) and
\(d \divides b\) is called the
greatest common divisor of \(a \and b\) which we denote by
\(\gcd(a,b)\text{.}\)
We say
\(a \and b\) are
relatively prime if
\(\gcd(a,b)=1\text{.}\)
Example 3.3.2 .
Find the following (by listing prime factors):
\(\displaystyle \gcd(36, 69)\)
\(\displaystyle \gcd(10, 27)\)
\(\displaystyle \gcd(360, 1000)\)
Definition 3.3.3 . Least Common Multiple.
Let
\(a \and b\) be integers, not both zero. The smallest integer
\(m\) such that
\(a\divides m\) and
\(b \divides m\) is called the
least common multiple of \(a \and b\) which we denote by
\(\lcm(a,b)\text{.}\)
Example 3.3.4 .
Find the following:
\(\displaystyle \lcm(36, 69)\)
\(\displaystyle \lcm(10, 27)\)
\(\displaystyle \lcm(360, 1000)\)
Theorem 3.3.5 .
Let \(a \and b\) be two positive integers. Then
\begin{equation*}
ab = \gcd(a,b) \cdot \text{lcm}(a,b)
\end{equation*}
This essentially shows that the greatest common divisor and least common multiple are opposites of eachother in a particular way. If you know the greatest common divisor of
\(a \and b\text{,}\) you can find the least common multiple by simply:
\(\frac{ab}{\gcd(a,b)}\text{.}\)
The greatest common divisor is the more useful of the two, so we’ll now give an algorithm that lets us find it without having to factor the number first.
Theorem 3.3.6 . The Euclidean Algorithm.
Aside: 2300+ years old.
This is called the Euclidean Algorithm after Euclid of Alexandria because it was included in the book(s) of
The Elements he wrote in around 300BCE. We don’t know much about Euclid, but
The Elements influenced all future Greek, Arab, and Western mathematics.
Let \(a\) and \(b\) be two positive integers where \(a \ge b\text{.}\) If we apply the division algorithm recursively so that
\begin{gather*}
a = bq_1 + r_1 \text{ where } 0 \le r_1 \lt b\\
b = r_1q_2 + r_2 \text{ where } 0 \le r_2 \lt r_1\\
r_1 = r_2q_3 + r_3 \text{ where } 0 \le r_3 \lt r_2\\
r_2 = r_3q_4 + r_4 \text{ where } 0 \le r_4 \lt r_3\\
\dots \\
r_{n-2} = r_{n-1}q_{n-1} + r_n \text{ where } 0 \le r_n \lt r_{n-1}\\
r_{n-1} = r_{n}q_{n} + 0
\end{gather*}
Then \(\gcd(a,b) = r_n\text{,}\) the last non-zero remainder.
Example 3.3.7 .
Here’s a fully worked out example showing how to run the algorithm to find
\(\gcd(7592, 5913)\)
Solution .
\begin{align*}
7592 &= 5913 \cdot 1 + 1679\\
5913 &= 1679 \cdot 3 + 876\\
1679 &= 876 \cdot 1 + 803 \\
876 &= 803 \cdot 1 + 73 \\
803 &= 73 \cdot 11 + 0
\end{align*}
According to the Euclidean Algorithm, the last non-zero remainder is the gcd, and so \(\gcd(7592, 5913) = 73\text{.}\)
Example 3.3.8 .
Find
\(\gcd(5040, 4704)\text{.}\)
Proposition 3.3.9 . Bézout’s Lemma.
Aside: 300 years old.
This one is much less old; discovered by Étienne Bézout in the 18th century (1700’s).
If
\(a \and b\) are positive integers, then there exist integers
\(s \and t\) such that
\({\gcd(a,b) = as + bt}\)
Definition 3.3.10 . Bézout Coefficients.
We call
\(s \and t\) in the theorem above the
Bézout coefficients of
\(a \and b\text{.}\)
Example 3.3.11 . Back Substitution.
We can reverse the Euclidean Algorithm to find the Bézout coefficients, a process that we’ll call
back substitution . We solve each equation in the Euclidean Algorithm for the remainder, and repeatedly substitute and combine like terms until we arrive at the gcd written as a
linear combination of the original two numbers, in this case,
\(73 = 7592s + 5913t\)
Solution .
The remainders:
\begin{align*}
73 &= 876 - 803 \cdot 1\\
803 &= 1679 - 876 \cdot 1 \\
876 &= 5913 - 1679 \cdot 3 \\
1679 &= 7592 - 5913 \cdot 1
\end{align*}
Substitution and combining like terms:
\begin{align*}
73 &= 876 - 803 \cdot 1\\
&= 876 - (1679 - 876 \cdot 1) \cdot 1\\
&= 876\cdot 2 - 1679 \cdot 1\\
&= (5913 - 1679\cdot 3) \cdot 2 - 1679 \cdot 1\\
&= 5913\cdot 2 - 1679 \cdot 7\\
&= 5913\cdot 2 - (7592 - 5913 \cdot 1) \cdot 7\\
&= 5913\cdot 9 - 7592 \cdot 7\\
&= 5913\cdot 9 + 7592 \cdot (-7)
\end{align*}
So
\(73 = 5913 \cdot 9 + 7592 \cdot(-7)\) is the linear combination we desired.
Example 3.3.12 .
Express the gcd of 168 and 525 as a linear combination of those numbers.
Example 3.3.13 .
Use the Euclidean algorithm to find \(\gcd(4147, 10672)\text{.}\)
Use back-substitution (reverse the steps of the Euclidean Algorithm) to write the greatest common divisor of 4147 and 10672 as a linear combination of those numbers.
Exercises Exercises
1.
Find the gcd via the Euclidean Algorithm and then use back-substitution to write the gcd as a linear combination of those numbers:
\(\displaystyle \gcd(36, 48) \)
\(\displaystyle \gcd(21, 724) \)
\(\displaystyle \gcd(60, 97) \)
\(\displaystyle \gcd(5, 26) \)
Solution .
\(12=36(-1)+48(\) 1)
\(1=21(69)+724(\) -2)
\(1=60(-21)+97(\) 13)
\(\displaystyle 1=5(-5)+26(1)\)
2. Use any method to find the greatest common divisor of 412 and 32.
Solution .
\(\gcd(412, 32) = 4\text{.}\) We can right it as the linear combination:
\(4=412(-1) + 32(13)\)
3. Use any method to find the greatest common divisor of 780 and 150.
Solution .
\(\gcd(780, 150) = 30\text{.}\) We can right the gcd as the linear combination
\(30=780(1) + 150(-5)\)
4. Find the greatest common divisor of 70, 98, 108.
Hint .
Try looking at each pair of numbers separately.
Solution .
\(\gcd(70, 98, 108) = 2\)
