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$


1 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$


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .