5.4: Greatest Common Divisors

Last updated
Save as PDF

Page ID: 8410

$kwong.jpg$
Contributed by Harris Kwong
Professors (Mathematics) at State University of New York at Fredonia
Publisher: OpenSUNY

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$

Given any two integers $a$ and $b$, an integer $c\neq0$ is a common divisor or common factor of $a$ and $b$ if $c$ divides both $a$ and $b$. If, in addition, $a$ and $b$ are not both equal to zero, then the greatest common divisor, denoted by $\gcd(a,b)$, is defined as the largest common divisor of $a$ and $b$. Greatest common divisors are also called highest common factors. It should be clear that $\gcd(a,b)$ must be positive.

Example $\PageIndex{1}\label{eg:gcd-01}$

The common divisors of 24 and 42 are $\pm1$, $\pm2$, $\pm3$, and $\pm6$. Among them, 6 is the largest. Therefore, $\gcd(24,42)=6$. The common divisors of 12 and 32 are $\pm1$, $\pm2$ and $\pm4$, it follows that $\gcd(12,32)=4$.

hands-on exercise $\PageIndex{1}\label{he:gcd-01}$

Verify that \[\gcd(5,35)=5, \quad \gcd(-5,10)=5, \quad \gcd(20,-10)=10, \quad\mbox{and}\quad \gcd(20,70)=10. \nonumber\] Explain why $\gcd(3,5)=1$

Example $\PageIndex{2}\label{eg:gcd-02}$

Can you explain why $\gcd(0,3)=3$? How about $\gcd(0,-3)=3$?

Solution: Recall that 0 is divisible by any nonzero integer. Hence, all the divisors of 3 are also divisors of 0. Obviously, 3 itself is the largest divisor of 3. Therefore, $\gcd(0,3)=3$.

hands-on exercise $\PageIndex{2}\label{he:gcd-02}$

Explain why $\gcd(0,-8)=8$.

Theorem $\PageIndex{1}\label{thm:gcd0b}$

For any nonzero integer $b$, we have $\gcd(0,b)=|b|$.

Proof

The largest positive divisor of $b$ is $|b|$. Since $|b|$ also divides 0, we conclude that $\gcd(0,b)=|b|$.

Theorem 5.4.1 tells us that $\gcd(0,b)=|b|$ if $b$ is nonzero. From the definition of common divisor and greatest common divisor, it is clear that $\gcd(a,b) = \gcd(b,a)$, and $\gcd(a,b) = \gcd(\pm a,\pm b)$. So we may assume $1\leq a\leq b$.

Theorem $\PageIndex{2}$

Let $a$ and $b$ be integers such that $1\leq a\leq b$. If $b=aq+r$, where $0\leq r< a$, then $\gcd(b,a)=\gcd(a,r)$.

Proof

To facilitate our argument, let $d=\gcd(b,a)$ and $e=\gcd(a,r)$. By definition, $d$ is a divisor of both $b$ and $a$. Therefore, $b=dx$ and $a=dy$ for some integers $x$ and $y$. Then \[r = b-aq = dx-dy\cdot q = d(x-yq), \nonumber\] where $x-yq$ is an integer. Hence, $d\mid r$. This makes $d$ a common divisor of both $r$ and $a$. Since $e$ is the greatest common divisor of $a$ and $r$, we determine that $d\leq e$.

Similarly, $e=\gcd(a,r)$ is a divisor of both $a$ and $r$. Thus, $a=eu$ and $r=ev$ for some integers $u$ and $v$. Then \[b = aq+r = a\cdot eu+ev = e(au+v), \nonumber\] where $au+v$ is an integer. Hence, $e\mid b$. This makes $e$ a common divisor of both $b$ and $a$. Since $d$ is the greatest common divisor of $b$ and $a$, we deduce that $e\leq d$. Together with $d\leq e$, we conclude that $d=e$.

Example $\PageIndex{3}\label{eg:gcd-03}$

From $997=996\cdot1+1$, we obtain $\gcd(997,996)=\gcd(996,1)=1$.

The theorem assures that $\gcd(b,a) = \gcd(a,r)$. We can apply the theorem again to $\gcd(a,r)$. Dividing $a$ by $r$ produces a new quotient and a new remainder. If necessary, repeat the process until the remainder becomes zero. If we denote $b=r_0$ and $a=r_1$, then \[\begin{array}{rcl@{\qquad\qquad}l} r_0 &=& r_1 q_1 + r_2, & 0\leq r_2 < r_1, \\ r_1 &=& r_2 q_2 + r_3, & 0\leq r_3 < r_2, \\ r_2 &=& r_3 q_3 + r_4, & 0\leq r_4 < r_3, \\ \vdots & & \vdots \\ r_{k-1} &=& r_k q_k + r_{k+1}, & 0\leq r_{k+1} < r_k, \\ \vdots & & \vdots \\ r_{n-3} &=& r_{n-2} q_{n-2} + r_{n-1}, & 0\leq r_{n-1} < r_{n-2}, \\ r_{n-2} &=& r_{n-1} q_{n-1} + r_n, & r_n=0. \end{array} \nonumber\] It follows that \[\gcd(b,a) = \gcd(r_0,r_1) = \gcd(r_1,r_2) = \cdots = \gcd(r_{n-1},r_n) = \gcd(r_{n-1},0) = r_{n-1}. \nonumber\] The last nonzero remainder is $\gcd(a,b)$. This method for finding the greatest common divisor is called Euclidean algorithm.

Example $\PageIndex{4}\label{eg:gcd-04}$

Find $\gcd(426,246)$.

Solution: By applying the theorem repeatedly, we find \[\begin{array}{rcl@{\qquad\qquad}lcl} 426 &=& 246\cdot1+180, & \gcd(426,246) &=& \gcd(246,180) \\ 246 &=& 180\cdot1+ 66, & \gcd(246,180) &=& \gcd(180, 66) \\ 180 &=& 66\cdot2+ 48, & \gcd(180, 66) &=& \gcd( 66, 48) \\ 66 &=& 48\cdot1+ 18, & \gcd( 66, 48) &=& \gcd( 48, 18) \\ 48 &=& 18\cdot2+ 12, & \gcd( 48, 18) &=& \gcd( 18, 12) \\ 18 &=& 12\cdot1+ 6, & \gcd( 18, 12) &=& \gcd( 12, 6) \\ 12 &=& 6\cdot2+ 0, & \gcd( 12, 6) &=& \gcd( 6, 0) = 6. \end{array} \nonumber\] Therefore, $\gcd(426,246)=6$.

hands-on exercise $\PageIndex{3}\label{he:gcd-03}$

Determine $\gcd(732,153)$.

hands-on exercise $\PageIndex{4}\label{he:gcd-04}$

Determine $\gcd(6958,2478)$.

By hand, it is more efficient to use a two-column format. First, put the two numbers 426 and 246 in two separate columns, with the larger number on the left. Perform a short division, and write the quotient on the left: \[\begin{array}{r|r|r|r} 1 & 426 & 246 & \\ & 246 & & \\ \ \cline{2-2} & 180 & & \end{array} \nonumber\]

In the next round, perform another short division on the two numbers 246 and 180 at the bottom. Since the larger number is now on the right column, leave the quotient to its right:

\[\begin{array}[t]{r|r|r|r} 1 & 426 & 246 & 1 \\ & 246 & 180 & \\ \hline & 180 & 66 & \end{array} \nonumber\]

Continue in this manner until the remainder becomes 0. The last nonzero entry at the bottom is the greatest common divisor. We can also leave all the quotients on the left:

\[\begin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 \\ & 246 & 180 & \\ \hline 2 & 180 & 66 & 1 \\ & 132 & 48 & \\ \hline 2 & 48 & 18 & 1 \\ & 36 & 12 & \\ \hline 2 & 12 & 6 & \\ & 12 & & \\ \hline & 0 & \end{array} \hskip0.5in\mbox{or}\hskip0.5in \begin{array}[c]{r|r|r|r} 1 & 426 & 246 & \\ 1 & 246 & 180 & \\ \hline 2 & 180 & 66 & \\ 1 & 132 & 48 & \\ \hline 2 & 48 & 18 & \\ 1 & 36 & 12 & \\ \hline 2 & 12 & 6 & \\ & 12 & & \\ \hline & 0 & \end{array} \nonumber\]

hands-on exercise $\PageIndex{5}\label{he:gcd-05}$

Use the two-column format to compute $\gcd(153,732)$.

hands-on exercise $\PageIndex{6}\label{eg:gcd-06}$

Use the two-column format to compute $\gcd(6958,2478)$.

Given any integers $m$ and $n$, the numbers of the form $ms+nt$, where $s,t$ are integers, are called the linear combinations of $m$ and $n$. They play an important role in the study of $\gcd(m,n)$, as indicated in the next theorem.

Theorem $\PageIndex{3}$

For any nonzero integers $a$ and $b$, there exist integers $s$ and $t$ such that $\gcd(a,b)=as+bt$.

Proof: The proof of this theorem is lengthy and complicated. We leave it, along with other related results, many of which are rather technical, to the next section.

Theorem $\PageIndex{4}$

Every linear combination of $a$ and $b$ is a multiple of $\gcd(a,b)$.

Corollary $\PageIndex{5}$

The greatest common divisor of two nonzero integers $a$ and $b$ is the smallest positive integer among all their linear combinations.

It is important to understand what these three results say. Finding a linear combination of $a$ and $b$ only gives us a multiple of $\gcd(a,b)$. Only a special linear combination will produce the exact value of $\gcd(a,b)$.

Example $\PageIndex{5}\label{eg:gcd-05}$

Let $n$ and $n+1$ be two consecutive positive integers. Then \[n\cdot(-1)+(n+1)\cdot1 = 1 \nonumber\] implies that 1 is a multiple of the greatest common divisor of $n$ and $n+1$. This means the greatest common divisor must be 1. Therefore, $\gcd(n,n+1)=1$ for all integers $n$.

Definition

Two integers $a$ and $b$ are said to be relatively prime if $\gcd(a,b)=1$. Therefore, $a$ and $b$ are relatively prime if they have no common divisors except $\pm 1$.

Example $\PageIndex{6}\label{eg:gcd-06}$

Prove that if $\gcd(a,b)=1$, then $\gcd(a+b,a-b)$ equals to 1 or 2.

Solution: From the linear combinations \[\begin{aligned} (a+b)\cdot1+(a-b)\cdot1 &=& 2a, \\ (a+b)\cdot1+(a-b)\cdot(-1) &=& 2b, \end{aligned} \nonumber\] we know that $\gcd(a+b,a-b)$ divides both $2a$ and $2b$. Since $\gcd(a,b)=1$, we conclude that $\gcd(a+b,a-b)$ divides 2. Consequently, $\gcd(a+b,a-b)$ is either 1 or 2.

Example $\PageIndex{7}\label{eg:gcd-07}$

Show that if $\gcd(a,b)=1$, then $\gcd(2a+b,a+2b)$ equals to either 1 or 3.

Solution: From the linear combinations \[\begin{aligned} (2a+b)\cdot 2 +(a+2b)\cdot(-1) &=& 3a, \\ (2a+b)\cdot(-1)+(a+2b)\cdot 2 &=& 3b, \end{aligned} \nonumber\] we know that $\gcd(2a+b,a+2b)$ divides both $3a$ and $3b$. Since $\gcd(a,b)=1$, we conclude that $\gcd(2a+b,a+2b)$ divides 3. Thus, $\gcd(a+b,a-b)$ is 1 or 3.

hands-on exercise $\PageIndex{7}\label{he:gcd-07}$

What are the possible values of $\gcd(5m+7n,7m+5n)$ if the two positive integers $m$ and $n$ are relatively prime?

Example $\PageIndex{8}\label{eg:gcd-08}$

Find the integers $s$ and $t$ such that $6=\gcd(426,246)=246s+426t$.

Solution

Earlier, we studied how to find $\gcd(426,246)=6$. In each division, we want to express the remainder as a linear combination of 246 and 426. This is how the computation proceeds:

\[\begin{array}{lrcl} 426 = 246\cdot1+180,& 180 &=& 246\cdot(-1)+426\cdot1 \\ [3pt] 246 = 180\cdot1+66, & 66 &=& 246\cdot1+180\cdot(-1) \\ & &=& 246\cdot1+[246\cdot(-1)+426\cdot1]\cdot(-1) \\ & &=& 246\cdot2+426\cdot(-1) \\ [3pt] 180 = 66\cdot2+48, & 48 &=& 180\cdot1+66\cdot(-2) \\ & &=& [246\cdot(-1)+426\cdot1]\cdot1 +[246\cdot2+426\cdot(-1)]\cdot(-2) \\ & &=& 246(-5)+426\cdot3 \\ 66 = 48\cdot1+18, & 18 &=& 66\cdot1+48\cdot(-1) \\ & &=& [246\cdot2+426\cdot(-1)]\cdot1 + [246(-5)+426\cdot3]\cdot(-1) \\ & &=& 246\cdot7+426\cdot(-4) \\ [3pt] 48 = 18\cdot2+12, & 12 &=& 48\cdot1+18\cdot(-2) \\ & &=& [246(-5)+426\cdot3]\cdot1 + [246\cdot7+426\cdot(-4)]\cdot(-2) \\ & &=& 246\cdot(-19)+426\cdot11 \\ [3pt] 18 = 12\cdot1+6, & 6 &=& 18\cdot1 + 12\cdot(-1) \\ & &=& [246\cdot7+426\cdot(-4)]\cdot1 + [246\cdot(-19)+426\cdot11]\cdot(-1) \\ & &=& 246\cdot26+426\cdot(-15) \end{array} \nonumber\]

The answer is $6=246\cdot26+426\cdot(-15)$.

The computation is tedious! The extended Euclidean algorithm provides a relief. It keeps track of two sequences of integers $s_k$ and $t_k$ alongside with $r_k$, such that \[r_k = a s_k + b t_k. \nonumber\] This expresses every remainder as a linear combination of $a$ and $b$. Since the last nonzero remainder is $\gcd(a,b)$, the corresponding linear combination will be the answer we are looking for.

The values of $s_k$ and $t_k$ for the last example are summarized below:

\[\begin{array}{|c|r|r|r| } \hline k & r_k & s_k & t_k \\ \hline 2 & 180 & -1 & 1 \\ 3 & 60 & 2 & -1 \\ 4 & 48 & -5 & 3 \\ 5 & 18 & 7 & -4 \\ 6 & 12 & -19 & 11 \\ 7 & 6 & 26 & -15 \\ \hline \end{array} \nonumber\]

The main issue is: how can we compute these values efficiently?

The table above starts with $k=2$. How about $k=0$ and $k=1$? From \[b = r_0 = a s_0 + b t_0, \nonumber\] we determine that $s_0=0$ and $t_0=1$. Similarly,

\[a = r_1 = a s_1 + b t_1 \nonumber\]

implies that $s_1=1$ and $t_1=0$. Hence, the list of values of $s_k$ and $t_k$ start with the following:

\[\begin{array}{ccc} k & s_k & t_k \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{array} \nonumber\]

In general, before we carry out the division $r_{k-1}\div r_k$, we should have already generated $s_0$ through $s_k$, and $t_0$ through $t_k$. After the division, we obtain $q_k$ and $r_{k+1}$ as in

\[r_{k-1} = r_k q_k + r_{k+1}. \nonumber\]

Next, we compute $s_{k+1}$ and $t_{k+1}$ before moving on to the next division. We find

\[\begin{array}{rcl} r_{k+1} &=& r_{k-1} - r_k q_k \\ &=& (a s_{k-1} + bt_{k-1}) - (a s_k + b t_k) q_k \\ &=& a (s_{k-1} - s_k q_k) + b (t_{k-1} - t_k q_k). \end{array} \nonumber\]

Therefore, we need

\[\begin{array}{r c l} s_{k+1} &=& s_{k-1} - s_k q_k, \\ t_{k+1} &=& t_{k-1} - t_k q_k. \end{array} \nonumber\]

In words:

\[\displaylines{ \mbox{next $s$-value} = \mbox{previous-previous $s$-value} - \mbox{previous $s$-value}\times \mbox{corresponding $q$}, \cr \mbox{next $t$-value} = \mbox{previous-previous $t$-value} - \mbox{previous $t$-value}\times \mbox{corresponding $q$}. \cr} \nonumber\]

For example, assume at a certain stage, the values of $s$, $t$, and $q$ are as follow:

\[\begin{array}{ccc} k & s_k & t_k & q_k \\ 0 & 0 & 1 & \\ 1 & 1 & 0 & 1 \\ 2 & -1 & 1 & 1 \\ 3 & 2 & -1 & 2 \\ & & & 1 \\ & & & 2 \\ & & & 1 \\ & & & 2 \end{array} \nonumber\] Then \[\displaylines{ \mbox{next $s$-value} = -1-2\cdot2 = -5, \cr \mbox{next $t$-value} = 1-(-1)\cdot2 = 3. \cr} \nonumber\] Now the list becomes \[\begin{array}{ccc} k & s_k & t_k & q_k \\ 0 & 0 & 1 & \\ 1 & 1 & 0 & 1 \\ 2 & -1 & 1 & 1 \\ 3 & 2 & -1 & 2 \\ 4 & -5 & 3 & 1 \\ & & & 2 \\ & & & 1 \\ & & & 2 \end{array} \nonumber\]

The entire computation can be carried out in a modified two-column format.

Example $\PageIndex{9}\label{eg:gcd-09}$

Find integers $s$ and $t$ such that $\gcd(246,426)=246s+426t$.

Solution

First, copy the quotients from the right-most column and insert them between those quotients in the left-most column:

\[\begin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 \\ & 246 & 180 & \\ \cline{2-3} 2 & 180 & 66 & 1 \\ & 132 & 48 & \\ \cline{2-3} 2 & 48 & 18 & 1 \\ & 36 & 12 & \\ \cline{2-3} 2 & 12 & 6 & \\ & 12 & & \\ \cline{2-2} & 0 & \end{array} \qquad\mbox{becomes}\qquad \begin{array}[c]{r|r|r|r} 1 & 426 & 246 & 1 \\ 1 & 246 & 180 & \\ \cline{2-3} 2 & 180 & 66 & 1 \\ 1 & 132 & 48 & \\ \cline{2-3} 2 & 48 & 18 & 1 \\ 1 & 36 & 12 & \\ \cline{2-3} 2 & 12 & 6 & \\ & 12 & & \\ \cline{2-2} & 0 & \end{array} \nonumber\]

Next, compute $s_k$ and $t_k$ alongside these quotients (we do not need to record the values of $k$):

\[\begin{array}[t]{rr@{\qquad}r|r|r|r} s_k & t_k & \multicolumn{1}{r}{q_k} \\ 0 & 1 \\ 1 & 0 & 1 & 426 & 246 & 1 \\ -1 & 1 & 1 & 246 & 180 & \\ \cline{4-5} 2 & -1 & 2 & 180 & 66 & 1 \\ -5 & 3 & 1 & 132 & 48 & \\ \cline{4-5} 7 & -4 & 2 & 48 & 18 & 1 \\ -19 & 11 & 1 & 36 & 12 & \\ \cline{4-5} 26 & -15 & 2 & 12 & 6 & \\ & & & 12 & & \\ \cline{4-4} & & & 0 & \end{array} \nonumber\] The last nonzero remainder is the greatest common divisor, and the last linear combination gives the desired answer. We find $\gcd(246,426) = 6 = 26\cdot246-15\cdot426$.

Observe that, starting with $k=2$, the signs of $s_k$ and $t_k$ alternate. This provides a quick check of their signs. In addition, the signs of $s_k$ and $t_k$ are opposite for each $k\geq2$.

hands-on exercise $\PageIndex{8}\label{he:gcd-08}$

Use the two-column format to find the linear combination that produces $\gcd(153,732)$.

hands-on exercise $\PageIndex{9}\label{he:gcd-09}$

Use the two-column format to find the linear combination that produces $\gcd(2478,6958)$.

Summary and Review

The greatest common divisor of two integers, not both zero, is the largest (hence it must be positive) integer that divides both.
Use Euclidean algorithm to find the greatest common divisor. It can be implemented in a two-column format.
Using an extended version with two additional columns for computing $s_k$ and $t_k$, we can find the special linear combination of two integers that produces their greatest common divisor.
In general, a linear combination of two integers only gives a multiple of their greatest common divisor.

Exercise $\PageIndex{1}\label{ex:gcd-01}$

For each of the following pairs of integers, find the linear combination that equals to their greatest common divisor.

27, 81
24, 84
1380, 3020

Exercise $\PageIndex{2}\label{ex:gcd-02}$

For each of the following pairs of integers, find the linear combination that equals to their greatest common divisor.

120, 615
412, 936
1122, 3672

Exercise $\PageIndex{3}\label{ex:gcd-03}$

What are the possible values of $\gcd(2a+5b,5a-2b)$ if the two positive integers aa and bb are relatively prime?

Exercise $\PageIndex{4}\label{ex:gcd-04}$

Prove that any consecutive odd positive integers are relatively prime.

Exercise $\PageIndex{5}\label{ex:gcd-05}$

Let $m$ and $n$ be positive integers. Prove that $\gcd(m,m+n)\mid n$.

Exercise $\PageIndex{6}\label{ex:gcd-06}$

Let $a$ and $b$ be integers such that $1<a<b$ and $\gcd(a,b)=1$. Prove that $\gcd(a+b,ab)=1$.

Exercise $\PageIndex{7}\label{ex:gcd-07}$

What are the possible values of $\gcd(3m-5n,5m+3n)$ if the two positive integers $m$ and $n$ are relatively prime?

Exercise $\PageIndex{8}\label{ex:gcd-08}$

What are the possible values of $\gcd(4p+7q,7p-4q)$ if the two positive integers $p$ and $q$ are relatively prime?