1
$\begingroup$

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?

$\endgroup$
4
+50
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are there 64 combinations of odd andd even for the 6 exponents? $\endgroup$ – Jebediah Nov 3 '13 at 21:50
  • $\begingroup$ @Jebediah: Yes, there are: there are two possibilities for each exponent, so they can be combined in $2^6=64$ ways. $\endgroup$ – Brian M. Scott Nov 4 '13 at 2:58
1
$\begingroup$

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.

$\endgroup$

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.