Skip to main content
Logo image

Integers and Modern Applications for the Uninitiated

Sebastian Pauli

Section 4.2 Greatest Common Divisors

In the video in Figure 4.2.1 we review the definition of divisibility. We also introduce greatest common divisors.
🔗
Figure 4.2.1. 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.
🔗

Definition 4.2.2.

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:
🔗
In the first example, we find the greatest common divisor of two integers by checking all divisors of both integers.
🔗

Example 4.2.4. 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.
🔗
So the greatest integer that divides both 12 and 42 is 6, that is, \(\gcd(12,42)=6\text{.}\)
🔗
🔗
We now give the greatest common divisor in some special cases.
🔗

Proof.

  1. We have \(\gcd(b,b)=b\text{,}\) because the largest natural number that divides \(b\) is \(b\text{.}\)
    🔗
    🔗
  2. By Definition 4.1.1 an integer \(a\) is divisible by a natural number \(b\) when there exists and integer \(q\) such that \(a=b\cdot q\text{.}\)
    🔗
    The integer \(0\) is divisible by all natural numbers \(b\text{,}\) because \(0=b \cdot 0\text{.}\) So the largest natural number that divides both \(0\) and \(b\) is \(b\text{.}\) Thus \(\gcd(0,b)=b\text{.}\)
    🔗
    🔗
  3. We have \(\gcd(1,a)=1\text{,}\) because the largest divisor of \(1\) is \(1\) and all natural numbers \(a\) are divisible by \(1\text{.}\)
    🔗
    🔗
🔗
🔗
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.2.6 tells us that we can use the remainder to help us find the greatest common divisor.
🔗

Proof.

In the proof of Item 1 and Item 2 we follow an approach similar to that of the proof of Theorem 4.1.4. We apply Item 1 and Item 2 in the proof of Item 3 and Item 3 to prove Item 4.
  1. 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{.}\)
    🔗
    🔗
  2. 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 \(t\) 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{.}\)
    🔗
    🔗
  3. 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{.}\)
    🔗
    🔗
  4. For \(q:=a \fdiv b\) 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*}
    🔗
    🔗
🔗
🔗
Now we repeatedly apply Theorem 4.2.6 Item 4 to find the greatest common divisor of two integers.
🔗

Example 4.2.7. 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.2.6 3. 4 we get
\begin{equation*} \gcd(51,15)=\gcd(51\fmod 15,15)=\gcd(6,15)\text{.} \end{equation*}
🔗
By Theorem 4.2.3 we have
\begin{equation*} \gcd(6,15)=\gcd(15,6)\text{.} \end{equation*}
🔗
Applying Theorem 4.2.6 3. 4 we get
\begin{equation*} \gcd(15,6)=\gcd(15 \fmod 6,6)=\gcd(3,6)\text{.} \end{equation*}
🔗
By Theorem 4.2.3 we have
\begin{equation*} \gcd(3,6)=\gcd(6,3)\text{.} \end{equation*}
🔗
With Theorem 4.2.6 3. 4 we get
\begin{equation*} \gcd(6,3)=\gcd(6\fmod 3,3)=\gcd(0,3)\text{.} \end{equation*}
🔗
By Theorem 4.2.5
\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\)
🔗
🔗
🔗
PrevTopNext