Proof Involving Pigeonhole Principle

Question

Let $a_1, a_2, ..., a_n$ be positive integers all of whose prime divisors are $\le$ 13.

a) Show that if $n \ge 65$ then there exist two of these integers whose product is a perfect square. [DONE]

b) Show that if $n \ge 193$ then there exists four of these integers whose product is a perfect fourth power.

Hint: Use a) to get many pairs of numbers which multiply to a square. Use a) again to get two disjoint such pairs a, b, and c, d such that $\sqrt{ab}\sqrt{cd}$ is a square.

For b, I got 64 pairs of numbers which multiply to a square using part a. Where do I go from there?

Answer 1

Part b: We claim that we can find $65$ disjoint pairs of integers such that their product is a square. By part a), for $n\ge 193>65$, we can find one such pair. Then remove the pair from the set, and apply part a) again on the remaining $n-2$ integers. We can do this repeatedly, and because $n-2\cdot 64\ge65$, we can find at least $65$ pairs. Because the original set of integers was distinct, the pairs are disjoint. Now for each pair $(a,b)$ consider $\sqrt{ab}$, which is an integer. By part a, there are distinct $a,b,c,d$ such that $\sqrt{ab}\cdot \sqrt{cd}$ is a perfect square, so $abcd$ is a perfect $4$th power.

Answer 2

Hint: There are $6$ primes $\le 13$. Express our integers as a product of prime powers. At least $33$ of them use an even power of $2$, possibly $2^0$, or at least $33$ use an odd power of $2$.

Take $33$ of our numbers that use an even power of $2$, or $33$ that use an odd power of $2$. Of these, at least $17$ use an even power of $3$, or at least $17$ use an odd power of $3$. Continue.

Remark: This is much like your earlier $9$ point problem, except that we are kind of in a $6$-dimensional space. And instead of adding coordinates, when we multiply we add exponents.

Answer 3

The obvious first step is to list the primes $\le 13$: they are $2,3,5,7,11$, and $13$. Thus, each $a_k$ must have the form

$$\large a_k=2^{r_k}\cdot3^{s_k}\cdot5^{t_k}\cdot7^{u_k}\cdot11^{v_k}\cdot13^{w_k}$$

for some non-negative integers $r_k,s_k,t_k,u_k,v_k$, and $w_k$. Now

$$\large a_ka_\ell=2^{r_k+r_\ell}\cdot3^{s_k+s_\ell}\cdot5^{t_k+t_\ell}\cdot7^{u_k+u_\ell}\cdot11^{v_k+v_\ell}\cdot13^{w_k+w_\ell}\;,$$

which is a perfect square if and only if all of the exponents are even. How many combinations of odd and even are possible for the $6$ exponents?

This problem is really very similar to this earlier one.