Product of $n$ positive integers with at most $n-1$ prime divisors

Question

Below is the question I am having difficulties with:

Show: If the $\prod_{i=1}^{n} a_i$ has strictly less than $n$ distinct prime divisors, then there is an $I \subseteq \lbrace 1,...n\rbrace$ s.t. $\prod_{i \in I} a_i$ is a perfect square.

The simplest case I already did:

Consider the simplest case, where $\forall i \in \lbrace 1,...n\rbrace: a_i = p_i \in \mathbb{P}$.

Then by the Pigeon Hole principle $\exists (i,j) \in \lbrace 1,...n\rbrace^2: a_i=p_i=p_j=a_j$.

Now we can simply chose $I = \lbrace i,j \rbrace$ such that $\prod_{i \in I} a_i = p_i^2 = p_j^2$ which is a perfect square.

For the general case, I find it difficult to formally show that the statement is true. The following is my attempt so far:

Let $a_i=\prod_{j=1}^{n-1} p_{j}^{\alpha _{j _{i}}}$ where $\alpha _{j _{i}} \geq 0$. Then

$$\prod_{i=1}^{n} a_i = \prod_{i=1}^{n} \prod_{j=1}^{n-1} p_{j}^{\alpha _{j _{i}}} = \prod_{j=1}^{n-1} \prod_{i=1}^{n} p_{j}^{\alpha _{j _{i}}} = \prod_{j=1}^{n-1} p_{j}^{ \sum_{i=1}^{n} \alpha _{j _{i}}}$$

where there exists at least one $j$ s.t $$\sum_{i=1}^{n} \alpha _{j _{i}} \geq 2$$

However, from this point, I don't really see how I can apply the Pigeon Hole principle. Would really appreciate some insight here.

Thanks folks in advance!

Answer 1

Here are the bare outlines of a proof. It does not use the pigeonhole principle, as I don't see how that applies to this problem.

The proof hinges on the fact that in a $k$-dimensional vector space, with $k<n$, any set of $n$ vectors will be linearly dependent.

Suppose there are $k<n$ prime divisors of the $a_i$. Each $a_i$ can be uniquely written as a product of prime powers using those $k$ primes (unused primes have exponent $0$ of course). This corresponds to a vector in $\mathbb{Z}_2^k$, the k-dimensional vector space over $\mathbb{Z}_2$, the integers mod $2$, simply by taking as the vector's coordinates those prime exponents modulo $2$.

To turn this into a proof you will have to justify why the vector space does what you want, i.e. establish the homomorphism and show that a linearly dependent set of vectors gives you the set $I$ that you are looking for.

Edit: As the other answer shows, it is possible to prove it using the pigeonhole principle, using the possible sets $I$ as the pigeons, and the elements of the vector space $\mathbb{Z}_2^k$ as the pigeonholes.

Answer 2

Here is a proof using Pigeonhole Principle (although my explanation is quite bad). Any critique is much appreciated.

Let $n \geq 2$. $\forall \ I \subseteq \{1,2,...,n\}, $ write $\prod_{i \in I} a_i$ in the form $p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}, k \leq n-1, \alpha_i \geq 0. $

For each $I$, consider the induced $k$-tuple $(\alpha_1,\alpha_2,...,\alpha_k)$ modulo $2$. There are at most $2^{n-1}$ distinct such tuples (Each $\alpha_i$ is $0$ or $1$ modulo $2$). Additionally, there are $2^n-1$ subsets of $\{1,2,...,n\}$, excluding the null set.

Since $2^n-1 > 2^{n-1}, $ by the Pigeonhole Principle, there are $2$ distinct subsets, $I_1$ and $I_2$, of $\{1,2,...,n\}$, such that $(\alpha_1,\alpha_2,...,\alpha_k) = (\beta_1,\beta_2,...,\beta_k)$ modulo $2$. We now consider $2$ cases :

Case $1$: $I_1$ and $I_2$ are disjoint. Clearly, $\prod_{i \in {I_1 \cup I_2}} a_i =p_1^{\alpha_1+\beta_1}p_2^{\alpha_2+\beta_2}...p_k^{\alpha_k+\beta_k}$ is a perfect square, since each exponent $\alpha_{i} + \beta_{i}$ is even.

Case $2$: $I_1$ and $I_2$ are not disjoint, but $I_1$ is not a subset of $I_2$, and vice versa. Let $m$ be a common element, and consider the $2$ new sets $J_1=I_1\setminus \{m\},J_2=I_2\setminus \{m\}$. Clearly, the $2$ new induced tuples $(\alpha_1^{'},\alpha_2^{'},...,\alpha_k^{'})$ and $(\beta_1^{'},\beta_2^{'},...,\beta_k^{'})$ are still equal modulo $2$. If $J_1$ and $J_2$ are disjoint, we are done by Case $1$. Otherwise, we iterate this process until we end up with $2$ disjoint subsets, then apply Case $1$.

Case $3$: $I_1$ is a (strict) subset of $I_2$, or vice versa. W.L.O.G. let it be the latter. Then, consider $\prod_{i \in {I_1 \setminus I_2}} a_i =p_1^{\alpha_1-\beta_1}p_2^{\alpha_2-\beta_2}...p_k^{\alpha_k-\beta_k}$, which is a perfect square since each exponent is a non-negative even integer.