# Given $11$ positive integers, we can always make a cube.

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?

• 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. Apr 20, 2015 at 7:54
• Interesting comment, thanks :) Apr 20, 2015 at 7:54
• 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$. Apr 20, 2015 at 7:57
• 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! Apr 20, 2015 at 8:00
• @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). Apr 20, 2015 at 8:17

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.
• Can you explain why it is true that if the exponent-sum is divisible by $3$, than the product is a cube number? :) Apr 21, 2015 at 20:21
• @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. Apr 21, 2015 at 20:27
• But if we do this vector method, then $n$ will always have this form you wrote in the first case? :) Apr 21, 2015 at 20:29
• Maybe it is unclear, I am asking that with this method you wrote in your answer, we always get an $n$ with such form? Apr 21, 2015 at 20:31
• @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}}$. Apr 21, 2015 at 20:37