Co-prime Integer Selection Count

XAT 2025 · Quantitative Ability & Data Interpretation · Medium · Number System

Arun selected an integer xx between 2 and 40, both inclusive. He noticed that the greatest common divisor of the selected integer xx and any other integer between 2 and 40, both inclusive, is 1.

How many different choices for such an xx are possible?

  1. A.

    4

  2. B.

    8

  3. C.

    1

  4. D.

    12

  5. E.

    0

Answer

A

Explanation

For gcd⁡(x,y)=1\gcd(x, y) = 1 for ALL y∈[2,40]∖{x}y \in [2, 40] \setminus \{x\}, xx must have no common prime factor with any other number in the set [2,40][2, 40]. Therefore, xx must be a prime number pp such that its smallest multiple 2p>40  ⟹  p>202p > 40 \implies p > 20. The prime numbers in [20,40][20, 40] are: 23, 29, 31, 37. Thus, there are 4 such possible choices for xx.

Related Number System questions

Practise this under exam conditions

Sign in to solve it with a live timer, the on-screen CAT calculator, and streak and accuracy tracking across every question you attempt.

Solve in the workspace