Skip to main content

Section 8.2 The GCD and the Euclidean Algorithm

Definition 8.2.1.

Let \(a\) and \(b\) be two nonzero integers. A common divisor or common factor of \(a\) and \(b\) is an integer \(d \in \NN\) such that \(d\) divides both \(a\) and \(b\text{.}\) The greatest common divisor (AKA the highest common factor) of \(a\) and \(b\) is the largest common divisor of \(a\) and \(b\text{.}\) We denote this integer \(d\) by \(\gcd(a,b)\) (you may also see the notation \(\mathrm{hcf}(a,b)\text{.}\)

If \(\gcd(a,b)=1\text{,}\) then we say that \(a\) and \(b\) are said to be coprime or relatively prime.

Thus \(a\) and \(b\) are coprime if and only if their only (positive) common divisor is \(1\text{.}\)

\(\gcd(15,45)=15\text{,}\) \(\gcd(6,15)=3\text{,}\) and \(\gcd(17,91)=1\text{.}\)

We allow ourselves the flexibility to speak of the gcd of negative integers as well as positive ones, but we notice that

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

(So for instance \(\gcd(-6,-27) = \gcd(6, 27) = 3\text{.}\)) As a result, we will mostly focus on the gcd of natural numbers.

For a prime \(p>1\) and any integer \(n\text{,}\) we have:

\begin{align*} \end{align*}
Definition 8.2.4.

Let \(a\) and \(b\) be integers. An integer linear combination of \(a\) and \(b\) is an integer of the form \(ma + nb\) for some \(m,n \in \ZZ\text{.}\)

Notice that a linear combination of linear combinations is a linear combination. That is, if \(c\) and \(b\) are each linear combinations of \(a\) and \(b\text{,}\) then for some integers \(m\text{,}\) \(n\text{,}\) \(p\text{,}\) and \(q\text{,}\) we have \(c = m a + n b\) and \(d = p a + q b\text{.}\) If we form a linear combination of \(c\) and \(d\text{,}\) we get

\begin{equation*} r c + s d = (rm+sp)a + (rn+sq)b\text{,} \end{equation*}

which is a linear combination of \(a\) and \(b\text{.}\)

A little trick that we will use repeatedly is the observation that common divisors of two integers are also divisors of linear combinations of those integers:

Since \(d\) divides \(a\) and \(d\) divides \(b\text{,}\) there are integers \(s\) and \(t\) so that \(a=sd\) and \(b=td\text{.}\) Hence

\begin{equation*} ma+nb=msd+ntd=(ms+nt)d \end{equation*}

and so \(d\) divides \(ma+nb\text{.}\)

Let \(a, b \in \ZZ\text{.}\) If there is a linear combination of \(a\) and \(b\) that gives \(1\text{,}\) then \(a\) and \(b\) are coprime. Indeed, if \(m,n \in \ZZ\) have the property that \(ma+nb = 1\text{,}\) then any common divisor \(d\) of \(a\) and \(b\) must also divide \(1\text{.}\) But then \(d=1\text{,}\) so \(\gcd(a,b)=1\text{.}\)

Here we'll show \(n\) and \(n+1\) are coprime: By the Linear Combination Lemma, \(\gcd(n,n+1)\) divides \((n+1)-n=1\text{,}\) so \(\gcd(n,n+1)\) divides \(1\text{.}\) Thus \(\gcd(n,n+1)=1\text{.}\)

We can also use it to narrow down the gcd of two numbers:

For \(n\in\mathbb{N}\text{,}\) what is \(\gcd(4n^2-2,2n)?\) Observe that by the Linear Combination Lemma, \(\gcd(4n^2-2,2n)\) divides \((2n)(2n)-(4n^2-2)=2\text{,}\) so the highest common factor of these numbers is either \(1\) or \(2\text{.}\) Since \(2\) divides both \(4n^2-2\) and \(2n\text{,}\) it also divides the \(\gcd\text{,}\) so Lemma 8.1.3 implies \(\gcd(4n^2-2,2n)=2\text{.}\)

How do we find the gcd for very large numbers? For this we use the Euclidean Algorithm which exploits the Remainder Theorem and the Linear Combination Lemma.

Let \(a,b\in\NN\text{.}\) Let us also assume \(a\lt b\text{.}\) We are going to construct a sequence of nonnegative integers

\begin{equation*} 0 = r_{n+1} \lt r_n \lt \cdots \lt r_2 \lt r_1 = a \lt r_0 = b \end{equation*}

such that for each \(k \in \NN\text{,}\) if \(k\leq n\text{,}\) then:

  1. \(r_{k-1}\) is an integer linear combination of \(r_k\) and \(r_{k+1}\text{,}\) and

  2. \(r_{k+1}\) is an integer linear combination of \(r_k\) and \(r_{k-1}\text{.}\)

If we manage to construct a sequence with these properties, then \(\gcd(a,b)\) will be the natural number \(r_n\text{.}\) Before we perform the construction, let's understand why. The key is the Linear Combination Lemma.

  • We first claim that \(\gcd(a,b)\) divides \(r_{n}\text{.}\) Note that \(r_0=b\) and \(r_1=a\) are certainly linear combinations of \(a\) and \(b\text{.}\) Let \(k\in \NN\) with \(1\leq k \leq n\text{.}\) If \(r_{k-1}\) and \(r_k\) are each integer linear combinations of \(a\) and \(b\text{,}\) so is \(r_{k+1}\text{.}\) By induction, we conclude that \(r_n\) is a integer linear combination of \(a\) and \(b\text{.}\) Hence it follows from the Linear Combination Lemma that \(\gcd(a,b)\) divides \(r_n\text{.}\)

  • On the other hand, we claim that \(r_{n}\) divides \(\gcd(a,b)\text{.}\) This is equivalent to the claim that \(r_n\) is a common divisor of \(a\) and \(b\text{.}\) Note that since \(r_{n+1}=0\text{,}\) it follows that \(r_{n-1}=q_{n+1}r_{n}\) for some \(q_{n+1}\in\ZZ\text{,}\) so \(r_{n}\) divides \(r_{n-1}\text{.}\) Let \(k\in \NN\) with \(k \leq n\text{.}\) Assume that \(r_n\) divides \(r_k\) and \(r_{k+1}\text{;}\) since \(r_{k-1}\) is a linear combination of \(r_k\) and \(r_{k+1}\text{,}\) it follows from the Linear Combination Lemma that \(r_n\) divides \(r_{k-1}\) as well. By induction, we conclude that \(r_n\) divides \(r_1=a\) and \(r_0=b\text{.}\)

This proves (using Lemma 8.1.3) that \(\gcd(a,b)=r_n\text{.}\)

So our goal now is to present an iterative construction of a sequence of nonnegative integers

\begin{equation*} 0 = r_{n+1} \lt r_n \lt \cdots \lt r_2 \lt r_1 = a \lt r_0 = b \end{equation*}

such that for each \(k \in \NN\text{,}\) if \(k\leq n\text{,}\) then

  1. \(r_{k-1}\) is an integer linear combination of \(r_k\) and \(r_{k+1}\text{,}\) and

  2. \(r_{k+1}\) is an integer linear combination of \(r_k\) and \(r_{k-1}\text{.}\)

To begin the iteration, we set \(r_0 = b\) and \(r_1 = a\text{.}\) To construct the rest of the sequence, assume that for some \(k\in\NN\) we have constructed nonnegative integers \(r_k \lt r_{k-1} \lt \dots \lt r_1 \lt r_0\) with the two properties above. Now use the Remainder Theorem to find an integers \(q_{k+1}\) and \(r_{k+1}\) such that

\begin{equation*} r_{k-1} = q_{k+1}r_k + r_{k+1}\text{.} \end{equation*}

Thus \(r_{k-1}\) is a linear combination of \(r_k\) and \(r_{k+1}\text{,}\) but also \(r_{k+1} = r_{k-1} - q_{k+1} r_k\) so \(r_{k+1}\) is a linear combination of \(r_k\) and \(r_{k-1}\text{.}\)

This process must terminate with \(r_{n+1}=0\) for some \(n\text{,}\) since the \(r_{j}\) are nonnegative and strictly decreasing. This completes the construction of the sequence

\begin{equation*} 0 = r_{n+1} \lt r_n \lt \cdots \lt r_2 \lt r_1 = a \lt r_0 = b \end{equation*}

with the desired properties.

Let's watch this algorithm in action.

Let \(a = r_1 = 6\) and \(b = r_0 = 15\text{.}\)

  • We divide \(15\) by \(6\) to get \(2\) with a remainder of \(r_2=3\text{.}\)

  • We divide \(6\) by \(3\) to get \(2\) with a remainder of \(r_3 = 0\text{.}\)

Thus \(r_2 = 3\) is the gcd of \(6\) and \(15\text{.}\)

Let \(a = r_1 = 48\) and \(b = r_0 = 66\text{.}\)

  • We divide \(66\) by \(48\) to get \(1\) with a remainder of \(r_2=18\text{.}\)

  • We divide \(48\) by \(18\) to get \(2\) with a remainder of \(r_3 = 12\text{.}\)

  • We divide \(18\) by \(12\) to get \(1\) with a remainder of \(r_4 = 6\text{.}\)

  • We divide \(12\) by \(6\) to get \(2\) with a remainder of \(r_5 = 0\text{.}\)

Thus \(r_4 = 6\) is the gcd of \(48\) and \(66\text{.}\)

Let \(a = r_1 = 120\) and \(b = r_0 = 214\text{.}\)

  • We divide \(214\) by \(120\) to get \(1\) with a remainder of \(r_2=94\text{.}\)

  • We divide \(120\) by \(94\) to get \(1\) with a remainder of \(r_3 = 26\text{.}\)

  • We divide \(94\) by \(26\) to get \(3\) with a remainder of \(r_4 = 16\text{.}\)

  • We divide \(26\) by \(16\) to get \(1\) with a remainder of \(r_5 = 10\text{.}\)

  • We divide \(16\) by \(10\) to get \(1\) with a remainder of \(r_6 = 6\text{.}\)

  • We divide \(10\) by \(6\) to get \(1\) with a remainder of \(r_7 = 4\text{.}\)

  • We divide \(6\) by \(4\) to get \(1\) with a remainder of \(r_8 = 2\text{.}\)

  • We divide \(4\) by \(2\) to get \(2\) with a remainder of \(r_9 = 0\text{.}\)

Thus \(r_8 = 2\) is the gcd of \(120\) and \(214\text{.}\)

Let \(a = r_1 = 14\) and \(b = r_0 = 348\text{.}\)

  • We divide \(348\) by \(14\) to get \(24\) with a remainder of \(r_2=12\text{.}\)

  • We divide \(14\) by \(12\) to get \(1\) with a remainder of \(r_3 = 2\text{.}\)

  • We divide \(12\) by \(2\) to get \(6\) with a remainder of \(r_4 = 0\text{.}\)

Thus \(r_3 = 2\) is the gcd of \(14\) and \(348\text{.}\)

Let \(a = r_1 = 2059\) and \(b = r_0 = 6744\text{.}\)

  • We divide \(6744\) by \(2059\) to get \(3\) with a remainder of \(r_2=567\text{.}\)

  • We divide \(2059\) by \(567\) to get \(3\) with a remainder of \(r_3 = 358\text{.}\)

  • We divide \(567\) by \(358\) to get \(1\) with a remainder of \(r_4 = 209\text{.}\)

  • We divide \(358\) by \(209\) to get \(1\) with a remainder of \(r_5 = 149\text{.}\)

  • We divide \(209\) by \(149\) to get \(1\) with a remainder of \(r_6 = 60\text{.}\)

  • We divide \(149\) by \(60\) to get \(2\) with a remainder of \(r_7 = 29\text{.}\)

  • We divide \(60\) by \(29\) to get \(2\) with a remainder of \(r_8 = 2\text{.}\)

  • We divide \(29\) by \(2\) to get \(14\) with a remainder of \(r_9 = 1\text{.}\)

  • We divide \(2\) by \(1\) to get \(2\) with a remainder of \(r_{10} = 0\text{.}\)

Thus \(r_9 = 1\) is the gcd of \(2059\) and \(6744\text{.}\) In particular, \(2059\) and \(6744\) are coprime.

One important corollary of the Euclidean Algorithm is the following.

Let's revisit some of the examples above to find the \(s\) and \(t\text{.}\)

Let \(a = r_1 = 6\) and \(b = r_0 = 15\text{.}\)

  • We divide \(15\) by \(6\) to get \(2\) with a remainder of \(r_2=3\text{.}\)

  • We divide \(6\) by \(3\) to get \(2\) with a remainder of \(r_3 = 0\text{.}\)

Thus \(\gcd(6,15) = 3 = 15-2\cdot 6\text{.}\)

Let \(a = r_1 = 48\) and \(b = r_0 = 66\text{.}\)

  • We divide \(66\) by \(48\) to get \(1\) with a remainder of \(r_2=18\text{.}\)

  • We divide \(48\) by \(18\) to get \(2\) with a remainder of \(r_3 = 12\text{.}\)

  • We divide \(18\) by \(12\) to get \(1\) with a remainder of \(r_4 = 6\text{.}\)

  • We divide \(12\) by \(6\) to get \(2\) with a remainder of \(r_5 = 0\text{.}\)

Thus \(\gcd(48,66) = 6 = 18-12 = 3\cdot 18-48 = 3\cdot 66 -4\cdot 48\text{.}\)

Let \(a = r_1 = 2059\) and \(b = r_0 = 6744\text{.}\)

  • We divide \(6744\) by \(2059\) to get \(3\) with a remainder of \(r_2=567\text{.}\)

  • We divide \(2059\) by \(567\) to get \(3\) with a remainder of \(r_3 = 358\text{.}\)

  • We divide \(567\) by \(358\) to get \(1\) with a remainder of \(r_4 = 209\text{.}\)

  • We divide \(358\) by \(209\) to get \(1\) with a remainder of \(r_5 = 149\text{.}\)

  • We divide \(209\) by \(149\) to get \(1\) with a remainder of \(r_6 = 60\text{.}\)

  • We divide \(149\) by \(60\) to get \(2\) with a remainder of \(r_7 = 29\text{.}\)

  • We divide \(60\) by \(29\) to get \(2\) with a remainder of \(r_8 = 2\text{.}\)

  • We divide \(29\) by \(2\) to get \(14\) with a remainder of \(r_9 = 1\text{.}\)

  • We divide \(2\) by \(1\) to get \(2\) with a remainder of \(r_{10} = 0\text{.}\)

Thus

\begin{align*} \gcd(6744, 2059) = 1 \amp = 29 - 14\cdot 2\\ \amp = 29\cdot 29 - 14 \cdot 60\\ \amp = 29\cdot 149-72\cdot 60\\ \amp = 101\cdot 149-72\cdot 209\\ \amp = 101\cdot 358-173\cdot 209\\ \amp = 274\cdot 358-173\cdot 567\\ \amp = 274\cdot 2059-995\cdot 567\\ \amp = 3259\cdot 2059-995\cdot 6744 \end{align*}

Bezout's Identity is incredibly useful, even in examples that seem to have nothing to do with the gcd:

Let \(a\) and \(b\) be coprime integers. Show that

  • (i).

    If \(a\) divides \(c\) and \(b\) divides \(c\) then \(ab\) divides \(c\text{.}\)

  • (ii).

    If \(a\) divides \(bc\) then \(a\) divides \(c\text{.}\)

Show that both parts of this result can fail if \(a\) and \(b\) are not coprime.

Solution.
  • (i).

    Since \(a\) and \(b\) are coprime, we can find integers \(s\) and \(t\) so that \(sa + tb = 1\text{.}\) If \(a\) divides \(c\) then we can write \(c = ax\text{,}\) and if \(b\) divides \(c\) then we can write \(c = by\) for some \(x,y \in \ZZ\text{.}\) Then \(c = csa + ctb = (by)sa + (ax)tb = (ab)sy + (ab)xt\text{,}\) so \(ab\) divides \(c\text{.}\)

  • (ii).

    As in (i), \(c = csa + ctb\text{.}\) If \(a\) divides \(bc\) then write \(az = bc\) for some integer \(z\text{,}\) and then we have \(c = csa + t(az) = a(cs + tz)\text{,}\) so \(a\) divides \(c\text{.}\)

Show that if \(a, b\) are postive integers, and \(d=gcd(a,b)\) then there exist positive integers \(s, t\) such that \(d=sa-tb\text{.}\) Note: that this exercise differs from Bezout’s Identity, in that we ask \(s, t\) to be positive.

Solution.

Claim: If \(a,b\) are positive integers and \(d=gcd(a,b)\text{,}\) we can find positive integers \(s, t \in\mathbb{Z}\) such that \(d=sa-tb\text{.}\)

By the Euclidean algorithm, we can find integers \(s,t\in\mathbb{Z}\text{,}\) such that

\begin{equation} d=sa+tb\label{gcdeqn}\tag{8.2.1} \end{equation}

Since \(0\lt d\leq a,b\text{,}\) at most one of \(s\) and \(t\) can be positive, and at most one can be non-positive (i.e. zero or negative). If it happens that \(t\) is negative, then we will have produced the desired expression for \(d\) (by writing \(d=sa - (-t)b\)).

In case \(t\) is non-negative, we can apply the following observation:

We have \((s+kb)a + (t-ka)b = sa+tb\text{,}\) simply by expanding the LHS, so one finds the same condition for both pairs.

Choosing \(k\) sufficiently large, we can replace \(t\) by \(t-ka\) so that it is negative. It follows then that \(s+kb\) is positive.