GCDs and The Euclidean Algorithm

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)\)

Video / Answer.

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)\)

Video / Answer.

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.

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{.}\)

Video / Answer.

Proposition 3.3.9. Bézout’s Lemma.

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.

Video / Answer.

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.

Video / Answer.

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\)

Discrete Math for Shockers

Search Results:

Section 3.3 GCDs and The Euclidean Algorithm

Subsection

Definition 3.3.1. Greatest Common Divisor (gcd).

Example 3.3.2.

Definition 3.3.3. Least Common Multiple.

Example 3.3.4.

Theorem 3.3.5.

Theorem 3.3.6. The Euclidean Algorithm.

Example 3.3.7.

Example 3.3.8.

Proposition 3.3.9. Bézout’s Lemma.

Definition 3.3.10. Bézout Coefficients.

Example 3.3.11. Back Substitution.

Example 3.3.12.

Example 3.3.13.

Exercises Exercises

1.

2.

3.

4.