S is a set of N distinct positive integers such that no member of S has a prime factor greater than 35. Let P be the set of products of members of S taken 2 at a time. (For example, if x, y and z are members of S, then xy, xz and yz will be members of P.)

What is the smallest value of N for which it is certain that P contains a perfect square?

By considering a scaled-down version of the problem, the crux of the matter becomes quite apparent.
Let us consider the case of just 2 different prime divisors p and q (which can be 2 and 3, if you like). We need to show that there is an N such that all sets of N or more numbers of the form (p^x)*(q^y) contain a pair whose product is a square. The product (p^u)*(q^v) of two of the numbers of the set is a square exactly when u and v are both even numbers. Consider now the exponent pairs (x,y). Mod 2, (x,y) is congruent to (0,0), (0,1), (1,0), or (1,1) and, (u,v) is congruent to the component-wise mod 2 sum of two of these, possibly the same one taken twice. It is precisely when the same one is taken twice that u and v both turn out to be even. Hence any set of 5 numbers of the form (p^x)*(q^y) will always contain a pair whose product is a square, but a smaller set need not.

Edited on November 15, 2004, 12:38 am

Posted by Richard on 2004-11-15 00:35:56