Highest common factors and least common multiples (HCF and LCM) are important concepts to master for the CAT Quantitative section. They play a key role in reducing and combining fractions, factoring, and many other mathematics skills. This review article will help you to understand what you need to know about HCF and LCM for the CAT.

(Check out this handy Math Syllabus for CAT Exam to see what other mathematical topics are covered on the test!)

## Factors and Multiples

In order to understand HCF and LCM, first you need to know a thing or two about factors and multiples.

A **factor** of a number is any number that divides into it with zero remainder. For example, the factors of 15 are: 1, 3, 5, and 15. The number 2, for example, is not a factor of 15, because 15/2 = 7.5 is not a whole number (there is a remainder). Factors are always less than or equal to the original number.

**Multiples** are numbers that have the original number as a factor. In other words, a multiple of *N* is simply the product of *N* by another whole number *k* (that is, *k* × *N*). For example, the multiples of 5 are: 5, 10, 15, 20, 25, 30, … Multiples are always greater than or equal to the original number, and there are infinitely many of them.

### Primes and Prime Factorizations

For any whole number *N*, the numbers 1 and *N* itself are always factors. Any number that has *only* those two factors is called **prime**. Prime numbers become very important when computing HCF and LCM, because the quickest way to compute these items is to compare prime factorizations.

There are infinitely many primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … Fortunately, you may only need to know the first five or six of these for most applications.

Every whole number has a unique **prime factorization**, that is, a list of the primes or prime powers that are factors of the number. The easiest way to find the prime factorization of a number is to use a **factor tree**.

To build a factor tree for a number *N*, follow these steps:

- If the first prime, 2, is a factor, then divide by 2.
- Place 2 on the left branch and the quotient on the right branch.
- Repeat as needed until the quotient no longer has 2 as a factor.
- Now, do steps 1–3 again on the current quotient, but with the next prime, 3.
- Repeat, using larger and large primes until the last quotient is itself prime.
- The primes on the “leaves” of the tree make up the prime factorization. Write your answer as a product of powers of primes.

Let’s see how it works for the number 168.

Therefore, 168 = 2^{3} × 3 × 7.

Now you try it for the number 90. (You can check your answer by reading through the next section.)

## Computing the HCF and LCM

Let’s start with just two numbers, *M* and *N*, though the methods work for three or more numbers just as easily.

- Find prime factorizations of both numbers.
- To compute
**HCF**of*M*and*N*: For each prime number, select the**smaller**power of the prime from the two prime factorizations. If one of the numbers does not have a particular prime, then that prime power will be zero in the HCF. - To compute the
**LCM**of*M*and*N*: For each prime number, select the**larger**power of the prime from the two prime factorizations.

Ok, so let’s use our steps to compute the HCF and LCM of 168 and 90.

- 168 = 2
^{3}× 3 × 7 - 90 = 2 × 3
^{2}× 5 (Did you get the right prime factorization?) - HCF(168, 90) = 2 × 3 = 6
- LCM(168, 90) = 2
^{3}× 3^{2}× 5 × 7 = 2520

Note: If there are more than two numbers, then just choose the smallest prime powers overall to find HCF, or the largest prime powers overall to find LCM.

## Using HCF and LCM in Problems

Ok, so why do we care about the highest common factor or least common multiple of a pair of numbers?

### HCF and Factoring

The HCF helps in factoring. For example, if you need to factor the polynomial 168*x*^{7} – 90*x*^{5}, then you first find the HCF of 168 and 90 (which we did above — it’s 6). Then you find the smallest power of the variable(s) showing up (which should remind you of the process of finding HCF for numbers, by the way). Then divide all terms by those items and write your answer appropriately:

168*x*^{7} – 90*x*^{5} = 6*x*^{5}(28*x*^{2} – 15)

### LCM and Combining Fractions

On the other hand, the LCM is useful in combining (adding/subtracting) fractions. Let’s see how it works!

Suppose you need to simplify 55/168 – 7/90. First find the LCM of the denominators, 168 and 90. Luckily, we’ve already done that step above and found that LCM(168, 90) = 2520. Now you also need to know how many times each denominator goes into the LCM, because those multipliers must be used on the numerators as well.

2520 ÷ 168 = 15

2520 ÷ 90 = 28

Now convert both fractions to equivalent ones with 2520 as denominator.

## Example Problems

Finally it’s your turn to practice the concepts. You can check your answers by scrolling down.

- A bowl full of candies can be redistributed into boxes each containing 4 candies, but there will be 1 left over. If put into boxes of 5 candies each, then there will still be 1 left over. Finally, if put into boxes of 6 candies each, there will again be 1 left over. What is the smallest number of candies that could have been in the bowl, assuming there is more than one piece of candy?
- Suppose two positive numbers add to 72. What is the largest possible HCF of the numbers?

### Solutions

**61**. Let*N*be the number of candies. The information implies that*N*– 1 is a multiple of 4, 5, and 6. Since we are looking for the least number possible, we need to compute LCM(4, 5, 6). We obtain*N*– 1 = 60, so*N*= 61.**36**. Let*x*+*y*= 72. Now if any common factors exits between*x*and*y*, then those factors must also be factors of 72. Because both numbers are positive, the largest such common factor must be half of 72, or*x*= 36 and*y*= 36. Finally, HCF(*x*,*y*) = HCF(36, 36) = 36.

By the way, sign up for our 1 Week Free Trial to try out Magoosh GMAT Prep!

nice explanation of use of HCF and LCM

Thank you!! ðŸ™‚