I am trying to prove the following:
The set $A$ consists of $n + 1$ positive integers, none of which have a
prime divisor that is larger than the $n$th smallest prime number.
Prove that there exists a non-empty subset $B\subseteq A$ such that the product
of the elements of $B$ is a perfect square.
Clearly each number is of the type $2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}\cdots p_n^{\alpha_n}$ where $p_n$ is the $n$th prime number and $\alpha_i\ge 0$.
Now if I was given more then $2^n$ numbers then I could have divided the numbers by the parity of the exponents of the primes in $2^n$ classes. By the pigeonhole principle two numbers would be in the same class and hence their product would be a perfect square.
Since I am given $n+1$ numbers I need to divide them into $n$ classes to get the pigeonhole working. The obvious thing is to divide into classes mod $n$. But this obviously doesn't work, as is evident from $n=4$ and the numbers $2,3,5,6,7$.
Anu suggestions on how should I prove this result?
Best Answer
Here is a nice presentation of the proof using linear algebra:
Identify each number $p_1^{a_1}\dots p_n^{a_n}$ with the tuple $(a_1,\dots,a_n)$, with each $a_i$ reduced modulo $2$, and note that multiplying numbers corresponds to adding their tuples, and that a square is precisely a number whose associated tuple is $(0,\dots,0)$.
We can think of these tuples as vectors in ${\mathbb F_2}^n$, where $\mathbb F_2$ is the field of two elements. This is a vector space of dimension $n$, and $n+1$ vectors are given, so they are linearly dependent, that is, there is a nontrivial linear combination of them that equals $0$. But a linear combination is just a sum of some of them (since the only scalars are $0$ and $1$), and we are done.