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{.}\)
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.
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.
Theorem 4.10.
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(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.
-
\(\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{.}\)
-
\begin{equation*} \gcd(a\fmod b,b) = \gcd(a-(b\cdot q),b) = \gcd(a,b)\text{.} \end{equation*}
Example 4.15. Compute \(\gcd(51,15)\) using \(\gcd(a,b) = \gcd(a\fmod b,b)\).
\begin{equation*}
\gcd(51,15)=\gcd(51\fmod 15,15)=\gcd(6,15)\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*}
With Theorem 4.14 3. 4 we get
\begin{equation*}
\gcd(6,3)=\gcd(6\fmod 3,3)=\gcd(0,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\)
