All elements in $\mathbb{Z}/n\mathbb{Z}$ are representable as sum of a square and a cube? Is it true that all elements in $\mathbb{Z}/n\mathbb{Z}$ are representable as the sum of a square and a cube?
Example: ($n=7$)
$0 \equiv 0^2+0^3 \left( \text{mod } 7 \right)$
$1 \equiv 1^2+0^3 \left( \text{mod } 7 \right)$
$2 \equiv 1^2+1^3 \left( \text{mod } 7 \right)$
$3 \equiv 2^2+3^3 \left( \text{mod } 7 \right)$
$4 \equiv 5^2+0^3 \left( \text{mod } 7 \right)$
$5 \equiv 2^2+4^3 \left( \text{mod } 7 \right)$
$6 \equiv 0^2+6^3 \left( \text{mod } 7 \right)$
It is trivial to see that $0$, $1$, $2$, and $\left( n-1 \right)$ can be represented as the sum of a square and a cube.  This is accomplished when considering the combinations like $\left( 0^2+0^3 \right)$, $\left( 0^2+1^3 \right)$, $\left( 1^2+0^3 \right)$, etc.
How can I prove this?
EDIT:
There is a slightly stronger version which states that all elements can be written as $a^2+b^3$, where $a \ne b$.  I have verified this stronger version up to $n=1000$.
 A: I prove it for $n=p$ a prime. After checking the cases $p=2$ and $p=3$ by hand, I suppose that $p>3$. Let $a \in \mathbf F_p$, we want to show that $a$ is the sum of a square and a cube. Without loss of generality we suppose $a \neq 0$.  Let $E_a$ be the curve
$$y^2 = x^3 +a.$$
over $\mathbf F_p$. Since $a \neq 0$, $E_a$ is an elliptic curve over $\mathbf F_p$. We have the following theorem (the so-called Hasse bound, or the Riemann hypothesis for elliptic curves over finite fields):

Theorem (Artin - Hasse) : Let $E/\mathbf F_p$ be an elliptic curve. Then $$|\#E(\mathbf F_p) - p - 1| \leq 2 \sqrt p.$$

Corollary: If $p>3$, then $\#E(\mathbf F_p)>1$, i.e. $E$ has a nontrivial rational point over $\mathbf F_p$.
Proof: If $\#E(\mathbf F_p) = 1$ then $p \leq 2 \sqrt p$ implies $p\leq 4$.
Corollary: If $p$ is prime, then every element of $\mathbf Z/p\mathbf Z$ is the sum of a cube and a square.
Proof: If $(x_0, y_0)$ is a nontrivial point on $E_a$ then $y_0^2 + (-x_0)^3 = a$.
Remark: Your other question, concerning the existence of a solution with $x_0 \neq y_0$, can be answered positively using Bézout's theorem. The line $y=x$ intersects $E_a$ in at most $3$ points, so for $p$ large enough, Artin-Hasse still guarantees the existence of a solution with $x_0 \neq y_0$. (I'll let you figure out the right bound on $p$.)
