Show that $y^2=x^3+1$ has infinitely many solutions over $\mathbb Z_p$. I first compared it with how I would solve this over the real numbers. You would  say:


*

*$y^2=\alpha$ has a solution for all $\alpha>0$, of which there are infinitely many. 

*$x^3+1>0$ for all $x>-1$, of which there are also infinitely many.


However I can't seem to extend this way of thinking to $\mathbb Z_p$. I have a strong hunch that I need to use Hensel's Lemma in some way, but I just can't see how. 
 A: You want to show that the square root $\sqrt{x^3 + 1}$ exists in $\mathbb{Z}_p$ for infinitely many $x$. To do this, show that if $p \mid x$, then
$$\sqrt{1 + x^3} = \sum_{n \ge 0} {1/2 \choose n} x^{3n}$$
converges in $\mathbb{Z}_p$. (The case $p = 2$ is, as usual, a bit different, but not so bad.) 
A: Instead of appealing either to the Binomial Theorem, as Qiaochu did, or to Hensel, you can do it “analytically”, knowing that in terms of the local uniformizing parameter $x$ at $(0,1)$, you must be able to expand $\eta=y-1$ as a series in $x$ with no constant term. Making that substitution, you get from $y^2=x^3+1$ to $\eta=(x^3-\eta^2)/2$, which you can look at as a recursive procedure for getting the expansion of $\eta$. The result is
$$
\eta=\frac12x^3 - \frac18x^6 + \frac1{16}x^9 - \frac5{128}x^{12} + \frac7{256}x^{15}-\cdots\,,
$$
and of course this is exactly the Binomial expansion. Just make a substitution $x\mapsto x_0$ for $x_0$ small enough, and you’ll get a convergent series.
I should say that this procedure is much more fun if you do it in the neighborhood of the point $\Bbb O$ at infinity of this curve, that is, $(0:1:0)$ projectively. There, the description of the curve in terms of $\xi=x/y$  and $\zeta=1/y$ is $\zeta=\xi^3+\zeta^3$, the l.u.p. being $\xi$, so you get a $\Bbb Z$-series for $\zeta$ in terms of $\xi$. Far as I can see, this expansion doesn’t come out of the Binomial Theorem.
