# Prime factorization problem

The prime factorizations of $r + 1$ positive integers ($r \geq 1$) together involve only $r$ primes. Prove that there is a subset of these integers whose product is a perfect square.

Now, I'm considering applying the pigeonhole principle as follows: The number of nonempty subsets of the given set of $r + 1$ positive integers is $2^{r+1} - 1$ (our "pigeonholes"). The number of subsets of the set of the given $r$ primes $\{p_{1},\ldots,p_r\}$, is $2^r - 1$ (our "pigeons"). By the pigeonhole principle, it should follow that there exist $2$ subsets of the set of the $r + 1$ positive integers that occupy the same "pigeonhole," i.e., both have the property that the product of their respective elements can be expressed as a prime factorization using the elements of a unique (singular) subset of $\{p_{1},\ldots,p_r\}$. Thus, if we take the product of the combined elements of these two sets, we should end up with a perfect square. The problem, though, is that in taking the union of these two sets, we may end up with a set that is "larger" than the given set of $r + 1$ positive integers. How can I get around this?

• Hint: You can view it as a question of linear dependency over $\mathbb{Z}/(2)$. – Daniel Fischer Nov 23 '13 at 20:03
• I've updated the problem, attempting a solution. – David Smith Nov 23 '13 at 21:22

You have misapplied the terms "pigeon" resp. "pigeonhole", but that's of course not essential.

Your attempt isn't bad, you just need to formulate it more clearly to see it works, and you shouldn't exclude empty subsets.

So for every subset $A$ of the $r+1$ integers, let $P$ be the product of the integers in $A$, and $B$ the subset of the $r$ primes that appear with an odd exponent in the factorisation of $P$.

By the pigeonhole principle - since there are $2^{r+1}$ subsets of the $r+1$ integers, but only $2^r$ subsets of the $r$ primes - there are two sets $A_1,\, A_2$ of integers that map to the same subset $B$ of the primes. That means that

$$P_1P_2 = \prod_{k\in A_1} k \cdot \prod_{m\in A_2}m$$

is a perfect square. But what if $A_1 \cap A_2 \neq \varnothing$? Then you can't (generally) use $A_1 \cup A_2$. No problem. The elements of $A_1\cap A_2$ appear in both products, so that contributes a perfect square to $P_1P_2$. We can just ignore them, and consider the symmetric difference of $A_1$ and $A_2$,

$$A = A_1 \bigtriangleup A_2 = (A_1 \setminus A_2) \cup (A_2 \setminus A_1).$$

Since $A_1 \neq A_2$, that isn't the empty set, and $\prod_{n\in A}n$ is a perfect square. (Aside, there's also the cheating(?) trivial solution of the empty subset with product $1$, which is a perfect square.)

Another way to prove it is what I hinted at in the comment, each of the $r+1$ integers gives you a vector $v_n \in\mathbb{Z}_2^r$, whose components are the parity of the corresponding prime in its factorisation. Since you get $r+1$ vectors in an $r$-dimensional space, these are linearly dependent. That meants there is a non-zero $(r+1)$-tuple $c \in \mathbb{Z}_2^{r+1}$ with $\sum c_nv_n = 0$. That means the product of the integers corresponding to the non-zero components of $c$ is a perfect square.

• Your statement, "there are $2^{r+1}$ subsets of the $r + 1$ integers," implies that each of the $r + 1$ integers is distinct from the others. But what if there are equivalent integers among the $r + 1$ integers? – David Smith Nov 23 '13 at 23:22
• Paint them with $r+1$ distinct colours to distinguish them. But, if there are two equal integers among them, multiply the two to get a perfect square, then you don't need pigeon-holing. – Daniel Fischer Nov 23 '13 at 23:24