Problem Solving

hey_thr67 wrote:How many numbers are co-prime to 2304 and lie between 1000 and 2000 ?

1: 500
2: 332
3: 333
4: 334
5: None of the above

Two integers a and b are said to be co-prime or relatively prime if the only positive integer that evenly divides both of them is 1. This means gcd(a, b) = 1.

2304 = 2^8 * 3^2

We have to find all integers, which are not multiples of 2 and 3.

Now, number of integers between 1000 and 2000, inclusive = (2000 - 1000) + 1 = 1001
Out of 1001 integers, 501 will be even integers. We are left with 500 integers, out of which every 3rd integer will be divisible by 3.
So, 500/3 = 166 integers are divisible by 3.

Therefore, number of integers, which are not multiples of 2 and 3 = 1001 - (501 + 166) = 334
So, 334 numbers are co-prime to 2304.

The correct answer is D.