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.

  • $\begingroup$ Consider the vector of exponents mod 2. $\endgroup$ – Aravind Oct 23 '15 at 17:21

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$).
  • $\begingroup$ @user263326 - This is purely a notational issue. $B\subsetneq C$ means that $B$ is a proper subset of $C$ (i.e. $B$ is a subset of $C$ and $B$ is not equal to $C$), and so $C-B\ne\emptyset$. It occurs to me now that both cases can be covered by $S=B\oplus C$, as this will yield $C-B$ when $B\subsetneq C$. $\endgroup$ – Marconius Oct 23 '15 at 22:15
  • $\begingroup$ Indeed, you can avoid cases and simply take $B\oplus C$. $\endgroup$ – user263326 Oct 23 '15 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.