2IIM Quant Notes  HCF & LCM

rajesh_balasubramanian
Director, 2IIM Online CAT Preparation  IIT Madras  IIM Bangalore  CAT 100th percentile  CAT 2011, 2012 and 2014.
How many pairs of integers (x, y) exist such that the product of x, y and HCF (x, y) = 1080?
(a) 8
(b) 7
(c) 9
(d) 12We need to find ordered pairs (x, y) such that xy * HCF(x, y) = 1080.
Let x = ha and y = hb where h = HCF(x, y) => HCF(a, b) = 1.
So h^3(ab) = 1080 = (2^3)(3^3)(5).
We need to write 1080 as a product of a perfect cube and another number.Four cases:
h = 1, ab = 1080 and b are coprime. We gave 4 pairs of 8 ordered pairs (1, 1080), (8, 135), (27, 40) and (5, 216). (Essentially we are finding coprime a,b such that a*b = 1080).
h = 2, We need to find number of ways of writing (3^3) * (5) as a product of two coprime numbers. This can be done in two ways  1 and (3^3) * (5) , (3^3) and (5)
number of pairs = 2, number of ordered pairs = 4
h = 3, number of pairs = 2, number of ordered pairs = 4
h = 6, number of pairs = 1, number of ordered pairs = 2Hence total pairs of (x, y) = 9, total number of ordered pairs = 18.
The pairs are (1, 1080), (8, 135), (27, 40), (5, 216), (2, 270), (10, 54), (3, 120), (24, 15) and (6, 30). Choice (C)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?
(a) 2519
(b) 5039
(c) 1079
(d) 979LCM (5, 6, 7, 8, 9)  1 = 2519.
Choice (A)There are three numbers a,b, c such that
HCF (a, b) = l
HCF (b, c) = m
HCF (c, a) = n
HCF (l, m) = HCF (l, n) = HCF (n, m) = 1.
Find LCM of a, b, c. (The answer can be "This cannot be determined").a is a multiple of l and n. Also HCF (l,n) =1; => a has to be a multiple of ln, similarly b has to be a multiple of lm and c has to be a multiple of mn.
We can assume, a = lnx, b = lmy, c = mnz.
Now given that HCF(a, b) = l, that means HCF(nx, my) = 1.
This implies HCF(x, y) = 1 and HCF(m, x) = HCF(n, y) = 1.Similarly it can also be shown that HCF(y, z) = HCF(z, x) = 1 and others also.
So in general it can be written any two of the set {l, m, n, x, y, z} are coprime.
Now LCM(a, b, c) = LCM (lnx, lmy, mnz) = lmnxyz = abc/lmn.Quiet obviously, it is a reasonable assumption that a question in CAT will not be as tough as the last one here. However, it is a good question to get an idea of the properties of LCM and HCF.
How many pairs of positive integers x, y exist such that HCF of x, y = 35 and sum of x and y = 1085?
(a) 12
(b) 8
(c) 15
(d) 30Let 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 coprime integers that add up to 31. (Another way of looking at it is to find out integers less than 31 those are coprime 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 coprime to each other. Or, there are totally 15 pairs that satisfy this condition.
Choice (C).How many pairs of positive integers x, y exist such that HCF (x, y) + LCM (x, y) = 91?
(a) 10
(b) 8
(c) 6
(d) 7Let us consider x = h * a; y = h * b
a and b are coprime. So, LCM of (x, y) = h * a * bSo, 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 as 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. Choice (B).Sum of two numbers x, y = 1050. What is the maximum value of the HCF between x and y?
(a) 350
(b) 700
(c) 1050
(d) 525x = 525 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. Choice (D)
The sum of two non co–prime numbers added to their HCF gives us 91. How many such pairs are possible?
(a) 2
(b) 4
(c) 3
(d) 6Let 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 = 12h = 13
=> 1 + a + b = 7
=> a + b = 6Case 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)
Answer choice (c)There are 2 numbers such that a > b, HCF (a, b) = h and LCM (a, b) = l. What is the LCM of a – b and b?
(a) l
(b) (a  b) b
(c) (a  b) b / h
(d) h (a  b)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 / h6 different sweet varieties of count 32, 216, 136, 88, 184, 120 were ordered for a particular occasion. They need to be packed in such a way that each box has the same variety of sweet and the number of sweets in each box is also the same. What is the minimum number of boxes required to pack?
(a) 129
(b) 64
(c) 48
(d) 97All 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 = 2^3 = 8
Minimum number of boxes = (32 + 216 + 136 + 88 + 184 + 120) / 8 = 97

hi i am having a doubt regarding question 4 the doubt is that why we have not calculated ordered pair in this solution.