2IIM Quant Notes - HCF & LCM


  • 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) 12

    We 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 co-prime. We gave 4 pairs of 8 ordered pairs (1, 1080), (8, 135), (27, 40) and (5, 216). (Essentially we are finding co-prime 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 co-prime 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 = 2

    Hence 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) 979

    LCM (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 co-prime.
    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) 30

    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.
    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) 7

    Let us consider 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 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) 525

    x = 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.

    1. 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) 6

    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)
    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 / h

    6 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) 97

    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 = 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.


Log in to reply
 

Looks like your connection to MBAtious was lost, please wait while we try to reconnect.