4
$\begingroup$

I have got the following task:

Let us have $11$ positive integers, none of them with a prime divisor greater than $29$. Prove that we can always choose $a_1,\ldots,a_k$ and $b_1,\ldots,b_k$, where $b_i = 1$ or $2$ for all $i$, such that the product $a_1^{b_1} \cdots a_k^{b_k}$ is a cube.

I am not sure that it is understandable, here is an example I found:

If I have the number $12$ and $18$ in my list, I can choose $a_1 = 12, a_2 = 18$ and $b_1= 1, b_2 = 1 \rightarrow a_1^{b_1} a_2^{b_2} = 12^1 18^1 = 6^3$ is indeed a cube.

I just have no idea how to do the solving in general. Maybe it has something to do with the number of primes between $1$ and $29$: $\{2,3,5,7,11,13,17,19,23,29\}$, which is $10$ primes, and we have $11$ numbers, so we have at least $2$ numbers which have the same prime divisor, but how to go further?

Thanks in advance!

$\endgroup$
11
  • 1
    $\begingroup$ It is like having $11$ vectors in $(\mathbb Z_ 3)^{10}$ being the exponents of each of the $10$ possible primes $2,3,5,7,11,13,17,19,23,29$ modulo $3$ and finding a subset of vectors that we can add multiples $1$ or $2$ together for them to add up to $0\in(\mathbb Z_3)^{10}$. It could well be something using the pigeon hole principle. $\endgroup$
    – String
    Commented Apr 20, 2015 at 7:54
  • $\begingroup$ Interesting comment, thanks :) $\endgroup$
    – Atvin
    Commented Apr 20, 2015 at 7:54
  • $\begingroup$ So a given number $n=2^a 3^b\cdots 29^j$ becomes the vector $(a,b,...,j)$ where $a,b,...,j$ have been reduced modulo $3$. $\endgroup$
    – String
    Commented Apr 20, 2015 at 7:57
  • 1
    $\begingroup$ And actually, since $(\mathbb Z_3)^{10}$ has dimension $10$, then $11$ vectors cannot be linearly independent. Thus there exists a linear combination of those $11$ vectors with non-zero coefficients that gives the zero vector. This is actually a solution to the problem! $\endgroup$
    – String
    Commented Apr 20, 2015 at 8:00
  • 2
    $\begingroup$ @String Pigeonhole principle works fine also, there's no need to appeal to linear algebra over finite fields (but it makes for a succinct argument). $\endgroup$
    – Erick Wong
    Commented Apr 20, 2015 at 8:17

1 Answer 1

3
$\begingroup$

Let $11$ numbers be given. Since they have prime factors less than $29$, we can write a given number $n$ in the form: $$ n=2^a 3^b\cdots 29^j $$ and map each $n$ to the corresponding vector $(a,b,...,j)\in(\mathbb Z_3)^{10}$. Since this is a vector space over the field $\mathbb Z_3$ of dimension $10$, we cannot have more than at most $10$ linearly independent vectors. Hence we can find a non-trivial linear combination of those $11$ exponent-vectors, that add up to the zero vector in $\mathbb Z_3$. But this exactly means that this exponent-sum is divisible by $3$ making the product of the corresponding integers a cube.

$\endgroup$
6
  • $\begingroup$ Can you explain why it is true that if the exponent-sum is divisible by $3$, than the product is a cube number? :) $\endgroup$
    – Atvin
    Commented Apr 21, 2015 at 20:21
  • 1
    $\begingroup$ @Atvin: Sure! If $n=x_1^{3y_1}\cdot x_2^{3y_2}\cdots x_k^{3y_k}$ we can write each $x_i^{3y_i}=(x_i^{y_i})^3$ and then use the rule $a^3\cdot b^3=(ab)^3$ repeatedly to have $n=(x_1^{y_1}\cdot x_2^{y_2}\cdots x_k^{y_k})^3$ which is clearly a cube number. $\endgroup$
    – String
    Commented Apr 21, 2015 at 20:27
  • $\begingroup$ But if we do this vector method, then $n$ will always have this form you wrote in the first case? :) $\endgroup$
    – Atvin
    Commented Apr 21, 2015 at 20:29
  • $\begingroup$ Maybe it is unclear, I am asking that with this method you wrote in your answer, we always get an $n$ with such form? $\endgroup$
    – Atvin
    Commented Apr 21, 2015 at 20:31
  • 1
    $\begingroup$ @Atvin: Yes! Say we have $k$ vectors $(a_1,b_1,...,j_1)$ and so on to $(a_k,b_k,...,j_k)$. Then the first number has the form $2^{a_1}\cdots 29^{j_1}$, the second $2^{a_2}\cdots 29^{j_2}$ and so on to $2^{a_k}\cdots 29^{j_k}$, and since $a_1+a_2+...+a_k=3y_1$ for some $y_1$ and $j_1+j_2+...+j_k=3y_{10}$ those numbers multiplied yield $2^{3y_1}\cdot 3^{3y_2}\cdots 29^{3y_{10}}$. $\endgroup$
    – String
    Commented Apr 21, 2015 at 20:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .