Loading [MathJax]/jax/element/mml/optable/BasicLatin.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

5.4: Greatest Common Divisors

( \newcommand{\kernel}{\mathrm{null}\,}\)

Given any two integers a and b, an integer c0 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, 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.

  1. 27, 81
  2. 24, 84
  3. 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.

  1. 120, 615
  2. 412, 936
  3. 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?


This page titled 5.4: Greatest Common Divisors is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Harris Kwong (OpenSUNY) .

Support Center

How can we help?