# LCM & HCF

Prime factorisation

A prime factorisation of a natural number can be expressed in the exponential form.

For example:

(i) 48 = 2 x 2 x 2x 2 x3 = 2^{4} x 3

(ii) 420 = 2 x 2 x 3 x 5 x 7 = 2^{2} x 3 x 5 x 7

Least Common Multiple (L.C.M.)A common multiple is a number that is a multiple of two or more numbers. The common multiples of 3 and 4 are 0, 12, 24, ....

The least common multiple (LCM) of two numbers is the smallest number (not zero) that is a multiple of both.

Method 1 Simply list the multiples of each number (multiply by 2, 3, 4, etc.) then look for the smallest number that appears in each list.

Example: Find the least common multiple for 5, 6, and 15.

Multiples of 5 are 10, 15, 20, 25, 30, 35, 40,...

Multiples of 6 are 12, 18, 24, 30, 36, 42, 48,...

Multiples of 15 are 30, 45, 60, 75, 90,....

Now, when you look at the list of multiples, you can see that 30 is the smallest number that appears in each list.Therefore, the least common multiple of 5, 6 and 15 is 30.

Method 2 To use this method factor each of the numbers into primes. Then for each different prime number in all of the factorizations, do the following...

1. Count the number of times each prime number appears in each of the factorizations.

2. For each prime number, take the largest of these counts.

3. Write down that prime number as many times as you counted for it in step 2.

The least common multiple is the product of all the prime numbers written down.

Example: Find the least common multiple of 5, 6 and 15.

Factor into primes

Prime factorization of 5 is 5

Prime factorization of 6 is 2 x 3

Prime factorization of 15 is 3 x 5

Â· Notice that the different primes are 2, 3 and 5.

Now, we do Step #1 - Count the number of times each prime number appears in each of the factorizations...

The count of primes in 5 is one 5

The count of primes in 6 is one 2 and one 3

The count of primes in 15 is one 3 and one 5

Step #2 - For each prime number, take the largest of these counts. So we have...

The largest count of 2s is one

The largest count of 3s is one

The largest count of 5s is one

Step #3 - Since we now know the count of each prime number, you simply - write down that prime number as many times as you counted for it in step 2.

Here they are...2, 3, 5

Step #4 - The least common multiple is the product of all the prime numbers written down.

2 x 3 x 5 = 30

Therefore, the least common multiple of 5, 6 and 15 is 30.

So there you have it. A quick and easy method for finding least common multiples.

Highest Common Factor (abbreviated H.C.F.) of two natural numbers is the largest common factor (or divisor) of the given natural numbers. In other words, H.C.F. is the greatest element of the set of common factors of the given numbers.

H.C.F. is also called Greatest Common Divisor (abbreviated G.C.D.)

Example. Find the H.C.F. of 72, 126 and 270.

Solution. Using Prime factorisation method

72 = 2 x 2 x 2 x 3 x 3 = 2 ^{3} x 3^{2}

126 = 2 x 3 x 3 x 7 = 2 ^{1} x 3^{2} x 7^{1}

270 = 2 x 3 x 3 x 3 x 5 =

2^{1} x 3^{3} x 5^{1}

H.C.F. of the given numbers = the product of common factors with least index

= 2^{1} x 3^{2}

Using Division method

First find H.C.F. of 72 and 126

72|126|1

72

54| 72|1

54

18| 54| 3

54

0

H.C.F. of 72 and 126 = 18

Similarly calculate H.C.F. of 18 and 270 as 18

Hence H.C.F. of the given three numbers = 18

Co-prime numbers: Two natural numbers are called co-prime numbers if they have no common factor other than 1.

in other words, two natural numbers are co-prime if their H.C.F. is 1.

Some examples of co-prime numbers are: 4, 9; 8, 21; 27, 50.

Relation between L.C.M. and H.C.F. of two natural numbers

The product of L.C.M. and H.C.F. of two natural numbers = the product of the numbers.

Note. In particular, if Two natural numbers are co-prime then their L.C.M. = The product of the numbers.

QuestionS

Answer : Both ice cream trucks will visit Jeannette's neighborhood in 20 days and in 40 days. However, the problem asks: when is the next time both trucks will visit on the same day?, so the final answer is IN 20 DAYS

If a natural number is expressed as the product of prime numbers, then the factorisation of the number is called its prime (or complete) factorisation. First we list the multiples of each number. Q1. During the summer months, one ice cream truck visits Jeannette's neighborhood every 4 days and another ice cream truck visits her neighborhood every 5 days. If both trucks visited today, when is the next time both trucks will visit on the same day