HCF and LCM

Prime Factorization:

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 = 24 x 3(ii) 420 = 2 x 2 x 3 x 5 x 7 = 22 x 3 x 5 x 7

Highest Common Factor(H.C.F) or Greatest Common Meaure(G.C.M) or Greatest Common Divisor(G.C.D) :

The H.C.F of two or more than two numbers is the greatest number that divides each of them exactly.
There are two methods :


Method 1 - Factorization method: Express each one of the given numbers as the product of prime factors.

The product of least powers of common prime factors gives HCF.

Example : Find HCF of 2⁶ * 3²*5*7⁴ , 2² *3⁵*5² * 7⁶ , 2²*5 *7²

Sol: The prime numbers given common numbers are 2,5,7

Therefore HCF is 2² * 5 *7² .


Method 2- Division Method : Divide the larger number by smaller one. Now divide the divisor by remainder. Repeat the process of dividing preceding number last obtained till zero is obtained as
number. The last divisor is HCF.


Example: Find HCF of 513, 1134, 1215


Sol:

1134) 1215(1
1134
----------
81)1134(14
81
-----------
324
324
-----------
0
-----------
HCF of this two numbers is 81.

81)513(6
486
--------
27)81(3
81
-----
0
---

HCF of 81 and 513 is 27.

Least common multiple[LCM] : The least number which is divisible by each one of given numbers is LCM.
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.

 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.
Important
For LCM
1. LCM >= the largest number of a set.
2. For Co-prime numbers - LCM is product of co-prime numbers.
3. LCM is multiple of all the numbers of a set as well as HCF of a set of numbers.


For HCF
1. HCF =< the largest number of a set.
2. For Co-prime numbers - HCF is equals to 1.
3. HCF is factor of all the numbers of a set as well as LCM of a set of numbers.