S Is 10 Distinct Primes, A = Products of Two or More Elements, Find n(P)

JEE Main 2025 — 24 January, Morning Shift. Previous Year Question.

Problem

Let $S$ be a set of $10$ distinct primes, and let $A$ be the set of products of two or more elements from $S$. If $P = \{(x,y): x \in S \text{ and } y \in A \text{ and } y \text{ is divisible by } x\}$, then $n(P)$ is equal to:

Key insight. Because the elements of $S$ are distinct primes, a product of any subset of them is divisible by exactly the primes that were multiplied into it — nothing more, nothing less. So “count pairs $(x,y)$ with $x\mid y$” quietly becomes “for each fixed prime $x$, count subsets of size $\geq2$ that include $x$” — a much simpler counting problem than it first looks.

Watch this explained step by step →  ·  More on the Shiwam’s Classes channel

Approach

Fix one prime $x \in S$ at a time. Since every element of $A$ is a squarefree product of distinct primes from $S$, $x$ divides such a product $y$ exactly when $x$ itself was one of the primes multiplied together to form $y$. So the count for a fixed $x$ is just the number of subsets of the remaining nine primes that, together with $x$, form a valid product (size $\geq 2$). Summing this count over all $10$ choices of $x$ gives $n(P)$.

Solution

Step 1 — Fix a prime x and count valid y’s

Let $x$ be one of the $10$ primes in $S$. Any $y \in A$ divisible by $x$ must be a product of a subset $T \subseteq S$ with $x \in T$ and $|T| \geq 2$. Writing $T = \{x\} \cup R$ where $R$ is a subset of the other $9$ primes, the condition $|T|\geq 2$ just means $R$ is non-empty.

Step 2 — Count the non-empty subsets of the remaining 9 primes

The other $9$ primes have $2^9$ subsets in total, including the empty one. Excluding the empty subset (which would make $T=\{x\}$, a single prime — not “two or more”):

$$\text{Valid } y\text{‘s for this } x = 2^9 – 1 = 511$$

Step 3 — Sum over all 10 choices of x

This count of $511$ is the same for every choice of $x \in S$, since the argument didn’t depend on which specific prime $x$ was. With $10$ primes to choose from:

$$n(P) = 10 \times 511 = 5110$$

Answer

Common mistakes

• Trying to first count all of $A$ and then work out divisibility separately. This is a valid path (and useful for a different part of the question) but it’s a longer route to $n(P)$ than directly counting, for each $x$, the subsets of the other nine primes.
• Forgetting to exclude the empty subset when counting $R$. Since $A$ requires products of two or more elements, $T=\{x\}$ alone (with $R=\varnothing$) isn’t a valid element of $A$ — this is exactly why the count is $2^9-1$, not $2^9$.

Practise next

• If $S$ is a set of $6$ distinct primes and $A$ is the set of products of two or more elements of $S$, find $n(P)$ for the same relation $P=\{(x,y): x\in S, y\in A, x\mid y\}$.