Why continued fraction gives initial solution of Pell's equation

Question

According to wikipedia, following algorithm find the smallest solution of $x^2-dy^2=1$. How the validity of this algorithm is shown?

1. Let $α_0 :=\sqrt{d}$.

2. Let $q_i:= ⌊α_i⌋$, $α_{i+1} := 1/(αi − qi)$ and construct the infinite series. Such series always have finite period.

3. Let the series above $q_0, q_1, \ldots , q_{m−1}, q_m , q_1, \ldots$. The period is $m-1$. Let $b:=[q_0; q_1, \ldots , q_{m−1}]=q_0+\frac{1}{q_1+\frac{1}{\ldots+q_{m-1}}}$

4. Let $b:=x/y$ (x and y are coprime). Then, $x^2-dy^2=\pm1$. If $x^2-dy^2=1$, output $\langle x,y\rangle$. Otherwise, output $\langle x^2+dy^2,2xy\rangle$

Answer 1

There is no quick answer to that, you have to study continued fractions. A starting point would be the 4 online pdf-s that I referred to in this query: algebra direct connect pell eqn soln $(p_{nk},q_{nk})$ with $(p_n + q_n\sqrt{D})^k$