Is there an elementary way to find the integer solutions to $x^2-y^3=1$? I gave this problem to my undergraduate assistant, as I saw that Euler had originally solved it (although I am having trouble finding his proof).  After working on it for two weeks, we boiled the hard cases down to showing that (1) in $\mathbb{Z}[w]$ the fundamental unit is $1+w+w^2$ (where $w$ is the real cube-root of 2) [which I'm sorry to say, I'm not certain I know off the top of my head how to prove], and (2) using that fundamental unit, I found a crazy ad hoc computation to show that there are only the obvious solutions.
So I'm wondering if someone else out there is more clever, knows where I can find Euler's proof, or if there is another nice elementary proof in the literature.
 A: More generally, $x^2-y^3=k$ is called the Mordell equation. For some values of $k$, you'll find elementary solutions in Mordell's Diophantine Equations, and in Uspensky and Heaslett's textbook. 
EDIT: I've had a look at Mordell's book. He refers to his paper, The infinity of rational solutions of $y^2=x^3+k$, J London Math Soc 41 (1966) 523-525. 
A: If your students know a little about the Eisenstein integers (unique factorization and what the units are) there's the following simple argument (maybe it's essentially Euler's?).
Let $u$ and $v$ be the complex roots of $z^2+z+1=0$.
Theorem. Let $A$, $B$, $C$ be non-zero elements of $\mathbb{Q}[u]$ with sum $0$ and product twice a cube. Then some two of $A$, $B$, $C$ are equal.
Corollary. Suppose $x$ is in $\mathbb{Q}$ and $x^2-1$ is a cube. Then $x$ is $1$, $-1$, $0$, $3$, or $-3$.
(To prove the corollary let $A=1+x$, $B=1-x$ and $C=-2$).
The proof of the theorem is a reductio ad absurdum. If there's a counterexample, there's one with $A$, $B$, $C$ in $\mathbb{Z}[u]$; take such a counterexample with $d=\min(|A|,|B|,|C|)$ as small as possible. Then $A$, $B$, $C$ are pairwise coprime. Since $ABC=2$(cube) we may assume $A=2i$(cube), $B=j$(cube), $C=k$(cube) where $i$, $j$, and $k$ are in the set $\{1,u,v\}$. Now all cubes in $\mathbb{Z}[u]$ are $0$ or $1$ mod $2$. Since $B+C$ is $0$ mod $2$, $j=k$. Since $ABC=2$(cube), $ijk$ is a cube and $i=j=k$. We may assume $i=j=k=1$. Then $A=2r^3$, $B=s^3$, $C=t^3$, and we may further assume that $s$ and $t$ are $1$ mod $2$. $s$ and $t$ are not both in $\{1,-1\}$ and it follows that $d$ is at least $\sqrt{27}$. Now look at $s+t$, $us+vt$ and $vs+ut$. They
sum to $0$ and their product is $B+C=-2(r^3)$. They are congruent to $0$, $1$ and $1$ mod $2$, and the last 2 of them can't be equal since $s$ is not equal to $t$. Since each of them is at most $2d^{1/3}$, this contradicts the minimality assumption.
This is really a 3-descent argument on an elliptic curve, but the fancy language as you see isn't needed. An almost identical argument gives what I think is the nicest proof of Fermat's Last Theorem for exponent 3. 
A: There is a beautiful elementary way of solving the equation
$$Ny^2-x^3=\pm1$$ when $N$ contains no prime factors that are of the form $6k+1$. There are only 7 solutions $(x,y,N)$ $$\{(2,3,1)(1,1,2)(23,78,2)(23,39,8)(2,1,9)(23,26,18)(23,18,72)\}$$ This was proven by J.H.E. Cohn in the article "The diophantine equations $x^3=Ny^2\pm 1$"
A: Only the second proof below is new. In 1., I explain where the units in the cubic field
are coming from, and  3. is a variation of Paul Monsky's proof.


*

*We try working in ${\mathbb Z}$ for as long as possible.
Write $x^3 = y^2 - 1 = (y-1)(y+1)$; since the gcd of the 
factors on the right hand side divides $2$, there are
two possibilities:
a) $y$ is even; then $y+1 = \pm a^3$ and $y - 1 = \pm b^3$.
  Subtracting these equations gives 
  $2 = a^3 - b^3 = (a-b)(a^2+ab+b^2)$, hence $a-b$ divides
  $2$. Going through all cases gives $(x,y) = (-1,0)$.
b) $y$ is odd; then $y+1 = 2a^3$ and $y - 1 = 4b^3$. 
  Subtracting these equations gives $1 = a^3 - 2b^3$.
It remains to solve the last equation. One possibility is showing
that the unit $1 - \sqrt[3]{2}$ is fundamental in the cubic number
field ${\mathbb Q}(\sqrt[3]{2})$, and that its only powers
of the form $a+b\sqrt[3]{2}$ have exponent $0$ or $1$.
The other possibility is observing that this equation is a special
case of the twisted Fermat cubic $x^3 + y^3 = 2z^3$. But Paul
Monsky's proof shows directly that solving this equation is
all that is needed.

*A more or less standard proof (this is basically a classical 
$2$-descent, but perhaps more direct than Euler's approach,
which avoids number fields altogether - it is well known that
on curves with a rational point of order $2$, a simple 2-decent
can be performed by working within the rationals)
proceeds as follows: write the equation in the form
$$ y^2 = (x+1)(x+\rho)(x+\rho^2), $$
where $\rho$ is a primitive cube root of unity. The gcd
of two factors divides $1-\rho$, hence there are two possibilities:
a) $x+1 = \pm a^2$, $x + \rho = (-\rho)^e (a+b\rho)^2$, 
  $x + \rho^2 =  (-\rho^2)^e (a+b\rho^2)^2$. Since
  $\rho = (1+\rho)^2$  is a square, we can subsume the powers
  of $\rho$ into the square and find
  $x + \rho = \pm (a+b\rho)^2$ and $x + \rho^2 = \pm (a+b\rho^2)^2$. 
  Subtracting these equations and dividing through by $\rho - \rho^2$
  gives $1 = \pm b(2a-b)$, leading to  $(x,y) = (0,\pm 1)$ and $(-1,0)$.
b) Here we find
   $$  x+1  = \ \pm 3a^2, \quad
        x + \rho    = \ \pm (1-\rho) (a+b\rho)^2, \quad
        x + \rho^2  = \ \pm (1-\rho^2) (a+b\rho^2)^2. $$
 Adding the last two equations gives $2x-1 = \pm 3(a^2 - b^2)$. 
 Eliminating $x$ from this and the first equation 
 (where we actually have $x = 3a^2$ since $x \ge -1$) yields 
 $(x,y) = (2,\pm 3)$.

*Let me give here my rendition of Paul's beautiful proof:
Let $\alpha, \beta, \gamma \in {\mathbb Z}[\rho] \setminus \{0\}$. If
$\alpha + \beta + \gamma = 0$ and $\alpha\beta\gamma = 2\mu^3$, then
after a suitable permutation of the three numbers we have 
$\alpha = 0$ or $\beta = \gamma$.
Proof. Let $(\alpha,\beta,\gamma)$ be a counterexample. Then
$\alpha$, $\beta$ and $\gamma$ are pairwise coprime in ${\mathbb Z}[\rho]$, 
and after a suitable permutation we have 
$$ \alpha = 2 \rho^a A_1^3, \quad 
    \beta =   \rho^b B_1^3,  \quad
   \gamma =   \rho^c C_1^3. $$
Among all such counterexamples we now take one in which $N\alpha$
is minimal. Dividing all three numbers by $\rho^a$ we may assume
that $a = 0$.
Cubes in ${\mathbb Z}[\rho]$ are $\equiv 0, 1 \bmod 2$ by Fermat's Little Theorem. 
Thus $0 \equiv \alpha \equiv \beta + \gamma \equiv \rho^b + \rho^c \bmod 2$, which implies $b = c$. Since $\alpha\beta\gamma$ is a cube, we must have $a = b = c = 0$.
Thus 
$$ \alpha = 2 A_1^3, \quad \beta = B_1^3,  \quad \gamma = C_1^3. $$
Since $B_1^3 \equiv C_1^3 \equiv 1 \bmod 2$, we may assume that 
$B_1 \equiv C_1 \equiv 1 \bmod 2$ (after multiplying these numbers
through by a suitable power of $\rho$).
Now set $\alpha_1 = B_1 + C_1$, $\beta_1 = \rho B_1 + \rho^2 C_1$ 
and $\gamma_1 = \rho^2 B_1 + \rho C_1$. Then 


*

*$\alpha_1 + \beta_1 + \gamma_1 = B_1(1+\rho+\rho^2) + C_1(1+\rho+\rho^2) = 0$.

*$\alpha_1 \beta_1 \gamma_1  = B_1^3 + C_1^3 = \beta + \gamma 
             = -\alpha = 2(-A_1)^3$.

*$\beta_1 + \gamma_1 = (B_1 + C_1)(\rho+\rho^2) = - (B_1 + C_1) \ne 0$
  since $\beta + \gamma = -\alpha \ne 0$.

*$N(\alpha_1 \beta_1 \gamma_1) = N\alpha \mid N(\alpha\beta\gamma)$; 
if we had equality, it would follow that $N(\beta) = N(\gamma) = 1$,
hence $\beta, \gamma = \pm 1$. But then 
$\beta = 1$, $\gamma = -1$ and $\alpha = 0$ against our assumptions.


Now descent finishes the proof: $(\alpha_1, \beta_1, \gamma_1)$ is another
solution with $N(\alpha_1 \beta_1 \gamma_1) < N(\alpha\beta\gamma)$, 
As a final remark I would like to point out that the article by Cohn in Gjergji Zaimi's answer uses "well known results" such as the solution of $x^4 - 2y^2 = \pm 1$ and $x^4 - 3y^2 = 1$. I do not know offhand how elementary the corresponding proofs are.
