Test: LCM & GCD - 1 - GMAT MCQ

Before we start solving the question in hand, here are a couple of important concepts that we need to know.

Concept 1:

Product of two numbers is the same as the product of the LCM and HCF of those two numbers.

i.e., If the numbers are a and b, a * b = LCM (a, b) * HCF (a, b)

Note: a * b * c NEED NOT be equal to LCM(a, b, c) * HCF(a, b, c).

This rule works for 2 numbers, irrespective of whether the numbers are both integers, both fractions, one fraction and the other an integer.

Concept 2:

Let ‘h’ be the HCF of a and b and ‘L’ be the LCM of a and b.
a can be expressed as m*h and b can be expressed as n*h because h is a factor common to both the numbers.
a = mh and b = nh.

Note, m and n are co-prime (have no factor in common) because ‘h’ is the HCF of the two numbers. HCF of two numbers holds all factors common to both the numbers.Hence, we can deduce that the LCM (a, b), L = m*n*hi.e., the HCF of two numbers will be a factor of the LCM of the two numbers.

Data given in the question stem:

LCM of a and b is 1104 and their HCF is 4.

Statement I: a * b = 4416

Result 1 states that a * b = LCM (a, b) * HCF (a, b).

So, a * b = 1104 * 4 = 4416.

Statement I is true.

Statement II: a and b are both divisible by 8

The HCF of a and b is 4. So, the largest number that could divide both a and b is 4.

If 8 could divide both a and b, the largest number that could divide both would have been 8.

Consequently, the HCF of the two numbers would have been 8 and not 4.

So, statement II is NOT true.

Statement III: a : b = 48 : 23 or a : b = 23 : 48

Result 2 comes in handy to evaluate statement III.

If L is the LCM(a, b) and h is the HCF(a, b), L = m * n * h.

Where a = mh and b = nh and m and n are co-prime.

We have to determine whether a : b = 48 : 23 or 23 : 48.

i.e., we have to determine whether m : n = 48 : 23 or 23 : 48.

Because L = m * n * h, 1104 = m * n * 4

Or m * n = 1104/4 = 276

Note: m and n are co-prime.

If m and n are 48 and 23 or vice versa, m * n = 1104 and not 276.

Statement III is NOT true.

Note: When a number is divided by 8, a remainder of 7 can be thought of as a remainder of -1.
This idea is very useful in a bunch of questions. So, N = 5a - 1 or N + 1 = 5a

N = 6b - 1 or N + 1 = 6b
N = 7c - 1 or N + 1 = 7c
N = 8d - 1 or N + 1 = 8d
N = 9e - 1 or N + 1 = 9e
N + 1 can be expressed as a multiple of (5, 6, 7, 8, 9)

N + 1 = 5a*6b*7c*8d*9e 
Or N = (5a*6b*7c*8d*9e) - 1 

Smallest value of N will be when we find the smallest common multiple of (5, 6, 7, 8, 9) or LCM of (5, 6, 7, 8, 9) 
N = LCM (5, 6, 7, 8, 9) - 1 = 2520 - 1 = 2519.
The question is "Find the smallest number that leaves a remainder of 4 on division by 5, 5 on division by 6, 6 on division by 7, 7 on division by 8 and 8 on division by 9?"

Hence the answer is "2519"

Let HCF of (x, y) be h. Then we can write x = h * a and y = h * b.
Furthermore, note that HCF (a, b) = 1. This is a very important property. One that seems obvious when it is mentioned but a property a number of people overlook.

So, we can write x = 35a; y = 35b

x + y = 1085 => 35(a + b) = 1085. => (a + b) = 31. We need to find pairs of co-prime integers that add up to 31. (Another way of looking at it is to find out integers less than 31 those are co-prime with it or phi(31) as had mentioned. More on this wonderful function in another post).

Since 31 is prime. All pairs of integers that add up to 31 will be co-prime to each other. Or, there are totally 15 pairs that satisfy this condition.

The question is "How many pairs of positive integers x, y exist such that HCF of x, y = 35 and sum of x and y = 1085?"

Hence the answer is "15"

Let us x = h * a; y = h * b
a and b are co-prime. So, LCM of (x, y) = h * a * b

So, in essence h + h * a * b = 91. Or h(ab + 1) = 91
Now, 91 can be written as 1 * 91 or 7 * 13
Or, we can have HCF as 1, LCM as 90 - 
There are 4 pairs of numbers like this (2, 45), (9, 10), (1, 90) and (5, 18)

We can have HCF as 7, ab + 1 = 13 => ab = 12 => 1 * 12 or 4 * 3

Or, the pairs of numbers are (7, 84) or (21, 28)

The third option is when HCF = 13, ab + 1 = 7 => ab = 6
Or (a, b) can be either (1, 6) or (2, 3)
The pairs possible are (13, 78) and (26, 39)
There are totally 8 options possible - (2, 45), (9, 10), (1, 90), (5, 18), (7, 84), (21, 28), (13, 78) and (26, 39).
8 Pairs.

The question is "How many pairs of positive integers x, y exist such that HCF (x, y) + LCM (x, y) = 91?"

Hence the answer is "8 pairs"

x = 525 and y = 525 works best.
If the question states x, y have to be distinct, then the best solution would be x = 350, y = 700, HCF = 350.
So the HCF is 525.
The question is "What is the maximum value of the HCF between x and y?"
Hence the answer is "525"

Let HCF of the numbers be h. The numbers can be taken as ha + hb, where a, b are coprime. 
h + ha + hb = 91 
h(1 + a + b) = 91 
h ≠ 1 
h = 7
⇒ 1 + a + b = 13 a + b = 12 

h = 13
⇒ 1 + a + b = 7 
⇒  a + b = 6 

Case 1: h = 7, a + b = 12 
(1, 11), (5, 7) => Only 2 pairs are possible as a, b have to be coprime. 

Case 2: h = 13, a + b = 6 
(1, 5) only one pair is possible as a, b have to be coprime.

Overall, 3 pairs of numbers are possible – (7, 77) (35, 49) and (13, 65)

The question is "How many such pairs are possible?"

Hence the answer is "3 Pairs"

Product of 2 numbers = LCM * HCF.
Given a > b, HCF = h, LCM = l
From the above we can say, HCF of (a – b, b) = h

LCM x HCF = Product of 2 numbers
(a – b)b = h x LCM 
LCM = (a - b) b / h

The question is "What is the LCM of a – b and b?"

Hence the answer is "(a - b) b / h"

All sweets need to packed and each box has the same variety.
This implies the number of sweets in each box should be HCF of different count of sweets
HCF of 32, 216, 136, 88, 184, 120 = 23 = 8
Minimum number of boxes = (32 + 216 + 136 + 88 + 184 + 120) / 8 = 97

The question is "What is the minimum number of boxes required to pack?"

Hence the answer is "97 boxes"

16 in a row --> 12 left 
24 in a row --> 20 left 
25 in a row --> 21 left 
30 in a row --> 26 left 

In all the 4 cases above, the remainder is 4. 
(16 – 12) = (24 – 20) = (25 – 21) = (30 – 26) 

Hence the required students = LCM (16, 24, 25, 30 ) – 4 
= 1200 – 4 
= 1196

The question is "What is the minimum number of students present in the school?"

Hence the answer is "1196 students minimum"

Correct Answer :- B

Explanation : We know, 935 = 5*11*17

Let p = hx

q = hy

Where h is the hcf of p and q.

Therefore, lcm of p and q= hxy

We have lcm = 935.

hxy = 935

If h = 1,

Then p = 935

q = 1

Sum of digits of q = 1

If h = 5,

p = 5*17 = 85

q = 5*11 = 55

Sum of digits of q = 10

If h = 11,

p = 11*17 = 187

q = 11*5 = 55

Sum of digits of q = 10

If h = 17,

p = 17*11 = 187

q = 17*5 = 85

Sum of digits of q = 13

Maximum possible sum of digits of q = 13