1.7: Greatest Common Divisor and Least Common Multiple

In the last few chapters we have discussed divisibility and the Division Algorithm when a single number is divided by another. In this chapter we begin to look at divisors and multiples that two numbers have in common.

Definition \(\PageIndex{1}\): Greatest Common Divisor

Let \(a,b\in\mathbb{Z}\). If \(a\ne 0\) or \(b\ne 0\), we define the greatest common divisor of \(a\) and \(b\), denoted \(\gcd(a,b)\), to be the largest integer \(d\) such that \(d\mid a\) and \(d\mid b\). We define \(\gcd(0,0)=0\).

Discussion.

If \(e\mid a\) and \(e\mid b\) we call \(e\) a common divisor of \(a\) and \(b\). Let \[C(a,b)=\{e:e\mid a\text{ and }e\mid b\},\nonumber \] that is, \(C(a,b)\) is the set of all common divisors of \(a\) and \(b\). Note that since everything divides \(0\) \[C(0,0)=\mathbb{Z}\nonumber \] so there is no largest common divisor of \(0\) with \(0\). This is why we must define \(\gcd(0,0)=0\).

Example \(\PageIndex{1}\)

\[C(18,30)=\{-1,1,-2,2,-3,3,-6,6\}.\nonumber\] So \(\gcd(18,30)=6\).

Lemma \(\PageIndex{1}\)

If \(e\mid a\) then \(-e\mid a\).

Proof

If \(e\mid a\) then \(a=ek\) for some \(k\). Then \(a=(-e)(-k)\). Since \(-e\) and \(-k\) are also integers \(-e\mid a\).

Lemma \(\PageIndex{2}\)

If \(a\ne 0\), the largest positive integer that divides \(a\) is \(|a|\).

Proof

Recall that \[|a|=\left\{\begin{array}{ccc} a & \text{if} & a\ge 0 \\ -a & \text{if} & a<0. \end{array}\right.\nonumber \] First note that \(|a|\) actually divides \(a\): If \(a>0\), since we know \(a\mid a\) we have \(|a|\mid a\). If \(a<0\), \(|a|=-a\). In this case \(a=(-a)(-1)=|a|(-1)\) so \(|a|\) is a factor of \(a\). So, in either case \(|a|\) divides \(a\), and in either case \(|a|>0\), since \(a\ne 0\).

Now suppose \(d\mid a\) and \(d\) is positive. Then \(a=dk\) some \(k\) so \(-a=d(-k)\) for some \(k\). So \(d\mid |a|\). So by Theorem 1.4.1 (10) we have \(d\le|a|\).

The following lemma shows that in computing \(\gcd\)’s we may restrict ourselves to the case where both integers are positive.

Lemma \(\PageIndex{3}\)

For any integers \(a\) and \(b\), \[\gcd(a,b)=\gcd(|a|,|b|).\nonumber \]

Proof

If \(a=0\) and \(b=0\), we have \(|a|=a\) and \(|b|=b\). So \(\gcd(a,b)=\gcd(|a|,|b|)\). Suppose one of \(a\) or \(b\) is not \(0\). Note that \(d\mid a\Leftrightarrow d\mid |a|\). See Exercise \(\PageIndex{1}\). It follows that \[C(a,b)=C(|a|,|b|).\nonumber \] So the largest common divisor of \(a\) and \(b\) is also the largest common divisor of \(|a|\) and \(|b|\).

The last lemma above showed that to find the greatest common divisor of any two numbers, it is enough to be able to do so for nonnegative numbers. Exercise \(\PageIndex{1}\) at the end of the chapter proves a more general statement about divisibility.

Lemma \(\PageIndex{4}\)

For any integers \(a\) and \(b\), \[\gcd(a,b)=\gcd(b,a).\nonumber \]

Proof

Clearly \(C(a,b)=C(b,a)\). It follows that the largest integer in \(C(a,b)\) is the largest integer in \(C(b,a)\), that is, \(\gcd(a,b)=\gcd(b,a)\).

Lemma \(\PageIndex{5}\)

If \(a\ne 0\) and \(b\ne 0\), then \(\gcd(a,b)\) exists and satisfies \[0<\gcd(a,b)\le\min\{|a|,|b|\}.\nonumber \]

Proof

Note that \(\gcd(a,b)\) is the largest integer in the set \(C(a,b)\) of common division of \(a\) and \(b\). Since \(1\mid a\) and \(1\mid b\) we know that \(1\in C(a,b)\). So the largest common divisor must be at least \(1\) and is therefore positive. On the other hand \(d\in C(a,b)\Rightarrow d\mid |a|\) and \(d\mid |b|\) so \(d\) is no larger than \(|a|\) and no larger than \(|b|\). So \(d\) is at most the smaller of \(|a|\) and \(|b|\). Hence \(\gcd(a,b)\le\min\{|a|,|b|\}\).

Example \(\PageIndex{2}\)

From the above lemmas we have \[\begin{split} \gcd(48,732) &=\gcd(-48,732) \\ &=\gcd(-48,-732) \\ &=\gcd(48,-732). \end{split}\] We also know that \[0<\gcd(48,732)\le 48.\nonumber \] Since if \(d=\gcd(48,732)\), then \(d\mid 48\), to find \(d\) we may check only which positive divisors of \(48\) also divide \(732\).

In the next chapter we will discuss a more computationally practical way to compute \(\gcd(a,b)\). Right now we discuss a complementary concept.

Definition \(\PageIndex{2}\)

Let \(a,b\in\mathbb{N}\). We define the least common multiple of \(a\) and \(b\), denoted \(\operatorname{lcm}(a,b)\), to be the smallest positive integer \(m\) such that \(a\mid m\) and \(b\mid m\).

Example \(\PageIndex{3}\)

If we wish to find \(\operatorname{lcm}(6,10)\), we may start by listing positive multiples of 10 and looking for the first one that it divisible by 6. Since neither 10 nor 20 is divisible by 6 but \(30 = 10 \cdot 3 = 6 \cdot 5\), we see both that 30 is a multiple of both 6 and 10, and no smaller positive multiple of 10 is divisible by 6. Hence \(\operatorname{lcm}(6,10)=30\).

Exercises \(\PageIndex{5}\) and \(\PageIndex{6}\) in this chapter invite you to discover a few basic properties of \(\operatorname{lcm}(a,b)\). Like the greatest common divisor, the least common multiple will be further developed over the next few chapters.

Exercises

Exercise \(\PageIndex{1}\)

Prove that \[d\mid a\Leftrightarrow d\mid |a|.\nonumber \] (Hint: recall that \[|a|=\begin{cases}a & \text{ if } a\ge 0;\\-a & \text{ if } a<0\end{cases},\nonumber \] so it may help to consider two cases. Also remember the definition of “divides,” and use it here.)

Exercise \(\PageIndex{2}\)

Find \(\gcd(48,732)\) using Example \(\PageIndex{2}\).

Exercise \(\PageIndex{3}\)

Find \(\gcd(a,b)\) for each of the following values of \(a\) and \(b\):

1. \(a=-14\), \(b=14\)
2. \(a=-1\), \(b=78654\)
3. \(a=0\), \(b=-78\)
4. \(a=2\), \(b=-786541\)

Exercise \(\PageIndex{4}\)

Find both \(\gcd(a,b)\) and \(\operatorname{lcm}(a,b)\) for each of the following values of \(a\) and \(b\). (Explain your reasoning, using only the definitions and properties discussed in this chapter; do not assume other properties that have not been proved yet.)

1. \(a=3\), \(b=14\)
2. \(a=9\), \(b=15\)
3. \(a = 58\), \(b=406\)
4. \(a=74\), \(b=111\)

Exercise \(\PageIndex{5}\)

The definition given in this chapter requires that \(\operatorname{lcm}(a,b)\) be a positive integer and that \(a\) and \(b\) be natural numbers. To examine why this might be convenient, answer the following:

1. What is the smallest common multiple (not necessarily positive) of \(0\) and \(b\), where \(b\) is any integer?
2. If neither \(a\) nor \(b\) is \(0\), is there a smallest common multiple of \(a\) and \(b\) among the negative integers? Illustrate your answer with an example, choosing a specific pair \(a,b\) of nonzero integers and discussing their common multiples.

Exercise \(\PageIndex{6}\)

Each of the lemmas in this chapter discusses divisors and/or \(\gcd(a,b)\). For each lemma, can you find a similar, true statement about multiples and/or \(\operatorname{lcm}(a,b)\)? If so, write these statements down (proving them is encouraged but optional); if not, explain why not.