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.