HCF & LCM

H.C.F and L.C.M

Factors and Multiples:

If a number `a' divides another number `b' exactly, then we say that `a' is a factor of `b' and that `b' is a multiple of `a'.

eg. 2 is a factor of 12 and therefore 12 is a multiple of 2.

Least Common Multiple (L.C.M.)

L.C.M. is the least non-zero number in common multiples of two or more numbers.

Multiple of 6 =  6, 12, 18, 24, 30, ....

Multiple of 8 =  8, 16, 24, 32, 40, ........

Common Multiple of 6 and 8 = 24, 48

Least Common Multiple = 24

Factorisation Method:

Q-Find the L.C.M. of 12, 27 and 40 ?

Factors of 12 = 2 * 2*3

Factors of 27 = 3 *3*3

Factors of 40 = 2*2*2*5

L.C.M = 2*2*2*3*3*3*5 = 1080

SHORT CUT METHOD

(Division Method)

Q-Find the L.C.M. of 12, 27, 40 ?

2      12,27,40

2       6,27,20

3       3,27,10

         1,9,10

 L.C.M = 2*2*3*9*10 = 1080

HIGHEST COMMON FACTOR (H.C.F)

The highest common factor of two or more numbers is the greatest number which divides each of them exactly.

Q- Find the H.C.F. of  24 , 56 ?

Factors of 24 = 1, 2, 3, 4, 6, 8, 12, 24

Factors of 56 = 1, 2, 4, 7, 8, 14, 28, 56

Common factors of 24 and 56 are 1, 2, 4, 8

H.C.F. of 24 and 56 = 8

Factorisation Method:

H.C.F. can be found by resolving the given numbers into prime factors and then taking the product of least powers of all common factors, that occur in these numbers.

Q- Find H.C.F. of 48, 108, 140 ?

Factors of 48 = 2*2*2*2*3                                                                                                                                                       Factors of 108 = 2*2*3*3*3

Factors of 140 = 2*2*5*7

H.C.F. = 2*2 = 4

HCF OF GIVEN FRACTIONS:

H.C.F of given fractions = HCF of numerator/LCM of denominator

Example 1:  Find the H.C.F of 4/9 ,16/15 , 12/21 ?

Solution:

According to the formula, H.C.F of numerators 4, 16, 12

4 = 2x2

16=2x2x2x2

12=2x2x 3

So, the H.C.F of numerators = 4

L.C.M of denominators 9, 15, 21

9 = 3x3

15= 3x5

21= 3x7

So, the L.C.M of denominators = 3*3 *5*7 = 315

Therefore, H.C.F of given fractions= 4/315

L.C.M OF GIVEN FRACTIONS:

L.C.M of given fractions =  LCM of numerator/HCF of denominator

Example 2:   Find the L.C.M of the fractions 2/3,  7/18 , 11 /12?

Solution:

According to the formula, L.C.M of numerators 2, 7, 11.

 As the numerators are all prime numbers, L.C.M of numerators = 2*7*11 = 154

H.C.F of denominators 3, 18, 12

3=3

18=3*3*2

12=2*2*3

So, H.C.F of denominators 3, 18, 12 = 3

Therefore, L.C.M of given fractions = 154/3 

The product of two given numbers is equal to the product of their H.C.F. and L.C.M.

Example 3:   The L.C.M. of two number is 2310. Their H.C.F. is 30. If one number is 210, the other number is

Solution:

The other number =  (L.C.M * H.C.F ) / given number = (2310 * 30) / 210 = 330

Type: The greatest number which divides x, y and z to leave the remainder R is H.C.F of (x – R), (y – R) and (z – R).

Example 4: Find the greatest number divides 24, 60, and 84 leaves the remainder 3?

Solution:

By definition the greatest number which divides the given numbers and leaves a remainder of 0, only if it is the H.C.F of given numbers

x = 24, y = 60, z = 84 and R = 3

H.C.F of (x - R), (y - R), (z - R) = H.C.F of 21, 57, 81

21= 3*7

57 =3*19

81 = 3*3*3*3

So, H.C.F of 21, 57, 81 =3.

 Therefore the greatest number is 3 which divide 24, 60 and 84 to leave a remainder 3

Type:  The greatest number which divide x, y, z to leave remainders a, b, c is H.C.F of (x - a), (y - b) and (z - c).

Example 5: Find the greatest number which divides 18, 26 and 54 to leave remainders 3, 1, 4?

Solution:

Here, x = 18, y = 26, z = 54, a = 2, b = 1, c = 4

H.C.F of (x - a), (y - b), (z - c) = H.C.F of 15, 25, 50

 15= 5*3

 25= 5*5

 50= 2*5 *5

So, H.C.F of 15, 25, 50 = 5, we can cross check by dividing x, y, z and obtain the same remainders as mentioned in question.

Type: The smallest number which when divided by x, y and z leaves remainder of a, b, c (x – a), (y - b), (z - c) are multiples of K

Required number = (L.C.M of x, y and z) – K

Example 6: Find the Smallest number which divides 2, 5, 7 to leave remainders 0, 3, 5?

Solution:

Here, x = 2, y = 5, z = 7, a = 0, b = 3, c = 5

 (x - a), (y - b), (z - c) = 2, 2, 2

Therefore, K = 2

L.C.M of x, y, and z = 2 * 5 * 7 = 70

 Required number = (L.C.M of x, y and z) – K = 70 -2 =68

Example 7: What is the least number which when divided by 8,9,12 and 15 leaves the same remainder 1 in each case ?

Solution:

Required number = ( l.c.m of 8,9,12,15)+1 = 361

Example 8:The traffic lights at three different road crossings change after every 48 sec, 72 sec and 108 sec respectively. If they all change simultaneously at 8 : 20 : 00 hours, then they will again change simultaneously at?

Solution:

Interval of change = (l.c.m of 48,72,108) = 432 sec. The lights will change simultaneously after every 432 seconds . Next simultaneous change will take place at 8:27:12 hrs.

Finding last digit of any power

FINDING LAST DIGIT OF ANY POWER:

Last digits of the powers of any number follow a cyclic pattern. If we find out after how many steps the last digit of the powers of a number repeat then we can find out the last digit of any power of any number. Let us check out the pattern of last digits for different digits:

1	1
2	2	4	8	6
3	3	9	7	1
4	4	6
5	5
6	6
7	7	9	3	1
8	8	4	2	6
9	9	1

No. ending with 1:

Any power on number ending with 1 will have unit digit 1.

Ex: 251³⁵ will have unit digit 1.

No. ending with 2:

Last digit of 2¹ is2

Last digit of 2² is 4

Last digit of 2³ is 8

Last digit of 2⁴ is 6

Last digit of 2⁵ is again 2

And the whole cycle is repeated

So there are only 4 possible unit digits in case of 2. These are 2,4,8,6.

Ex: Find the unit digit of 2⁹⁸.

Since, in case of 2, there are 4 possible unit digits as explained above. So the cyclicity is 4.

Now we will divide the power by 4 (cyclicity is 4) and check the remainder.

When 98 is divided by 4 remainder is 2. The unit digit is same as that of 2² which is 4.

No. ending with 3:

Last digit of 3¹ is3

Last digit of 3² is 9

Last digit of 3³ is 7

Last digit of 3⁴ is 1

Last digit of 3⁵ is again 3

And the whole cycle is repeated

So there are only 4 possible unit digits in case of 3. These are 3,9,7,1.

Ex: Find the unit digit of 3⁷³.

Since, in case of 3, there are 4 possible unit digits as explained above. So the cyclicity is 4.

Now we will divide the power by 4 (cyclicity is 4) and check the remainder.

When 73 is divided by 4 remainder is 1. The unit digit is same as that of 3¹ which is 3.

No. ending with 4:

Last digit of 4¹ is4

Last digit of 4² is 6

Last digit of 4³ is 4

Last digit of 4⁴ is 6

So in case if 4, there are only 2 possible unit digits which are 4,6

We can also say that

Unit digit of 4^{odd no}=4

Unit digit of 4^{even no}=6

No. ending with 5:

Last digit of 5¹ is 5

Last digit of 5² is 5

Last digit of 5³ is 5

Last digit of 5⁴ is 5

Unit digit in case of 5 is 5 only.

No. ending with 6:

Last digit of 6¹ is 6

Last digit of 6² is 6

Last digit of 6³ is 6

Last digit of 6⁴ is 6

Unit digit in case of 6 is 6 only.

No. ending with 7:

Last digit of 7¹ is 7

Last digit of 7² is 9

Last digit of 7³ is 3

Last digit of 7⁴ is 1

Last digit of 7⁵ is again 7

And the whole cycle is repeated

So there are only 4 possible unit digits in case of 7. These are 7,9,3,1.

Ex: Find the unit digit of 7¹⁵⁶.

Since, in case of 7, there are 4 possible unit digits as explained above. So the cyclicity is 4.

Now we will divide the power by 4 (cyclicity is 4) and check the remainder.

When 156 is divided by 4 remainder is 0. The unit digit is same as that of 7⁴ which is 1.

No. ending with 8:

Last digit of 8¹ is 8

Last digit of 8² is 4

Last digit of 8³ is 2

Last digit of 8⁴ is 6

Last digit of 8⁵ is again 8

And the whole cycle is repeated

So there are only 4 possible unit digits in case of 8. These are 8,4,2,6.

Ex: Find the unit digit of 8⁵⁵.

Since, in case of 8, there are 4 possible unit digits as explained above. So the cyclicity is 4.

Now we will divide the power by 4 (cyclicity is 4) and check the remainder.

When 55 is divided by 4 remainder is 3. The unit digit is same as that of 8³ which is 2.

No. ending with 9:

Last digit of 9¹ is9

Last digit of 9² is 1

Last digit of 9³ is 9

Last digit of 9⁴ is 1

So in case if 4, there are only 2 possible unit digits which are 9,1

We can also say that

Unit digit of 9^{odd no}=9

Unit digit of 9^{even no}=1

Ques: Find the unit digit of 152⁵⁵⁵x 999¹⁰⁰⁰

Ans. Since we are talking about unit digit we will take 2 in place of 152(unit digit)

And 9 in place of 999

Unit digit of 2⁵⁵⁵: divide the power by 4(cyclicity in case of 2) and check the remainder

555 gives remainder 3 when divided by 4. So unit digit is same as that of 2³ which is 8

Unit digit of 9¹⁰⁰⁰:  We know that Unit digit of 9^{even no}=1

So unit digit of 9¹⁰⁰⁰ is 1

Required unit digit is 8 x 1 =8

Divisibility Rules

DIVISIBILITY RULES

A divisibility rule is a shorthand way of determining whether a given number is divisible by a fixed divisor without   performing the division, usually by examining its digits. It also tells us the remainder we get when a number is divided by a given number

1.Divisibility by 2ⁿ : If the last n digits of the number is divisible by 2ⁿ, then the number is divisible by 2ⁿ.

                a. 2¹ – For 2, we check the last digit. Last digit should be divisible by 2. The last digit is even (0, 2, 4, 6, or 8)

                b. 4 - 4 can be written as 2². So divisibility rule of 4 says check the last 2 digits. If the last 2 digits of a number is divisible by 4 then the whole number is divisible by 4.

                c. 8 - 8 can be written as 2³. So divisibility rule of 8 says check the last 3 digits. If the last 3 digits of a         number is divisible by 8 then the whole number is divisible by 8.

Ex.  953360  is  divisible  by  8,  since  the  number  formed  by  last  three  digits  is  360,  which  is divisible by 8. But, 529418 is not divisible by 8, since the number formed by last three digits is 418, which is not divisible by 8.

               d. 16 - 16 can be written as 2⁴. So divisibility rule of 16 says check the last 4 digits. If the last 4 digits of a         number is divisible by 16 then the whole number is divisible by 16.

               So, this divisibility rule is applicable for all the powers of 2.

                So we now have the divisibility rule for 2,4,8,16,32,64,128,256,512,.......

            2. Divisibility rule of 3 and 9

             A number is divisible by 3, if the sum of its digits is divisible by 3.

             A number is divisible by 9, if the sum of its digits is divisible by 9.
            Ex.592482 is divisible by 3, since sum of its digits =(5+9+2+4+8+2)=30, which is divisible by 3.
             But, 864329 is not divisible by 3, since sum of its digits =(8+6+4+3+2+9)=32, which is not divisible by 3.

Ex. 60732 is divisible by 9, since sum of digits =(6+0+7+3+2)=18, which is divisible by 9.
But, 68956 is not divisible by 9, since sum of digits =(6+8+9+5+6)=34, which is not divisible by 9.

3. Divisibility rule of 5ⁿ: If the last n digits of the number is divisible by 5ⁿ, then the number is divisible by 5ⁿ.

   5 - A number is divisible by 5, if its unit's digit is either 0 or 5. Thus, 20820 and 50345 are divisible by 5, while 30934 and 40946 are not.

25 – Can be written as 5². So for 25, we check the last 2 digits. If the last 2 digits of a number is divisible by 25 then the complete number is divisible by 25.

125 - Can be written as 5³. So for 125, we check the last 3 digits. If the last 3 digits of a number is divisible by 125 then the complete number is divisible by 125.

625 - Can be written as 5⁴. So for 625, we check the last 4 digits. If the last 4 digits of a number is divisible by 625 then the complete number is divisible by 625.

So, this divisibility rule is applicable for all the powers of 5.

So we now have the divisibility rule for 5,25,125,625,3125,.......

4. Divisibility rule of 7: To find out if a number is divisible by seven, take the last digit, double it, and subtract it from the rest of the number. Repeat the process till we get a 3 digit number. If the number is divisible by 7 (including zero), then the original number is divisible by 7.

5. Divisibility By 10:

A number is divisible by 10, if it ends with 0.Ex. 96410, 10480 are divisible by 10, while 96375 is not.

6.   Divisibility By 11:

A number is divisible by 11, if the difference of the sum of its digits at odd places and the sum of its digits at even places, is either 0 or a number divisible by 11.
Ex. The number 4832718 is divisible by 11, since :(sum of digits at odd places) - (sum of digits at even places) =
=(8+7+3+4)−(1+2+8)=11, which is divisible by 11.

7. Divisibility Rule of 13: To find out if a number is divisible by 13, take the last digit, double it, and add it to the rest of the number. Repeat the process till we get a 3 digit number. If the number is divisible by 13 (including zero), then the original number is divisible by 13

8. Divisibility by 17 : Subtract five times the last digit from the remaining leading truncated number. If the result is divisible by 17, then so was the first number. Apply this rule over and over again as necessary.
Example: 3978-->397-5*8=357-->35-5*7=0. So 3978 is divisible by 17.

9. Divisibility by 19: Add two times the last digit to the remaining leading truncated number. If the result is divisible by 19, then so was the first number. Apply this rule over and over again as necessary.
EG: 101156-->10115+2*6=10127-->1012+2*7=1026-->102+2*6=114 and 114=6*19, so 101156 is divisible by 19.

10. Divisibility by composite numbers:

Find two coprime factors of the composite number and the apply the divisibility rule of these factors.

Ex- 6 = 2 x 3. So a number is divisible by 6 if it is divisible by both 2 and 3

12= 3x4. So a number is divisible by 12 if it is divisible by both 3 and 4

18=2x9. So a number is divisible by 18 if it is divisible by both 2 and 9

48= 16x3. So a number is divisible by 48 if it is divisible by both 16 and 3

72= 8x9. So a number is divisible by 72 if it is divisible by both 8 and 9