Multiplying products of $p_1,p_2,\ldots,p_n$ gives a square.

Question

Given $n+1$ ($n\ge 4$) arbitrary products of primes $p_1,p_2,\ldots, p_n$, prove multiplying some of the products gives a square.

E.g., for $n=4$: $\{p_1,p_2,p_3,p_4,p_1p_3\}$ satisfies the condition, because $p_1\cdot p_3\cdot p_1p_3=(p_1p_3)^2$. $\{p_1p_3p_4,p_2,p_1p_4,p_1p_2,p_3p_4\}$ satisfies the condition, because $p_1p_3p_4\cdot p_2\cdot p_1p_2\cdot p_3p_4=(p_1p_2p_3p_4)^2$.

Clearly it's true if $p_1,p_2,\ldots,p_n$ are not all different. Induction can help. My proof uses it, but it's difficult to explain, inelegant. I've come up with this problem while solving another problem, and it seems correct.

Answer 1

Let the $n+1$ arbitrary products be $A=\{a_1,a_2,\ldots,a_{n+1}\}$. The set of all possible products (where $6\times10\times15$ is considered distinct from $30\times2\times15$ from, for example, $A=\{2,6,10,15,30\}$) of the $a_i$ has a bijection to the power set of $A$ excepting the empty set, $\mathcal{P}(A)\setminus\emptyset$. So there are $2^{n+1}-1$ possible product expressions [edit to exclude empty set].

Now consider the set of all distinct parities of the prime powers in $P=\{p_1,\ldots,p_n\}$. This set has size $2^n$. For example, the prime parity of $12=2^2\times3$ is $(0,1)$.

So by the pigeonhole principle there are two elements of $\mathcal{P}(A)$ that evaluate (under multiplication of sub-elements) to numbers that have the same parity of prime factors. Hence when multiplied together these numbers produce a square, but the two elements are themselves sets which are not necessarily disjoint, so we cannot use this result directly.

Call the two elements $B,C\in\mathcal{P}(A)$. Consider two cases:

1. $B\subsetneq C$ (or similarly by symmetry $C\subsetneq B$).
   Take $S=C-B \neq \emptyset$. It is easily verified that every prime factor of the number formed by multiplying all elements of $S$ has even parity, hence is a square.
2. $B-C\ne\emptyset\text{ and }C-B\ne\emptyset$.
   Take $D=B-(B\cap C),\:E=C-(B\cap C),\:S=D\cup E\ne\emptyset$. It is clear that $D$ and $E$ produce numbers of the same prime parity and are disjoint sets, so $S$ produces a number with all prime factors having even parity, hence is a square. ($S$ is actually the symmetric difference of $B$ and $C$, $S=B\oplus C$).