3
$\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
    Apr 20, 2015 at 7:54
  • $\begingroup$ Interesting comment, thanks :) $\endgroup$
    – Atvin
    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
    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
    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
    Apr 20, 2015 at 8:17

1 Answer 1

Reset to default
2
$\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
    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
    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
    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
    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
    Apr 21, 2015 at 20:37

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.