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.
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.
Hint: work modulo 9. ${}{}{}{}{}{}{}$
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:
- 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
.
- 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.
- 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:
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).