The total number of 3-digit numbers, whose greatest common divisor with 36 is 2, is ___________.

Solution

Maths sir · 4 steps

Break 36 into 2² × 3²: the number needs exactly one factor of 2 and no factor of 3.

1. Read the condition. Since 36 = 2² × 3², gcd(n, 36) = 2 means n is even, n is not divisible by 4, and n is not divisible by 3. The first two together say n ≡ 2 (mod 4).
2. Count the candidates. The 3-digit numbers with n ≡ 2 (mod 4) are 102, 106, …, 998. That is (998 - 102)/4 + 1 = 225 numbers.
3. Remove multiples of 3. A number that is 2 mod 4 and divisible by 3 is 6 mod 12. These are 102, 114, …, 990, which gives (990 - 102)/12 + 1 = 75 numbers.

   225 - 75 = 150

4. So. There are 150 three-digit numbers whose gcd with 36 is 2.

The common slip: 225. Forgetting to throw out the multiples of 3 gives 225, the count of numbers that are 2 mod 4, not 150.

The idea to keep. For a gcd condition, factorise the fixed number into primes. Each prime then tells you exactly what power the unknown number must or must not contain.

Answer from the NTA final answer key. Solution by PrepWiser.