All solutions of a Pell's equation $x^2-2y^2=-1$

Question

I want to prove the algorithm below produces all solutions of $x^2-2y^2=-1$. Although this algorithms have been already posted to another posts on mathstack exchange, they don't explain why it find all solution. This is the most important (and difficult) part to prove.

I want to get all integer solutions of $$x^2-2y^2=-1$$ for $x,y>0$. This equation is known as Pell's equation. The minimum solution is $(x,y)=(1,1)$. If we consider the norm of the element of $\mathbb{Q}[\sqrt{2}]$, any $(1+\sqrt2)^k=x_k+\sqrt2y_k$ satisfies $N(x_k+\sqrt2y_k)=N(1+\sqrt{2})^k=(-1)^k$. Thus, we get $$x_k^2-2y_k^2=(-1)^k.$$ So, $(x_{2k-1},y_{2k-1})$ is the solution of $x^2-2y^2=-1.$ I want to know if there is any other solution or to prove this is the only solution.

Answer 1

Given a solution $x^2 - 2 y^2 = -1,$ we can always make a new solution with positive elements by $$ (x,y) \mapsto (3x+4y, 2x+3y) \; . \; $$ This gives all solutions with positive elements, beginning with $(1,1).$ Why?

If we have a solution $(x,y)$ with both fairly large positive, we get a smaller solution with $$ (x,y) \mapsto (3x-4y, -2x+3y) \; . \; $$ However, there is a base case, as the new solution has one or more negative entries if $3x - 4y<0$ or $-2x + 3y < 0.$ It is easy enough to show, with inequalities, that the only positive solution with either condition holding, either $y < \frac{2}{3} x$ or $x < \frac{4}{3} y,$ actually is $(1,1).$ So that's it, every solution with both $x,y$ positive is the result of applying $ (x,y) \mapsto (3x+4y, 2x+3y) \; \; $ to $(1,1)$ a finite number of times. In turn, Cayley-Hamilton tells us that these obey $$ x_{n+2} = 6 x_{n+1} - x_n \; , \; $$ $$ y_{n+2} = 6 y_{n+1} - y_n \; . \; $$ In turn, these recurrences show that both $x_n$ and $y_n$ can be written as powers of $3 \pm 2 \sqrt 2,$ these being the squares of $1 \pm \sqrt 2$

The inqualities: in the first quadrant, on the hyperbola arc we always have $y > \frac{x}{\sqrt 2} > \frac{2x}{3}.$ However, the only integer point of the arc in the first quadrant with $y > \frac{3x}{4}$ is $(1,1).$ Note that the solution point $(7,5)$ is below the green line.

Answer 2

Here is a proof that that’s all the answers: Assime to the contrary that there are other solutions, then we can let $x_c+y_c\sqrt 2$be the smallest other element of $\mathbb Z[\sqrt 2]$ with norm of -1.then you can divide $x_c + y_c\sqrt 2$ by $3+2\sqrt 2$ to find another solution. If $y_c>2$, this would produce a new solution which is smaller producing a contradiction. we can check by hand that there are no other solutions with $y_c \leq 2$, so this is also a contradiction . QED