Home » Blog » Concepts of Co-primes for CAT Exam with Solved Examples and Explanations

Concepts of Co-primes for CAT Exam with Solved Examples and Explanations

Friday, July 31st, 2020

---

Concepts of Co-primes:

Co-primes are those numbers which do not have any common factors between them. For e.g. 4,9,77, are co-primes as they don’t have any common factors.

Note: Co-primes will not always be prime nos. 64 and 27 are co-primes but not prime numbers.

There are three types of questions based on co-primes:

1. Number of ways of writing a number as a product of two co-primes

If N=ap .bq .cr …….., then, the number of ways of writing N as a product of 2 co-primes is 2n-1, where ‘n’ is the number of distinct prime factors of the given number N.
Let’s understood it by a simple question:

Ques: Find the number of ways of writing 48 as a product of two co-primes?

Sol: 48, which is 24 x 31 , the value of ‘n’ is 2 because only 2 distinct prime factors (2&3) are involved.
Hence, the number of ways = 22-1 =2 i.e. 48 can be written as a product of 2 co-primes, in two different ways. They are (1, 48) and (3, 16).

2. Number of co-primes to N, that is less than N

If N is a number that can be written as ap .bq .cr …….., then, the number of co-primes of N, which are less than N, represented by ϕ (N) is,
N(1- 1/a ) (1- 1/b ) (1- 1/c )…………………

For e.g., if 48, is considered,
N= N=ap .bq .cr ……. i.e. 48=24. 31.

Hence, a=2, b=3, p=4, q=1.

ϕ (48) = 48(1- 1/2 ) (1- 1/3 )
= 48 x  1/2  x  1/3
=16

Note: If numbers less than 48 are listed, and co-primes to 48 are spotted, the count of co-primes will be 16.

3. Sum of co-primes to N that less than N

The sum of the co-primes of N, that less than N is N/2. ϕ (N). If we consider the above example, already we have ϕ (48) = 16.

Hence, sum of co-primes of 48 that are less than 48 = N/2. ϕ (N) = 48/2 x 16 = 384.

Let’s solve some advanced questions on Co-primes:

1. How many integers from 101 to 300 are co-prime to 20?

Sol: 20= 2² x 5

So we need to find the numbers which do 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 multiples 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
Hence, 80 is the answer.

2. How many positive integers between 100 and 200 are co-prime to 630?

Sol: 630 = 2 * 3² * 5 * 7

Numbers between 100 and 200 which are divisible by 2 = 51
Numbers between 100 and 200 which are divisible by 3 = 33
Numbers between 100 and 200 which are divisible by 5 = 21
Numbers between 100 and 200 which are divisible 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 co-prime to 630 = 101 – (119 – 43) = 25
Hence, 25 is the answer.

3. In how many ways in which 480 can be written as the product of two numbers which are coprime to each other?

Sol: Formula is 2^{(n – 1)} where n is the distinct primes in the factorized form of the number
480 = 2⁵ * 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.

4. How many factor pairs of N = 360 will be co-prime to each other?

Sol: On factorizing 360 we get the following factors:
360 = (23) * (32) * (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.

5. How many three digit numbers less than 200 are co-prime to 638?

Sol: 638 =2 * 11 * 29

3 digit numbers less than 200 divisible by 2 = 50
3 digit numbers less than 200 divisible by 11= 9
3 digit numbers less than 200 divisible by 29=3

Total= 62

Now on taking pairs:

3 digit numbers less than 200 divisible by 2*11=5
3 digit numbers less than 200 divisible by 2*29=2
3 digit numbers less than 200 divisible by 11*29=0

Hence answer is 100- (62-7) = 45

6. If N is a natural number < 100, then for how many values of N are the numbers 6N + 1 and 15N + 2 are relatively prime?

Sol: Suppose 6N + 1 and 15N + 2 are not relatively prime.

Let P is a prime dividing both of them.
Then P also divides 5(6N + 1) and 2(15N + 2) so P divides 30N + 5 and 30N + 4.
Hence P divides the difference (30N + 5) – (30N + 4) = 1.

Now 1 is not divisible by any other number, i.e. it contradicts our conditions.
So the pair 6N + 1 and 15N + 2 are relatively prime for all values of N.

Other posts related to Quantitative Aptitude – Number Systems

Divisibility Rules for CAT Quantitative Aptitude Preparation
Determining the second last digit and the last two digits
Baisc Idea of Remainders
Factor Theory
How to Find Number of Trailing Zeros in a Factorial or Product
Dealing With Factorials
Lowest Common Multiple (LCM) for CAT Exam
Concepts of HCF for CAT Exam with Solved Examples

CAT Questions related to Quantitative Aptitude – Number Systems

All questions from CAT Exam Quantitative Aptitude – Number Systems
Quantitative Aptitude – Number Systems – Q1: If the product of three consecutive positive integers is 15600 then the sum of the squares of these integers is
Quantitative Aptitude – Number Systems – Q2: If a, b, c are three positive integers such that a and b are in the ratio 3 : 4 while b and c are in the ratio 2:1, then which one of the following is a possible value of (a + b + c)?
Quantitative Aptitude – Number Systems – Q3: The numbers 1, 2,…,9 are arranged in a 3 X 3 square grid in such a way that each number occurs once and the entries along each column, each row, and each of the two diagonals add up to the same value.

---