CAT Question Bank - Co Primes



  • @rowdy-rathore 4
    2^(n-1) when n=3













  • 20 = 2^2 * 5
    So we need to find the numbers which does not have 2 or 5 as factors
    Numbers between 101 to 300 which are multiple of 2 = 200/2 = 100
    Numbers between 101 to 300 which are multiple of 5 = 200/5 = 40
    Now we need to find numbers which are multiple of both 2 and 5, as these numbers would be counted twice while counting the numbers divisible by 2 and 5
    Numbers between 101 and 300 which are multiple of 10 (both 2 and 5) = 200/10 = 20
    So total = 200 - (100 + 40 - 20) = 200 - 120 = 80



  • 630 = 2 * 3^2 * 5 * 7

    Numbers between 100 and 200 which are divisible
    by 2 = 51
    by 3 = 33
    by 5 = 21
    by 7 = 14
    Total = 119

    Now we need to find out the double counting cases and remove them.

    Numbers between 100 and 200 which are divisible
    by 2 * 3 = 17
    by 2 * 5 = 11
    by 2 * 7 = 7
    by 3 * 5 = 7
    by 3 * 7 = 5
    by 5 * 7 = 3
    by 2 * 3 * 5 = 3
    by 3 * 5 * 7 = 1
    by 2 * 5 * 7 = 1
    by 2 * 3 * 7 = 2
    by 2 * 3 * 5 * 7 = 0
    Total (to be removed) = 50 - 7 = 43

    So positive integers between 100 and 200 which are coprime to 630 = 101 - (119 - 43) = 25



  • Formula is 2^(n - 1) where n is the distinct primes in the factorized form of the number
    480 = 2^5 * 3 * 5
    3 distinct prime factors (2, 3 and 5)
    So 480 can be written as the product of 2 co prime numbers in 2^(3 - 1) = 4 ways.



  • If N = p1^a + p2^b + p3^c
    then ordered factor pairs coprime to each other = (2a + 1)(2b + 1)(2c + 1)
    Unordered factor pairs coprime to each other = {[(2a + 1)(2b + 1)(2c + 1) - 1]/2} + 1 (for (1,1)

    360 = 2^3 * 3^2 * 5
    Ordered factor pairs coprime to each other = (2 * 3 + 1) * (2 * 2 + 1) (2 * 1 + 1) = 7 * 5 * 3 = 105
    Un ordered factor pairs coprime to each other = (105 - 1)/2 = 52 + 1 = 53
    if we don't consider (1,1) then 52.
    Confused!

    Detailed approach (Hemanth Venkatesh)

    On factorizing 360 we get the following factors:
    360 = (2^3) * (3^2) * (5)
    First suppose that 5 divides neither co prime factor. Then we have two cases:
    Case 1: One factor must be 2 to some positive power while the other factor must be 3 to some positive power. Hence there are 3 * 2 = 6 of these (as there are 3 possible positive powers of 2 and there are 2 possible positive powers of 3).
    Case 2: One factor is 1 while the other factor is a divisor of (2^3) * (3^2).
    Hence there are (3+1)(2+1)=12 of these.

    Now, note that all of these pairs consist of different numbers except the pair {1,1}. For each of the pairs with two distinct elements, we can multiply either element by 5 to get two new co prime pairs of factors (that is the solution {a,b} gives rise to the solutions {5a,b} and {a,5b}.
    Finally, the pair {1,1} under this process only gives us one new pair: {1,5}.
    In conclusion, we have 3(6 + 12 − 1) + 2 = 53 co prime pairs.


Log in to reply