Problem:
Let be different prime numbers. Let be a set of natural numbers whose elements have the property that their simple divisors are some of the numbers and the product of any two elements from is not a perfect square.
What is the maximum number of elements in ?
Solution
Solution:
Let be two arbitrary numbers from . They can be written as
In order for the product of the elements and to be a square, all the sums of the corresponding exponents need to be even, from where we can conclude that for every , and have the same parity. If we replace all exponents of and by their remainders modulo , then we get two numbers , whose product is a perfect square if and only if is a perfect square.
In order for the product not to be a perfect square, at least one pair of the corresponding exponents modulo need to be of opposite parity.
Since we form such pairs modulo , and each number in these pairs is or , we conclude that we can obtain distinct products, none of which is a perfect square.
Now if we are given numbers, thanks to Dirichlet's principle, there are at least two with the same sequence of modulo exponents, thus giving a product equal to a square.
So, the maximal number of the elements of is .