Greatest Common Divisor (GCD)

and Least Common Multiple (LCM)

Hi everyone. How are we doing today?

Today I would like to help you solve math problems that involve finding the greatest common divisor and least common multiple of a set of positive integers. This can be extremely useful for standardized tests like the ACT and GRE. But before I even get to today’s post, I would like to go back to yesterday’s post on Prime Factorizations where I asked you to draw a factor tree for the number 6137. You can find that post here: Integers, Prime Numbers, and Prime Factorizations

Solution to Last Week’s Question

Let’s compare our drawings.

As I mentioned last week, it’s not artistic merit I am looking for, but rather that the numbers in your ‘tree’ are correct.

Let’s start by taking the square root of 6137. Punching that into your calculator, we see that we get about 78.3. So using the tip that I gave to you last week, we will divide 6137 by the prime numbers less than 78.3.

The primes less than 78.3 are 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71 and 73.

The good news is that we do not need to divide by all of these numbers to ind our factors – let me explain: Dividing by 2, 3, 5, 7, 11, and 13 do not produce integers, but 6137/17 = 361.

Now, the square root of 361 is exactly 19 (this is easily checked in your calculator). So 361 = (19)(19) = 19².

So 6137 = 17 · 19².

Here is my factor tree:

How does your tree look compared to mine? Get in touch if you have any questions regarding this…

GCD and LCM

Now for the main part of the post…

The greatest common divisor (gcd) of a set of positive integers is the largest positive integer that each integer in the set is divisible by.

The least common multiple (lcm) of a set of positive integers is the smallest positive integer that is divisible by each integer in the set.

Example 1

Let’s find the gcd and lcm of 9 and 15.

There are a few ways we can do this.

First method: The factors of 9 are 1, 3 and 9. The factors of 15 are 1, 3, 5 and 15. So the common factors of 9 and 15 are 1 and 3. Therefore we see that gcd (9,15) = 3.

The multiples of 9 are 9, 18, 27, 36, 45, 54, 63,… and the multiples of 15 are 15, 30, 45,.. We can stop at 45 because 45 is also a multiple of 9. Therefore we see that lcm (9,15) = 45.

Second method: We first find the prime factorizations of 9 and 15. We see that 9 = 3² and 15 = 3 · 5. To find the gcd we multiply together the smallest powers of each prime from both factorizations, and for the lcm we multiply the highest powers of each prime. So we have gcd (9,15) = 3 and we have lcm (9,15) = 3² · 5 = 45.

Now take note – If you have trouble seeing where the gcd and lcm are coming from here, it may be helpful to insert the “missing” primes. In this case, 5 is missing from the factorization of 9. So it might help you if you write 9 = 3² · 5º. Now we can think of the gcd as 3¹ · 5º = 3.

Third method: Your calculator can actually do this for you (not on the GRE though)! On your TI-84 calculator press MATH, scroll right to NUM. For the gcd press 9, type 9,15 and press ENTER. You will see an output of 3. For the lcm press 8, type 9,15 and press ENTER for an output of 45.

Example 2

Let’s try another example: Find the gcd and lcm of 100 and 270.

The prime factorizations of 100 and 270 are 100 = 2² · 5² and 270 = 2 · 3³ · 5. So gcd (100,270) = 2 · 5 = 10 and lcm (100,270) = 2² · 3³ · 5² = 2700.

If we were to insert the ‘missing’ primes in the prime factorization of 100 we would get 100 = 2² · 3⁰ · 5². So we can think of the gcd as 2¹ · 30 · 5¹ = 10.

Example 3

Okay, now let’s try an ACT math question…

What is the least positive integer divisible by the integers 3, 7 and 14?

A. 168
B. 126
C. 84
D. 42
E. 28

Calculator method: The question is actually asking for the least common multiple of 3, 7 and 14. Your calculator can only do two at a time. So first compute lcm (3,7) = 21, and then compute lcm (21,14) = 42, choice D.

Simple!

Solution by Starting with choice E: Begin by looking at choice E since it is the smallest. 28/3 comes to approximately 9.33 in our calculator. Since this is not an integer, 28 is not divisible by 3. We can therefore eliminate choice E. We next try choice D.

42/3 = 14, 42/7 = 6, 42/14 = 3

Since these are all integers, the answer is choice D.

For more information on this strategy see the following blog post: Starting With Choice C – A Basic SAT Math Strategy.

Example 4

Now here is a much more difficult example for us to try together:

The integer k is equal to m² for some integer m. If k is divisible by 6 and 40, what is the smallest possible positive value of k?

Did you realize that we are looking for the smallest perfect square that is divisible by the least common multiple of 6 and 40? Let’s find some prime factorizations: 6 = 2 · 3, and 40 = 2³ ·5. So lcm (6,40) = 2³ · 3 · 5. The least perfect square divisible by this number is 2⁴ · 3² · 5² = 3600.

It’s not too hard when you know how to compute the lcm.

This was quite a long blog post, but I hope you have received some good value from it.

Click on the picture below for more information about the Get 800 collection of test prep books.

Comments

comments