Solutions to the Mordell Equation modulo $p$ It is well known that for any nonzero integer $k$ the Mordell Equation $x^2 = y^3 + k$ has finitely many solutions $x$ and $y$ in $\mathbf Z$, but it has solutions modulo $n$ for all $n$. One proof of this involves using the Weil Bound to show that $x^2 = y^3 + k$ has solutions modulo $p$ for all $p > 3$, then manually checking for $2, 3$, and then using the lifting lemma. However, the first step doesn't seem very elementary. Does anybody know how to prove that it has solutions modulo $p$ for all primes $p$. 
 A: There is an elementary solution using Jacobi sums, which takes advantage of the equation's diagonal nature (each variable appearing separately to a power). 
If $p \not\equiv 1 \bmod 3$ (this includes $p = 3$) then every element of $\mathbf Z/(p)$ is a cube in a unique way, so $x^2 \equiv y^3 + k \bmod p$ has $p$ solutions (for each $x$ there is exactly one $y$). If $k \equiv 0 \bmod p$ then the equation becomes $x^2 \equiv y^3 \bmod p$, which also has $p$ solutions.  So now let's assume $p \equiv 1 \bmod 3$ and $k \not\equiv 0 \bmod p$.
As in Dylan's answer, let $N_p$ be the number of mod $p$ solutions.  Since $p \equiv 1 \bmod 3$ there is a cubic character $\chi$ on $(\mathbf Z/(p))^\times$. In fact there are exactly two cubic characters, $\chi$ and its complex conjugate $\overline{\chi}$. Since $p$ is odd, there is a quadratic character $\psi$ on $(\mathbf Z/(p))^\times$ (it's the Legendre symbol, of course). To count solutions to $x^2 \equiv y^3 + k \bmod p$ we will count solutions $(a,b)$ to the simpler equation $a \equiv b + k \bmod p$ and then count how often $a$ is a square mod $p$ and $b$ is a cube mod $p$.  The number of ways $a$ is a square mod $p$ is $1 + \psi(a)$, and the number of ways $b$ is a cube mod $p$ is $1 + \chi(b) + \chi(b)^2 = 1 + \chi(b) + \overline{\chi}(b)$.  Therefore
$$
N_p = \sum_{(a,b)} (1 + \psi(a))(1 + \chi(b) + \overline{\chi}(b)), 
$$
where we sum over all $(a,b)$ mod $p$ for which $a \equiv b + k \bmod p$ (either $a$ or $b$ determines the other).  Expanding out the product, we get a sum of 6 terms over all the pairs $(a,b)$ where $a \equiv b + k \bmod p$:
$$
N_p = \sum_{(a,b)} (1 + \psi(a) + \chi(b) + \psi(a)\chi(b) + \overline{\chi}(b) + \psi(a)\overline{\chi}(b)).
$$
Split this up into 6 sums. The first sum is $p$ since the number of possible $(a,b)$ is $p$ (both $a$ and $b$ determine each other and either one is free to take on any value). The second, third, and fourth sums are $0$ since the sum of a nontrivial multiplicative character over $\mathbf Z/(p)$ is $0$. We're left with the sums of $\psi(a)\chi(b)$ and $\psi(a)\overline{\chi}(b)$, and at this point let's write $b$ directly in terms of $a$ (and $k$) so we can write the sums as running over all $a \bmod p$:
$$
N_p = p + \sum_{a} \psi(a)\chi(a-k) + \sum_{a}\psi(a)\overline{\chi}(a-k).
$$
Since $k \not\equiv 0 \bmod p$, we can make the change of variables $a \mapsto ka$ in both sums and pull out the character values at $k$ and $-k$:
$$
N_p = p + \psi(k)\chi(-k)\sum_{a} \psi(a)\chi(1-a) + \psi(k)\overline{\chi}(-k)\sum_{a}\psi(a)\overline{\chi}(1-a).
$$
Set $J = \sum_{a} \psi(a)\chi(1-a)$, which is a Jacobi sum, so $$N_p = p + \psi(k)\chi(-k)J + \psi(k)\overline{\chi}(-k)\overline{J} = p + 2{\rm Re}(\psi(k)\chi(-k)J).$$ For any complex number $z$, $|{\rm Re}(z)| \leq \sqrt{|z|}$, so $|N_p - p| \leq 2\sqrt{|J|}$. Since $\psi$ and $\chi$ are nontrivial characters of different order, it is standard that the modulus of the Jacobi sum is $\sqrt{p}$. Therefore $|N_p - p| \leq 2\sqrt{p}$.
For completeness, my answer at https://mathoverflow.net/questions/134352/the-modular-arithmetic-contradiction-trick-for-diophantine-equations?rq=1 discusses how to turn the count on mod $p$ solutions into the existence of a solution mod $p^r$ for all $r$.
The argument I made with quadratic and cubic multiplicative characters mod $p$ carries over to any finite field $\mathbf F_q$ in place of $\mathbf Z/(p)$: for any $k$ in $\mathbf F_q$, the equation $y^2 = x^3 + k$ has a solution $x$ and $y$ in $\mathbf F_q$.
A: The Hasse-Weil bound for elliptic curves (like $x^2=y^3+k$) tells you that the number of solutions mod $p$, which I'll call $N_p$, satisfies $|p+1 - (N_p+1)|\leq2 \sqrt{p}$. 
The smallest $N_p$ can be is $N_p = p - 2\sqrt{p}$, which is definitely $>1$ for $p>5$. For the people who know elliptic curves, I have used $N_p + 1$ because I assume OP doesn't want the point at infinity. 
