# Divisibility, prime factorization, GCF and LCM

You are likely to encounter one or two divisibility questions on the SHSAT.  The good news is that most of them are straightforward greatest common factor or least common multiple problems. If you don’t know how to find GCF and LCM using prime factorization, check out one of the first three links at the bottom of the page. This post is about understanding divisibility a little deeper.

Every now and then you get a trickier problem like this one:

Which of the following is a factor of ?

a) b) c) d) e) (Note for those who aren’t familiar with the symbol. It is just a symbol for multiplication, so is the same thing as 2 x 2.)

Most 8th graders haven’t learned enough about divisibility to easily solve this problem. I didn’t go deep into divisibility until college. So let’s talk about divisibilty and factoring using an example.

Let’s use the number 60. The prime factorization of 60 is 2 x 2 x 3 x 5.

The factors of 60 are 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, and 60. Now let’s prime factorize all these factors (except for 1).

2

3

4 = 2 x 2

5

6 = 2 x 3

10 = 2 x 5

12 = 2 x 2 x 3

15 = 3 x 5

20 = 2 x 2 x 5

30 = 2 x 3 x 5

60 = 2 x 2 x 3 x 5

What you might notice is that all these factors are just combinations of the prime factors of 60.

This is the key idea of divisibility.  All the factors (besides 1) of a whole number are made up of the prime factors of the number.

Let’s try one more number: 45.

Prime factorize:  45 = 3 x 3 x 5

Factors of 45:

1

3

5

9 = 3 x 3

15 = 3 x 5

45 = 3 x 3 x 5

So the rule works again! 3, 5, 9, 15, and 45, can all be made out of 3, 3, and 5 using multiplication. Now we can use the rule to solve our problem.

2 x 2 x 2 x 3 x 3 x 5 x 7 x 7 x 13 is a big number, but we know that all of its factors can be made by multiplying some of its prime factors. The only answer choice we can make from 2, 2, 2, 3, 3, 5, 7, 7, and 13 is choice D, 2 x 3 x 3 x 5 x 7 x 13, so that is the only one of the choices that is a factor of our big number. Choices A and C have prime numbers that are not in the original (11 and 17), and choice B has too many 5’s. Choice E is actually larger than the original number and is a multiple of it, not a factor.

What does this have to do with GCF and LCM?

We can use this rule to talk about the concepts behind GCF and LCM.

GCF:

We want to find the GCF of two numbers. We know that the factors of each number are made up of the prime factors of the number. The greatest common factor, or the biggest factor they both have in common, is just the biggest number that can be made from both numbers’ prime factors. Let’s do an example.

What is the GCF of 84 and 315?

First we prime factor both numbers.

84 = 2 x 2 x 3 x 7

315 = 3 x 3 x 5 x 7

The biggest number that can be made from both sets of prime factors is 3 x 7, or 21. So the greatest common factor of 84 and 315 is 21. It is a factor of both, since it can be made from both of their prime factors, and it is the biggest number that can be made by both sets of prime factors.

LCM

If we want to find the least common multiple of two numbers, we are looking for the smallest number that has both of the numbers as factors. Since both of the numbers are factors, we know that we have to be able to make both numbers should be made of the prime factors of the LCM. Let’s do an example:

What is the least common multiple of 30 and 36?

First we prime factor:

30 = 2 x 3 x 5

36 = 2 x 2 x 3 x 3

So we have to be able to make 2 x 3 x 5 and 2 x 2 x 3 x 3 from our number. The smallest number that they both can be made from is 2 x 2 x 3 x 3 x 5, or 180. So the LCM of 30 and 36 is 180.

Common mistake: A lot of people just combine the prime factors and get 2 x 2 x 2 x 3 x 3 x 3 x 5 (which equals 30 x 36, or 1080). This is wrong. 30 and 36 can both be made from the prime factors of this number, so it is a common multiple, but it is not the least common multiple of 30 and 36. 180 is smaller and both 30 and 36 go into it.

TLDR: This post is about some of the basic ideas of divisibility. For the test, knowing how to do GCF and LCM using prime factorization should get you a couple extra points. Check the further reading.