12
$\begingroup$

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.

  • 0
    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$?".2011-06-03
  • 0
    I meants in integers. Edited2011-06-03
  • 0
    Do you know anything about the method of infinite descent or well ordering property?2011-06-03

2 Answers 2

21

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

  • 0
    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)2011-06-03
  • 5
    @Qwirk: See [modular arithmetic](http://en.wikipedia.org/wiki/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.2011-06-03
  • 0
    @ShreevatsaR - Thanks, I didn't catch that $a^3 \equiv 0,1,8 \text{ mod } 9$, was expecting something more complex!2011-06-03
  • 2
    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\}$.2011-06-03
  • 0
    @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$...2011-07-05
  • 0
    @Vladimir This is in part why it's a 'trick' - you can't be sure what modulus will work. In fact, it's even worse than that; there are polynomial equations $f(x)=0$ that have solutions $\pmod{p}$ for every prime $p$ but no solutions over the reals! And of course, once you get enough variables you run into Hilbert's 10th Problem that the root problem is undecidable. In general, though, it's easy enough to try a few small prime-power moduli and see if there are 'simple' exclusions.2011-07-05
  • 0
    @Vladimir, the question of which integers can be written as a sum of three cubes is hard. I believe it is unknown whether 33 is a sum of three cubes. Since I know this, I expected there had to be a trick. With squares, the first trick to try is modulus 8, since there are only three squares there; with cubes, modulus 9, similar reason.2011-07-05
  • 0
    @Gerry, after thinking about this for a little while, I've managed to come up with the explanation I was looking for of where the moduli 8 and 9 (for some of squares and cubes would come from). I would be grateful if you took a look and left a comment whether that perspective is correct.2011-07-06
6

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.
  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 ) 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).

  • 1
    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.2011-07-06