# Help with olympiad question: Solve $x^3 + y^3 + z^3 = 2011 \text{ for }x,y,z \in \mathbb{Z}$

Solve the equation: $x^3 + y^3 + z^3 = 2011$ in integer numbers.

I'm trying to solve problems I couldnt on the competition itself but I'm totally stuck.

-
You cannot mean natural numbers, since those are (depending whom you ask) $1$, $2$, $3$, and so on, or $0$, $1$, $2$, $3$, and so on, and you could try all possibilities, taking a few shortcuts to cut down on the work. But if you mean integers, then there is some work to do. It would be better to phrase the question as "Are there integers $x$, $y$, $z$ such that $x^3+y^3+z^3=2011$?". –  André Nicolas Jun 3 '11 at 6:11
I meants in integers. Edited –  Vadiklk Jun 3 '11 at 6:15
Do you know anything about the method of infinite descent or well ordering property? –  night owl Jun 3 '11 at 10:13

Hint: work modulo 9. ${}{}{}{}{}{}{}$

-
Hi Gerry. Can you just explain to someone with no experience how this works? (for example, a Wikipedia reference to some relevant theorem is fine) –  Juan S Jun 3 '11 at 8:52
@Qwirk: See modular arithmetic — basically, here you consider the remainders of numbers when divided by 9, rather than the numbers themselves. There are only nine possible remainders, so only nine classes of numbers, and their cubes happen to fall into only 3 classes. (In other words, the cube of any integer when divided by 9 leaves remainder either 0, 1, or 8.) So whether three cubes can add up to 2011 which leaves remainder 4 when divided by 9 is something you may be able to eliminate by looking at just remainders. –  ShreevatsaR Jun 3 '11 at 9:57
@ShreevatsaR - Thanks, I didn't catch that $a^3 \equiv 0,1,8 \text{ mod } 9$, was expecting something more complex! –  Juan S Jun 3 '11 at 10:38
It may simplify the analysis to think of the residues as $-1,0,1$ instead of $0,1,8$. (This is fine since $-1 = 8 \bmod 9$.) Now ask yourself how to make $4$ from three members of the set $\{-1,0,1\}$. –  Fixee Jun 3 '11 at 15:27
@Gerry I'm not sure this answers the question as posed: in order to be certain that the modular trick would work you have to already be certain that the equation has no solutions. Furthermore, even if you believe the equation has no solutions, how do you determine what modulus would give you the counter-example? In particular, based on this answer, I've no idea how to solve $x^3+y^3+z^3=2017$... –  Vladimir Sotirov Jul 5 '11 at 20:15

I think the appearance of $9$ in Gerry's answer can be explained using a part of Hensel's Lemma.

Since at least one of the commentators on Vadiklk's question seem to just be learning about modular arithmetic, I'll comment briefly on some of the notation before stating the lemma. If $f(x)=a_nx^n+a_{n-1}x^{n-1}+\dots+a_0$, then the (formal) derivative of $f$ is denoted $f'$ and given by $f'(x)=a_nnx^{n-1}+a_{n-1}(n-1)x^{n-2}+\dots+a_22x^1+a_1$, and for any two integers $b$ and $a$ we say that $b\equiv a^{-1}\mod p$ if $ba\equiv1\mod p$.

Hensel's Lemma:

Let $f(x)$ be a single-variable polynomial with integer coefficients. Let $p^k\neq 1$ be some non-trivial prime power, and suppose that we have an integer $r$ that is a solution to $f(r)\equiv 0\mod p^k$. Then the set of solutions to $f(x)\equiv 0\mod p^{k+1}$ can be computed to be:

1. If $f'(r)\not\equiv0\mod p$, then the only solution is $x=r+tp^k$ where $t\equiv-(\frac{f(r)}{p^k})f'(r)^{-1}\mod p$ with $0\leq t<p$.
2. If $f'(r)\equiv0\mod p$ and $f(r)\equiv 0\mod p^k$, then any $x\equiv r\mod p^{k-1}$ (i.e. $x=r+tp^k$ for $0\leq t<p$ ) is a solution.
3. If $f'(r)\equiv 0\mod p$ and $f(r)\not\equiv0\mod p^k$, then there are no solutions.

(If you're just learning about modular arithmetic, proving Hensel's Lemma is a great exercise to get your head around this stuff.)

Notice that in cases 1. and 2. we have that $f'(r)=f'(x)\mod p$ (since $x=r+tp^k$ implies that $x\equiv r\mod p$). Hence:

1. $f(x)$ definitely has an integer root if $f'(r)\not\equiv 0\mod p$ and $f(r)\equiv 0\mod p$ for some integer $r$ and prime $p$.
2. $f(x)$ may have a root if $f'(r)\equiv0\mod p$ for some integer $r$ and prime $p$.

In other words, if $f'(r)\not\equiv0\mod p$, then non-existence of solutions $\mod p^k$ does not imply non-existence of solutions $\mod p^{k+1}$. Hence, if we wish to systematically determine if $f(x)$ has integer solutions, we must find a prime $p$ for which there exists an integer $r$ such that $f'(r)\equiv 0\mod p$, and then build up solutions $\mod p^k$ until we either can't (no solutions) or $p^k$ is large enough (since we would be computing $f(r)$ and reducing $\mod p^k$ anyway, large enough means that $f(r)=0$ and we have found a root).

Of course, it is not always possible to find a prime $p$ such that $f'(r)\equiv 0\mod p$ for some $r$, which is why determining whether integer solutions exist is in general difficult.

Applying this to our equation $x^3+y^3+z^3=2011$, we can define for any integers $y$ and $z$ polynomials $f_{y,z}(x)=x^3+(y^3+z^3-2011)$. Our equation has an integer solution if and only if one of the polynomials $f_{y,z}$ has a solution.

Fortunately, we see that $f'_{y,z}=3x^2$ does not depend on $y$ or $z$, so for any prime and any integer $r$ $f'_{y,z}(r)\equiv0$ if and only if $3r^2\equiv0\mod p$.

However, in order to simultaneously determine (using the above) which of the polynomials $f_{y,z}$ have integer solutions, we need $f'_{y,z}(r)\equiv 0\mod p$ for every $r$ such that $f_{y,z}(r)\equiv 0\mod p$. Since $y$ and $z$ are arbitrary, this means that we need $f'_{y,z}(r)\equiv 0\mod p$ for every $r$, which, since $f'_{y,z}(x)=3x^2$ implies we can only be checking $p=3$.

Hence, if a solution to $x^3+y^3+z^3=2011$ does not exist, this is detected by the smallest $3^k$ for which a solution does not exist. The first such one happens to be $9$.

More generally, because of how separability works over finite field, the above will be true exactly for those $p$ which divide the gcd of the powers of $x$ appearing in the equation (if the equation is not symmetric, we can also look at the gcd of the powers of $y$ and of the powers of $z$ and look at those primes as well).

-
I'm sure this is correct, but on the other hand I know I for one was aware of the properties of 8 and 9 with respect to squares and cubes long before I heard of Hensel's Lemma. –  Gerry Myerson Jul 6 '11 at 4:47