# Recurrence formula in Pell's equation

by basil
Tags: equation, formula, pell, recurrence
 P: 96 Let x$_{1}$, y$_{1}$ be basic solutions to x^2-N*y^2 = 1, with N a non-square integer number then we have the following recurrence relations for k>1: x$_{k+1}$:=x$_{1}$*x$_{k}$+N*y$_{1}$*y$_{k}$ y$_{k+1}$:=x$_{1}$*y$_{k}$+y$_{1}$*x$_{k}$ For N=2, (2,3) being the basic solution, we have (17,12) as 2. and (99,70) as 3.solution A trivial algorithm to find the basic solution could be: y:=1, max:=999 Do While n < max $\cdots$Compute w=1+N*y^2 $\cdots$If w is an integral square x^2 then $\cdots\cdots$Return "Basic solution: (x, y)" and Stop $\cdots$End_If $\cdots$Incr y End_Do Return max & " trials and no solution" and Stop Because there are values of N, whrer this "Q&D"-algorithm fails, who has experience with with non-trivial algorithms for basic solutions to the Pell equation?