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!
Best Answer
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.