Question

Arun selected an integer $x$ between 2 and 40, both inclusive. He noticed that the greatest common divisor of the selected integer $x$ and any other integer between 2 and 40, both inclusive, is 1. How many different choices for such an $x$ are possible?

Accepted Answer

A. For $\gcd(x, y) = 1$ for ALL $y \in [2, 40]$ with $y 
eq x$, $x$ must not share any prime factor with any other integer in $[2, 40]$. This means $x$ must be a prime number $p$ such that no multiple of $p$ exists in $[2, 40]$. That requires $2p > 40 \implies p > 20$. The prime numbers between 20 and 40 are 23, 29, 31, and 37. There are 4 such choices.

Co-prime Number Selection in Range

Explanation

Practise this under exam conditions