Processing math: 100%
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

1.7: Greatest Common Divisor and Least Common Multiple

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

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 1.7.1: Greatest Common Divisor

Let a,bZ. If a0 or b0, we define the greatest common divisor of a and b, denoted gcd(a,b), to be the largest integer d such that da and db. We define gcd(0,0)=0.

Discussion.

If ea and eb we call e a common divisor of a and b. Let C(a,b)={e:ea and eb}, 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)=Z so there is no largest common divisor of 0 with 0. This is why we must define gcd(0,0)=0.

Example 1.7.1

C(18,30)={1,1,2,2,3,3,6,6}. So gcd(18,30)=6.

Lemma 1.7.1

If ea then ea.

Proof

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

Lemma 1.7.2

If a0, the largest positive integer that divides a is |a|.

Proof

Recall that |a|={aifa0aifa<0. First note that |a| actually divides a: If a>0, since we know aa we have |a|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 a0.

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

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

Lemma 1.7.3

For any integers a and b, gcd(a,b)=gcd(|a|,|b|).

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 dad|a|. See Exercise 1.7.1. It follows that C(a,b)=C(|a|,|b|). 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 1.7.1 at the end of the chapter proves a more general statement about divisibility.

Lemma 1.7.4

For any integers a and b, gcd(a,b)=gcd(b,a).

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 1.7.5

If a0 and b0, then gcd(a,b) exists and satisfies 0<gcd(a,b)min{|a|,|b|}.

Proof

Note that gcd(a,b) is the largest integer in the set C(a,b) of common division of a and b. Since 1a and 1b we know that 1C(a,b). So the largest common divisor must be at least 1 and is therefore positive. On the other hand dC(a,b)d|a| and d|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)min{|a|,|b|}.

Example 1.7.2

From the above lemmas we have gcd(48,732)=gcd(48,732)=gcd(48,732)=gcd(48,732). We also know that 0<gcd(48,732)48. Since if d=gcd(48,732), then d48, 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 1.7.2

Let a,bN. We define the least common multiple of a and b, denoted lcm(a,b), to be the smallest positive integer m such that am and bm.

Example 1.7.3

If we wish to find 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=103=65, 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 lcm(6,10)=30.

Exercises 1.7.5 and 1.7.6 in this chapter invite you to discover a few basic properties of lcm(a,b). Like the greatest common divisor, the least common multiple will be further developed over the next few chapters.

Exercises

Exercise 1.7.1

Prove that dad|a|. (Hint: recall that |a|={a if a0;a if a<0, so it may help to consider two cases. Also remember the definition of “divides,” and use it here.)

Exercise 1.7.2

Find gcd(48,732) using Example 1.7.2.

Exercise 1.7.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 1.7.4

Find both gcd(a,b) and 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 1.7.5

The definition given in this chapter requires that 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 1.7.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 lcm(a,b)? If so, write these statements down (proving them is encouraged but optional); if not, explain why not.


This page titled 1.7: Greatest Common Divisor and Least Common Multiple is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Mike Barrus & W. Edwin Clark.

Support Center

How can we help?