# Pell equation ($x^2 - ny^2 = 1$): Why does $(x_{1}+y_{1}{\sqrt {n}})^{k}$ give all solutions?

Trying to solve a Pell equation (Diophantine equation $x^2 - ny^2 = 1$ where $n$ is not a square), we can generate all the solutions in the following way:

Given a fundamental solution $(x_1, y_1)$, we can find all other solutions by solving $$x_{k}+y_{k}{\sqrt {n}}=(x_{1}+y_{1}{\sqrt {n}})^{k},} \tag{*}\label{*}$$ for $k \in \mathbb{Z}$. (This can be solved by separating rational and irrational parts)

$\$

My question is: why? That is, why would it be a good idea to look for solutions like this (i) , and more importantly, why does it give all solutions? (ii)

(Bonus question: same but for $x^2 + ny^2 = -1$ solvable)

$\$

Anywhere that I could find this equation online, it is considered 'common' knowledge and therefore needs no explanation. I have not been able to find a proof.

What I have thus far: (i) $(x_1, y_1)$ is a solution, thus: $x_1^2 + ny_1^2 = 1$. Furthermore, for any $(x, y)$ we have $x^2 - ny^2 = (x - \sqrt{n}y)(x + \sqrt{n}y)$. Thus, for $k \in \mathbb{N}$ and any solution $(x, y)$:

\begin{align} (x - \sqrt{n}y)(x + \sqrt{n}y) &= x^2 - ny^2 = 1 = 1^k\ \\ &= (x_1^2 - ny_1^2)^k = (x_1 - \sqrt{n}y_1)^k(x_1 + \sqrt{n}y_1)^k\end{align} Now we can take only $(x + \sqrt{n}y)$ and $(x_1 + \sqrt{n}y_1)^k$ for some reason?

Also, if we assume \eqref{*} to be true, we can find the recurrence relations: $$\displaystyle x_{k+1} = x_1 x_k + n y_1 y_k,$$ $$\displaystyle y_{k+1} = x_1 y_k + y_1 x_k.$$ Since we can assume the fundamental solution won't have either zero I suppose we can conclude that each $x_k$ and $y_k$ will be unique. (ii) However, I still fail to see how this generates all solutions.

(i) Using (*) is simpler than calculating the convergents of $\sqrt n$, which is another way of solving Pell's equation.
Suppose that there is a positive solution $s, t$ that is not in the collection $\{x_k, y_k\}$. Because both $x_1 + y_1\sqrt n$ and $s + t\sqrt n$ are greater than 1, there must be some integer $m$ such that $$(x_1 + y_1\sqrt n)^m < s + t\sqrt n < (x_1 + y_1\sqrt n)^{m+1}.$$ Now $$(x_1 - y_1\sqrt n)^m = (x_1 + y_1\sqrt n)^{-m},$$ and we can multiply each part of the compound inequality by one or the other of those two equal expressions to obtain $$1 < (s + t\sqrt n)(x_1 - y_1\sqrt n)^m < x_1 + y_1\sqrt n.$$ Defining integers $a, b$ by $a + b\sqrt n = (s + t\sqrt n)(x_1 - y_1\sqrt n)^m$, we have $$a^2 - b^2n = (s^2 - t^2n)(x_1^2 - y_1^2n)^m = 1,$$ so $a,b$ is a solution of $x^2 - ny^2 = 1$ such that $1 < a + b\sqrt n < x_1 + y_1\sqrt n$. By the first part of that compound inequality and the fact that $0 < (a + b\sqrt n)^{-1} = a - b\sqrt n$, we have $0 < a - b\sqrt n < 1$.
Now \begin{align} a & = \frac{1}{2}(a + b\sqrt n) + \frac{1}{2}(a - b\sqrt n) > \frac{1}{2} + \, 0 \, > 0\\ b\sqrt n & = \frac{1}{2}(a + b\sqrt n) - \frac{1}{2}(a - b\sqrt n) > \frac{1}{2} - \frac{1}{2} = 0, \end{align} so $a, b$ is a positive solution. Therefore $a > x_1, b > y_1,$ which contradicts $a + b\sqrt n < x_1 + y_1\sqrt n$, and hence our supposition is false. Thus, all positive solutions are given by the collection $x_k, y_k$.
Assume that $x^2 - ny^2 = -1$ is solvable. Let $x_1, y_1$ be the smallest solution. Then all solutions of $x^2 - ny^2 = -1$ are given by $x_k, y_k$ where $x_k + y_k\sqrt n = (x_1 + y_1\sqrt n)^k$ with $k = 1, 3, 5, 7, \ldots$, and that all solutions of $x^2 - ny^2 = 1$ are given by $x_k, y_k$ with $k = 2, 4, 6, 8, \ldots$.