Problems on H.C.F and L.C.M


Factors and Multiples

If a number x divides another number y exactly (without leaving any remainder), then x is a factor of y and y is a multiple of x.

or

Factors  Set of numbers which exactly divides the given number.

Multiple  Set of numbers which are exactly divisible by the given number.

For example If the number is 8, then {8, 4, 2, 1} is the set of factors, while { 8, 16, 24, 32, ......} is the set of multiple of 8.

Note

  1. Factors of a number are always less than or equal to the given number.
  2. Multiples of a number are always more than or equal to the given number.

Common Multiple

A common multiple of two or more numbers is a number which is completely divisible (without leaving remainder) by each of them.

For example We can obtain common multiples of 3, 5 and 10 as follows

Multiple of 3

       = {3, 6, 9,12, 15, 18, 21, 24, 27, 30, 33 ....}

Multiples of 5 = { 5, 10, 15, 20, 25, 30 ,35, ....}

Multiples of 10 = { 10, 20, 30, 40, 50, 60, ....}

Common multiples of 3, 5 and 10
                            = { 30, 60, 90, 120 ....}


TIPS on cracking Aptitude Questions on LCM & HCF


Tip #1: Remember the basic formulae

1.    Least Common Multiple or LCM of A and B is the smallest number that can be divided by A or B without any reminder.

2.    Highest Common Factor or HCF (or GCD – Greatest Common Divisor) of A and B is the largest number that can divide A or B without any reminder.

3.    While determining the LCM or HCF, express the terms as products of prime numbers. For instance, let the terms be 15, 25 and 27. We can factorize these terms as:

a)    15 = 5 x 3

b)    25 = 52

c)    27 = 33

d)    HCF = 1  [no prime number is found across all three terms]

e)    LCM = 52 x 33          [we take the highest power for each prime number from the factorization results]

4.    Product of 2 numbers = LCM x HCF.     [This only holds for 2 terms]


Tip #2: Steps to calculate the LCM and HCF of fractions

1.    HCF of fractions = HCF of Numerator/ LCM of Denominator

Proof:

Let the fractions be a/b and c/d. Let the HCF be x/y.

The HCF is the highest possible number that divides both fractions without a reminder. Since we are looking for the highest possible number, we must try to maximize x and minimize y.

[a/b] [y/x] should have no reminder.

[c/d] [y/x] should have no reminder.

=>x is the HCF of a and c to ensure that x divides a and c both and is as large as possible

=>y is the LCM of b and d to ensure that y is divided by b and d both and is as small as possible.

2.    LCM of fractions = LCM of Numerator/ HCF of denominator

Proof:

Let the fractions be a/b and c/d. Let the LCM be x/y

The LCM is the smallest possible number that can be divided by both fractions without a reminder. Since we are looking for the smallest possible number, we must try to minimize x and maximize y.

[x/y] [b/a] should have no reminder.

[x/y] [d/c] should have no reminder.

=>x is the LCM of a and c to ensure that x is divided by both a and c and is as small as possible

=>y is the HCF of b and d to ensure that y divides both b and d and is as large as possible


Tip #3: Understand the concepts clearly to figure where to useHCF and where to use LCM

1.    Question: Find the greatest 4-digit number which is divisible by 15, 25, 40 and 75.

Solution: LCM of 15, 25, 40, 75 = 600. We need to find the largest 4 digit number divisible by 600.

Largest 4-digit number = 9999. Remainder on dividing 9999 by 600 = 399.

Thus, largest 4-digit number divisible by 15, 25, 40 and 75 = 9999 – 399 = 9600.

2.    Question: The ratio of two numbers is 3: 4 and their H.C.F. is 4. Find their LCM.

Solution: Let the numbers be 3x and 4x. HCF of 3 and 4 is 1. Therefore, HCF of 3x and 4x = x

=>    x = 4.      

=>   Thus, the numbers are 12 and 16. LCM = 48

3.    Question: A, B and C start at the same time in the same direction to run around a circular stadium. A completes a round in 252 seconds, B in 308 seconds and C in 198 seconds. After what time will they all meet again at the starting point, if they keep running in circles?

Solution: We need to find the time after which each of A, B and C would’ve completed full rounds.

=>   LCM of 252, 308, 198 = 2272 sec = 2272 / 60 minutes = 46 min 12 sec.

4.    Question: Six bells commence tolling together and toll at intervals of 2, 4, 6, 8 10 and 12 seconds respectively. In 30 minutes, how many times do they toll together?

Solution: The bells ring together after time equal to LCM of the intervals, i.e., 2, 4, 6, 8, 10, 12 sec.

LCM of 2, 4, 6, 8, 10, 12 = 120. Thus, the bells ring together after every 120 sec = 2 min.

In 30 minutes, they will together ring 30/2 + 1 = 16 times.

(Since at t = 0, the bells would ring together)


Tip #4: The smallest number which when divided by x, y and z leaves the same remainder R in each case= LCM(x, y, z) + R

Question: Find the smallest number which when divided by 5, 6, 7 and 8 leaves a remainder 3, but when divided by 9 leaves no remainder.

Solution:

The number must:

(i) Be a multiple of 9; (ii) leave a remainder of 3 when divided by 5, 6, 7 and 8.

LCM of 5, 6, 7 and 8 = 840.

Adding the remainder, the required number = (840 x t) + 3.

Now, smallest value of t for which (840 x t) + 3 is divisible by 9 = 2                [Trial and error]

Thus, the required number is (840 x 2) + 3 = 1683.


Tip #5: Largest number which divides x, y, z (x > y, y > z) to leave same remainder = HCF(x – y, y – z, x – z)

In case that the remainder is same and given, say R, the required number will be the HCF of x – R, y – R, z – R.

Similarly, the largest number which divides x, y and z to leave remainders a, b and c respectively is the HCF of x – a, y – b, z – c.

Question: Find the greatest number that will divide 183, 91 and 43 so as to leave the same remainder in each case.

Solution:

Let x be the greatest possible number such that it leaves the same reminder when it divides 183, 91 or 43.

Since the reminder is the same in each case, the difference of the terms must be exactly divisible by x. Also, x must the greatest possible number that exactly divides the difference between the terms.

Required number, x = HCF of (183 – 91, 91 – 43, 183 – 43) = HCF of (92, 48, 140) = 4