Prove that the product of primes in some subset of $n+1$ integers is a perfect square.

Question

I am trying to prove the following:

The set $A$ consists of $n + 1$ positive integers, none of which have a prime divisor that is larger than the $n$th smallest prime number. Prove that there exists a non-empty subset $B\subseteq A$ such that the product of the elements of $B$ is a perfect square.

Clearly each number is of the type $2^{\alpha_1}3^{\alpha_2}5^{\alpha_3}\cdots p_n^{\alpha_n}$ where $p_n$ is the $n$th prime number and $\alpha_i\ge 0$.

Now if I was given more then $2^n$ numbers then I could have divided the numbers by the parity of the exponents of the primes in $2^n$ classes. By the pigeonhole principle two numbers would be in the same class and hence their product would be a perfect square.

Since I am given $n+1$ numbers I need to divide them into $n$ classes to get the pigeonhole working. The obvious thing is to divide into classes mod $n$. But this obviously doesn't work, as is evident from $n=4$ and the numbers $2,3,5,6,7$.

Anu suggestions on how should I prove this result?

Answer 1

Ah, you see, you are given $n+1$ numbers, but how many subsets of those numbers do you have?

If you've got a set $B$ whose elements multiply to $\pi=p_{1}^{\beta_1}\cdots p_n^{\beta_n}$, separate the square-free part, so that $\pi=m^2\chi$ where $\chi$ is some product of distinct primes. There are $2^n-1$ nonempty sets of distinct primes from $p_1,\ldots,p_n$ and $2^{n+1}-1$ nonempty subsets from your $n+1$ integers, so here is where you can use the pigeonhole principle.

After you've got your sets $A$ and $B$ with the same $\chi$ parts, the product of their $\pi$'s is a perfect square as you've said. This number itself may not be a $\pi$ of any subset though; at that point, you should look to $(A\cup B)\setminus (A \cap B)$ and prove that that's your perfect square.

Answer 2

Given the $n+1$ numbers, how many non-empty products are there? Each product is $2^{\beta_1}3^{\beta_2}\cdots p_n^{\beta_n}$; how many "parity-boxes" are there for the exponents? Now you can use pigeonhole, though you still have to work out how to finish things off once you have your two pigeons in the same hole.

Answer 3

For a number $n=\prod_{i=1}^np_i^{e_i}$, where $p_i$ are distinct prime numbers, we define the unsquare part $$u(n)=\prod_{i=1}^np_i^{e_i\bmod 2}$$ So for example $u(6)=6,u(9)=1,u(12)=3,u(24)=6$. From this definition we get

$$u(mn)=u(u(m)u(n)),\,\forall m,n \in \mathbb N \tag {a1}$$ $$u(u(n)u(n))=1, \,\forall n \in \mathbb N \tag{a2}$$

From $(a1)$ and $(a2)$ we get

$$u(n^2)=1, \,\forall n \in \mathbb N \tag {b1}$$ $$u(u(n))=u(n), \,\forall n \in \mathbb N \tag {b2}$$

$$u(\prod_{i=1}^nm_i)=u(\prod_{i=1}^nu(m_i)), \,\forall m_i \in \mathbb N \tag {b3}$$

$$u(km)=u(kn) \implies u(mn)=1, \,\forall k,m,n \in \mathbb N \tag{b4}$$

---

Proof by Pigeon Hole Principle

From $n+1$ numbers $a_1,\ldots,a_{n+1}$ one can build $2^{n+1}-1$ products

$$\prod_{i=1}^{n+1}a_i^{e_i}, e_i \in \{0,1\}, (e_1,\ldots,e_{n+1})\ne(0,\ldots,0)\tag 1$$ from that we can create $2^{n+1}-1$ unsquare parts $$u\left(\prod_{i=1}^{n+1}a_i^{e_i}\right), e_i \in \{0,1\}, (e_1,\ldots,e_{n+1})\ne(0,\ldots,0) \tag 2$$ that can take $2^n$ different values $$\prod_{i=1}^np_i^{e_i}, e_i \in \{0,1\}\tag 3$$

so by the pigeon hole principle there are at least two different products $(3)$, $\prod_{t=1}^{n_1}a_{i_t}\cdot\prod_{t=1}^{n_2}a_{j_t}$ and $\prod_{t=1}^{n_1}a_{i_t}\cdot\prod_{t=1}^{n_3}a_{k_t}$, with $\{a_{i_1},\ldots,a_{i_{n_1}}\}$, $\{a_{j_1},\ldots,a_{j_{n_2}}\}$ and $\{a_{k_1},\ldots,a_{k_{n_3}}\}$ are pairwise disjoint and such that their unsquare part $(2)$ is equal $$u\left(\prod_{t=1}^{n_1}a_{i_t}\cdot\prod_{t=1}^{n_2}a_{j_t}\right)=u\left(\prod_{t=1}^{n_1}a_{i_t}\cdot\prod_{t=1}^{n_3}a_{k_t}\right)$$
and so by $(b4)$ $$u\left(\prod_{t=1}^{n_2}a_{j_t}\cdot \prod_{t=1}^{n_3}a_{k_t}\right)=1$$ so $\prod_{t=1}^{n_2}a_{j_t}\cdot \prod_{t=1}^{n_3}a_{k_t}$ is a perfect square and the product of $n_2+n_3$ different numbers $a_i$.

---

Proof by induction

The existence of such a number can also be proven by induction without using the pigeon hole principle.

For $n=1$ we have $a_1=p_1^{e_{1,1}}$ and $a_2=p_1^{e_{1,2}}$. One of $a_1,a_2$ or $a_3=p_1^{e_{1,1}+e_{1,2}}$ has an even exponent and so it is a perfect square.

If it is already proven for $n-1$ prime numbers then, given $n$ prime numbers $p_1,\ldots,p_n$ and $n+1$ numbers $a_1,\ldots,a_{n+1}$ built by these primes then we apply the induction hypothesis to the primes $p_1,\ldots,p_{n-1}$ and $a'_1,\ldots,a'_n$, where $a'_i$ is $a_i$ divided by the highest power of $p_n$ that divides $a_i$. There is a set $i_1,\ldots,i_n$ such that $a'_{i_1}\cdot\ldots\cdot a'_{i_k}$ is a perfect square and so either $a_{i_1}\cdot\ldots\cdot a_{i_k}$ is a perfect square or $u(a_{i_1}\cdot\ldots\cdot a_{i_k})=p_n$ Now we apply the induction hypothesis again to the primes $p_1,\ldots,p_{n-1}$ and the $n$ numbers $a'_1,\ldots,a'_{n+1}$ without $a'_{i_1}$ from the previous result. We get a different $j_1,\ldots,j_m$ such that either $a_{j_1}\cdot\ldots\cdot a_{j_m}$ is a perfect square or $u(a_{j_1}\cdot\ldots\cdot a_{j_m})=p_n$ Either we have found a perfect square or $$u(a_{i_1}\cdot\ldots\cdot a_{i_k})=u(a_{j_1}\cdot\ldots\cdot a_{j_m})$$ and we again can construct a perfect square by $(b4).$