Let S=p_1,p_2 ,p_10 be the set of first ten prime numbers.

Question

Let $S={{p}_{1},{p}_{2}\ldots ,{p}_{10}}$ be the set of first ten prime numbers. Let $A=S\cup P$, where $P$ is the set of all possible products of distinct elements of $S$. Then the number of all ordered pairs $(x,y),x\in S$, $y\in A$, such that $x$ divides $y$, is \_\_\_\_\_\_\_\_ .

Answer: 5120

Accepted Answer

Fix $x = p_i \in S$. For $x\mid y$ with $y\in A$, $y$ must be a product including $p_i$ as a factor, i.e. $y = p_i \cdot \lambda$ where $\lambda$ is a product of any subset of the remaining 9 primes (including the empty subset, giving $y=p_i$ itself).

Number of such $\lambda$: $\displaystyle\sum_{k=0}^{9}\binom{9}{k} = 2^9 = 512$.

Since this holds for each of the 10 choices of $x$:
$$10 \times 512 = 5120$$

Solutions · 1