Greatest Common Divisors

Section 4.2 Greatest Common Divisors

In the video in Figure 4.8 we recall the definition of divisibility and give an introduction to greatest common divisors.

Figure 4.8. Greatest Common Divisors by Matt Farmer and Stephen Steward

The definition of the greatest common divisor of two integers is intuitive. To make it unique, we require it to be positive, that is, we require the greatest common divisor to be a natural number.

Definition 4.9.

Let \(a\) and \(b\) be integers. The greatest natural number \(g\) that divides both \(a\) and \(b\) is called the greatest common divisor of \(a\) and \(b\) and is denoted by \(\gcd(a,b)\text{.}\)

We say \(a\) and \(b\) are coprime if \(\gcd(a,b) = 1\text{.}\)

In the definition the order of \(a\) and \(b\) does not matter. We have:

Theorem 4.10.

Let \(a\) and \(b\) be integers. Then \(\gcd(a,b)=\gcd(b,a)\text{.}\)

In our first example we find a greatest common divisor of two integers by checking all divisors of both numbers.

Example 4.11. Greatest common divisor of \(12\) and \(42\).

We find the greatest common divisor of \(12\) and \(42\text{.}\) As all divisors of 12 are less than or equal to 12, we only have to check numbers less than 12.

1 divides both 12 and 42
2 divides both 12 and 42
3 divides both 12 and 42
4 divides 12 but not 42
5 does not divide 12 or 42
6 divides both 12 and 42
7 does not divide 12, but does divide 42
8 does not divide 12 or 42
9 does not divide 12 or 42
10 does not divide 12 or 42
11 does not divide 12 or 42
12 divides 12 but not 42

Thus the greatest integer that divides both 12 and 42 is 6, that is, \(\gcd(12,42)=6\text{.}\)

We now consider some special cases, in which we can directly read of the greatest common divisor.

Example 4.12. Greatest common divisor special cases.

We give the greatest common divisor in some special cases. Let \(a\) be a natural number. Then

\(\gcd(a,a)=a\text{,}\) as the largest natural number that divides \(a\) is \(a\text{.}\)
\(\gcd(0,a)=a\text{,}\) as \(0\) is divisible by all natural numbers \(a\text{.}\)
\(\gcd(1,a)=1\text{,}\) as the largest divisor of \(1\) is \(1\) and all natural numbers \(a\) are divisible by \(1\text{.}\)

In Checkpoint 4.21 recognize the special cases considered above in order to find greatest common divisors/.

Checkpoint 4.13. Special cases of greatest common divisors.

For each of the following pairs of numbers, find the greatest common divisor. Although the numbers are large finding their greatest common divisor is not too hard. Taking a closer look at both numbers reveals special relationships.

gcd(950806,950806)=

gcd(4917140,1)=

gcd(2567541,0)=

gcd(0,4917140)=

gcd(571447,571447)=

gcd(1,2567541)=

gcd(4917141,4917141)=

Our next goal is to find an efficient method for finding greatest common divisors in general. Recall that remainder of division of \(a\) and \(b\) is \(a - (b\cdot q)\) where \(q := a \fdiv b\text{.}\) Theorem 4.14 tells us that we can use the remainder to help us find the greatest common divisor.

Theorem 4.14.

Let \(g\) be a natural number and let \(a\text{,}\) \(b\text{,}\) and \(q\) be integers.

If \(g\) divides \(a\) and \(g\) divides \(b\) then \(g\) also divides \(a-(b\cdot q)\text{.}\)
If \(g\) divides \(a-(b\cdot q)\) and \(g\) divides \(b\) then \(g\) also divides \(a\text{.}\)
\(\gcd(a-(b\cdot q),b)=\gcd(a,b)\text{.}\)
\(\gcd(a\fmod b,b)=\gcd(a,b)\text{.}\)

Proof.

In the proof of Item 1 and Item 2 we follow an approach similar to that of the proof of Theorem 4.6. We apply Item 1 and Item 2 in the proof of Item 3 and Item 3 to prove Item 4.

As \(g\) divides \(a\) there exists an integer \(s\) such that \(a=g\cdot s\) and as \(g\) divides \(b\) there exists an integer \(t\) such that \(b=g\cdot t\text{.}\) We now have

\begin{equation*} a-(b\cdot q)=(g\cdot s)-((g\cdot t) \cdot q)=g\cdot(s-(t\cdot q))\text{.} \end{equation*}

Thus \(a-(b\cdot q)\) is a multiple of \(g\) which means that \(g\) divides \(a-(b\cdot q)\text{.}\)
As \(g\) divides \(a-(b\cdot q)\) there exists an integer \(s\) such that \(a-(b\cdot q)=g\cdot s\) and as \(g\) divides \(b\text{,}\) there exists an integer \(s\) such that \(b=g\cdot t\text{.}\) We now have

\begin{equation*} a=(a-(b\cdot q))+ (b\cdot q)= (g\cdot s)+( (g\cdot t)\cdot q)=g\cdot(s+(t\cdot q)) \end{equation*}

Thus \(a\) is a multiple of \(g\) which means that \(g\) divides \(a\text{.}\)
By Item 1 all natural numbers \(g\) that divide \(a\) and \(b\) also divide \(a-(b\cdot q)\text{.}\) By Item 2 all natural numbers \(g\) that divide \(a-(b\cdot q)\) and \(b\) also divide \(a\text{.}\) Thus the common divisors of \(a\) and \(b\) and the common divisors of \(a-(b\cdot q)\) are the same. So, in particular, the greatest common divisor of \(a\) and \(b\) is equal to the greatest common divisor of \(a-(b\cdot q)\) and \(b\text{.}\)
For \(q:=a \fdiv q\) we have \(a \fmod b=a-(b\cdot q)\text{.}\) With Item 3 we get

\begin{equation*} \gcd(a\fmod b,b) = \gcd(a-(b\cdot q),b) = \gcd(a,b)\text{.} \end{equation*}

We now repeatedly apply Theorem 4.14 Item 4 to find the greatest common divisor of two integers.

Example 4.15. Compute \(\gcd(51,15)\) using \(\gcd(a,b) = \gcd(a\fmod b,b)\).

Let \(a:=51\) and \(b:= 15\text{.}\) We find \(\gcd(a,b)\text{.}\) With Theorem 4.14 3. 4 we get

\begin{equation*} \gcd(51,15)=\gcd(51\fmod 15,15)=\gcd(6,15)\text{.} \end{equation*}

By Theorem 4.10 we have

\begin{equation*} \gcd(6,15)=\gcd(15,6)\text{.} \end{equation*}

Applying Theorem 4.14 3. 4 we obtain

\begin{equation*} \gcd(15,6)=\gcd(15 \fmod 6,6)=\gcd(3,6)\text{.} \end{equation*}

By Theorem 4.10 we have

\begin{equation*} \gcd(3,6)=\gcd(6,3)\text{.} \end{equation*}

With Theorem 4.14 3. 4 we get

\begin{equation*} \gcd(6,3)=\gcd(6\fmod 3,3)=\gcd(0,3)\text{.} \end{equation*}

By Example 4.12

\begin{equation*} \gcd(0,3)=3\text{.} \end{equation*}

We summarize the steps above. We have found:

\begin{align*} \gcd(51,15) \amp =\gcd(51-(15\cdot 3),15) \\ \amp = \gcd(6,15)\\ \amp =\gcd(15,6)\\ \amp=\gcd(3,6)\\ \amp=\gcd(6,3)\\ \amp=\gcd(0,3)=3\text{.} \end{align*}

That is, \(\gcd(51,15)=3\)

Prev Top Next