Prove that the product of primes in some subset of $n+1$ integers is a perfect square.

Solution 1:

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.

Solution 2:

Ah, you see, you are given $n+1$ numbers, but how many subsets of those numbers do you have?

If you've got a set $B$ whose elements multiply to $\pi=p_{1}^{\beta_1}\cdots p_n^{\beta_n}$, separate the square-free part, so that $\pi=m^2\chi$ where $\chi$ is some product of distinct primes. There are $2^n-1$ nonempty sets of distinct primes from $p_1,\ldots,p_n$ and $2^{n+1}-1$ nonempty subsets from your $n+1$ integers, so here is where you can use the pigeonhole principle.

After you've got your sets $A$ and $B$ with the same $\chi$ parts, the product of their $\pi$'s is a perfect square as you've said. This number itself may not be a $\pi$ of any subset though; at that point, you should look to $(A\cup B)\setminus (A \cap B)$ and prove that that's your perfect square.

Solution 3:

Given the $n+1$ numbers, how many non-empty products are there? Each product is $2^{\beta_1}3^{\beta_2}\cdots p_n^{\beta_n}$; how many "parity-boxes" are there for the exponents? Now you can use pigeonhole, though you still have to work out how to finish things off once you have your two pigeons in the same hole.