
C4. Let $p_{1}, p_{2}, \ldots, p_{2005}$ be different prime numbers. Let $\mathrm{S}$ be a set of natural numbers which elements have the property that their simple divisors are some of the numbers $p_{1}, p_{2}, \ldots, p_{2005}$ and product of any two elements from $\mathrm{S}$ is not perfect square.

What is the maximum number of elements in $\mathrm{S}$ ?


## Solution

Let $a, b$ be two arbitrary numbers from $\mathrm{S}$. They can be written as

$$
a=p_{1}^{a_{1}} p_{2}^{a_{2}} \cdots p_{2005}^{a_{2005}} \text { and } b=p_{1}^{\beta_{1}} p_{2}^{\beta_{2}} \cdots p_{2005}^{\beta_{2005}}
$$

In order for the product of the elements $a$ and $b$ to be a square all the sums of the corresponding exponents need to be even from where we can conclude that for every $i, a_{i}$ and $\beta_{i}$ have the same parity. If we replace all exponents of $\mathrm{a}$ and $b$ by their remainders modulo 2 , then we get two numbers $a^{\prime}, b^{\prime}$ whose product is a perfect square if and only if ab is a perfect square.

In order for the product $a^{\prime} b^{\prime}$ not to be a perfect square, at least one pair of the corresponding exponents modulo 2, need to be of opposite parity.

Since we form 2005 such pairs modulo 2, and each number in these pairs is 1 or 2 , we conclude that we can obtain $2^{2005}$ distinct products none of which is a perfect square.

Now if we are given $2^{2005}+1$ numbers, thanks to Dirichlet's principle, there are at least two with the same sequence of modulo 2 exponents, thus giving a product equal to a square.

So, the maximal number of the elements of $S$ is $2^{2005}$.

