Maths Olympiad Prep

Library / /15 of 16

Number theory Difficulty 6.6 National Olympiad Prove it JBMO

Problem:
Let p1,p2,,p2005p_{1}, p_{2}, \ldots, p_{2005} be different prime numbers. Let S\mathrm{S} be a set of natural numbers whose elements have the property that their simple divisors are some of the numbers p1,p2,,p2005p_{1}, p_{2}, \ldots, p_{2005} and the product of any two elements from S\mathrm{S} is not a perfect square.
What is the maximum number of elements in S\mathrm{S}?

Solution

Solution:
Let a,ba, b be two arbitrary numbers from S\mathrm{S}. They can be written as
a=p1a1p2a2p2005a2005 and b=p1β1p2β2p2005β2005 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 aa and bb to be a square, all the sums of the corresponding exponents need to be even, from where we can conclude that for every ii, aia_{i} and βi\beta_{i} have the same parity. If we replace all exponents of aa and bb by their remainders modulo 22, then we get two numbers aa', bb' whose product is a perfect square if and only if abab is a perfect square.

In order for the product aba' b' not to be a perfect square, at least one pair of the corresponding exponents modulo 22 need to be of opposite parity.

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

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

So, the maximal number of the elements of SS is 220052^{2005}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.