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

78

60

53

44

61

32

64

61