Does the Pell-like equation $X^2-dY^2=k$ have a simple recursion like $X^2-dY^2=1$?

If $d \ne 0$ is a non-square integer, and $(u,v)$ is an integer solution to the Pell equation
$$
X^2 – dY^2 = 1, \tag{$\star$}
$$
then each solution $(x_i,y_i)$ can be recursively calculated using the formulas
\begin{align}
x_{n+1} &= ux_n + dvy_n, \\
y_{n+1} &= vx_n + uy_n\tag1
\end{align}
n.b. If $(u,v)$ is not the fundamental solution to ($\star$), the recursion still works, though you will instead get $(x_{n+m},y_{n+m})$ for some integer $m$ determined by which solution $(u,v)$ actually is. Thus you can always determine a larger solution to ($\star$), though not necessarily the next largest solution, using only a single solution $(x_n,y_n)$ and the recursion
\begin{align}
x_{n+1} &= x_n^2 + dy_n^2, \\
y_{n+1} &= 2x_ny_n\tag2
\end{align}

QUESTION: Considering the equation
$$
X^2 – dY^2 = k, \qquad k \ne 1,
$$
is there a similar simple recursion to determine $(x_{n+1},y_{n+1})$ knowing only $(x_n,y_n)$ [and possibly, though not necessarily, one other solution $(u,v)$]?

With $d=6$ and $k=3$, I tried applying the recursion for $X^2-6Y^2=1$ to the fundamental solution $(3,1)$ of the equation $X^2-6Y^2=3$, and ended up with a solution to the equation $X^2-6Y^2=9$. Since $9=3^2=k^2$, I feel like there might be just a small adjustment to be made to the recursion, to compensate for $k \ne 1$, but I haven’t found it.

Solutions Collecting From Web of "Does the Pell-like equation $X^2-dY^2=k$ have a simple recursion like $X^2-dY^2=1$?"

Yes. The recursion is just the Brahmagupta-Fibonacci Identity in disguise,

$$(u x + d v y)^2 – d(v x + u y)^2 = (u^2 – d v^2) (x^2 – d y^2) = k$$

The coefficients $u,v$ are determined by the fundamental solution to $u^2 – d v^2=1$. And you simply plug in initial $x_1,y_1$ to $x^2 – d y^2 = k$, whether $k=1$ or not, to get subsequent ones. For ex, the universal recursion for $d = 6$,

$$x^2-6y^2 = k$$

is given by,

$$x_{n+1} = \color{blue}5\,x_n + 12y_n$$

$$y_{n+1} = \color{blue}2\,x_n + 5y_n$$

which uses uses $\color{blue}5^2-6\times\color{blue}2^2=1$. To apply for $k=3$, using $3^2-6\times1^2=3$, hence initial $x_1,y_1 = 3,1$, we get,

$$x_2, y_2 = 27,11$$

so $27^2-6\times11^2=3$, and so on.

Make this an answer. It turns out that, using the recursion you describe, the set of all solutions to $x^2 – dy^2 = k$ split into a small number of orbits. The cleanest way to locate the “seed” values for the different orbits is Conway’s topograph method. In essence, $k=\pm 1$ give the smallest number of orbits, namely one. Not much worse for $k $ prime. The number of orbits increases with the number of prime factors of $k,$ as long as the primes $p$ satisfy $(d|p)= 1.$ There is no truly easy way to find all the necessary seed values when $k$ is such a composite number.

Example: $11$ and $19$ are primes represented by $x^2 – 5 y^2,$ and $11 \cdot 19 = 209.$ The solutions to $x^2 – 5 y^2 = 209$ need more than one orbit under your recursion. We can make it worse by throwing in $29,$ and solving $x^2 – 5 y^2 = 6061.$ The only reason it is not bad is that we have class number one.

Here are the 8 seed pairs I get for $x^2 – 5 y^2 = 6061.$ If you apply the mapping
$$ (x,y) \mapsto (9x + 20y, 4x + 9y) $$
you get a pair with larger entries than any of these 8. A proof that these eight really are enough takes more work, although I have done plenty of these and think the list is complete.

x:  79  y:  6
x:  81  y:  10
x:  129  y:  46
x:  159  y:  62
x:  191  y:  78
x:  241  y:  102
x:  529  y:  234
x:  591  y:  262

Why not? Here is a longer list, including pairs from the same orbits:

x:  79  y:  6
x:  81  y:  10
x:  129  y:  46
x:  159  y:  62
x:  191  y:  78
x:  241  y:  102
x:  529  y:  234
x:  591  y:  262
x:  831  y:  370
x:  929  y:  414
x:  2081  y:  930
x:  2671  y:  1194
x:  3279  y:  1466
x:  4209  y:  1882
x:  9441  y:  4222
x:  10559  y:  4722
x:  14879  y:  6654
x:  16641  y:  7442
x:  37329  y:  16694
x:  47919  y:  21430
x:  58831  y:  26310
x:  75521  y:  33774
x:  169409  y:  75762
x:  189471  y:  84734
x:  266991  y:  119402
x:  298609  y:  133542
x:  669841  y:  299562
x:  859871  y:  384546
x:  1055679  y:  472114
x:  1355169  y:  606050
x:  3039921  y:  1359494
x:  3399919  y:  1520490
x:  4790959  y:  2142582
x:  5358321  y:  2396314
x:  12019809  y:  5375422
x:  15429759  y:  6900398
x:  18943391  y:  8471742
x:  24317521  y:  10875126

EDIT: it is possible to make a definition of “fundamental solution” that fits well into the group action on the form. As $x,y$ get large, we know that $y/x \approx 1/\sqrt 5 \approx 0.447213596.$ For large $x,y,$ we also know we can back up the solution by the inverse mapping,
$$ (x,y) \mapsto (9x-20y, -4x+9y) $$
and get another solution with positive $x,y.$ So, in a nod to Hurwitz, why not call a solution fundamental if either $9x-20y < 0$ or $-4x+9y < 0?$ That way, a solution is fundamental if either $y/x < 0.45$ or $y/x > 0.4444444.$ Below I list the first few solutions with the ratio $y/x$ in decimal. If that decimal is close to $0.44721$ then the solution is not fundamental. This can be upgraded to an “effective” set of bounds on $x,y$ to show that the set of fundamental solutions is finite. Good.

x:  79  y:  6 ratio: 0.0759494  fundamental 
x:  81  y:  10 ratio: 0.123457  fundamental 
x:  129  y:  46 ratio: 0.356589  fundamental 
x:  159  y:  62 ratio: 0.389937  fundamental 
x:  191  y:  78 ratio: 0.408377  fundamental 
x:  241  y:  102 ratio: 0.423237  fundamental 
x:  529  y:  234 ratio: 0.442344  fundamental 
x:  591  y:  262 ratio: 0.443316  fundamental 
x:  831  y:  370 ratio: 0.445247
x:  929  y:  414 ratio: 0.44564
x:  2081  y:  930 ratio: 0.446901
x:  2671  y:  1194 ratio: 0.447024
x:  3279  y:  1466 ratio: 0.447088
x:  4209  y:  1882 ratio: 0.447137
x:  9441  y:  4222 ratio: 0.447198
x:  10559  y:  4722 ratio: 0.447201
x:  14879  y:  6654 ratio: 0.447207
x:  16641  y:  7442 ratio: 0.447209
x:  37329  y:  16694 ratio: 0.447213
x:  47919  y:  21430 ratio: 0.447213
x:  58831  y:  26310 ratio: 0.447213
x:  75521  y:  33774 ratio: 0.447213
x:  169409  y:  75762 ratio: 0.447214
x:  189471  y:  84734 ratio: 0.447214

I did the same run for $x^2 – 5 y^2 = -6061.$ Here the ratio $y/x$ decreases until it gets lower than $0.45$

x:  8  y:  35 ratio: 4.375  fundamental 
x:  28  y:  37 ratio: 1.32143  fundamental 
x:  112  y:  61 ratio: 0.544643  fundamental 
x:  128  y:  67 ratio: 0.523438  fundamental 
x:  188  y:  91 ratio: 0.484043  fundamental 
x:  212  y:  101 ratio: 0.476415  fundamental 
x:  488  y:  221 ratio: 0.452869  fundamental 
x:  628  y:  283 ratio: 0.450637  fundamental 
x:  772  y:  347 ratio: 0.449482
x:  992  y:  445 ratio: 0.448589
x:  2228  y:  997 ratio: 0.447487
x:  2492  y:  1115 ratio: 0.447432
x:  3512  y:  1571 ratio: 0.447323
x:  3928  y:  1757 ratio: 0.447301
x:  8812  y:  3941 ratio: 0.447231
x:  11312  y:  5059 ratio: 0.447224
x:  13888  y:  6211 ratio: 0.447221
x:  17828  y:  7973 ratio: 0.447218
x:  39992  y:  17885 ratio: 0.447214
x:  44728  y:  20003 ratio: 0.447214
x:  63028  y:  28187 ratio: 0.447214
x:  70492  y:  31525 ratio: 0.447214
x:  158128  y:  70717 ratio: 0.447214
x:  202988  y:  90779 ratio: 0.447214

I thought the idea for naming some “fundamental” solutions, from yesterday, was pretty good. I wrote a program to do that. I wanted to show what can happen if the target number is not squarefree. In the following output, $x^2 – 5 y^2 = 121,$ one out of three $(x,y)$ is just $11$ times a pair that solves $x^2 – 5 y^2 = 1.$

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental

 x^2 - 5 y^2 = 121

x:  11  y:  0 ratio: 0  fundamental 
x:  21  y:  8 ratio: 0.380952  fundamental 
x:  29  y:  12 ratio: 0.413793  fundamental 
x:  99  y:  44 ratio: 0.444444
x:  349  y:  156 ratio: 0.446991
x:  501  y:  224 ratio: 0.447106
x:  1771  y:  792 ratio: 0.447205
x:  6261  y:  2800 ratio: 0.447213
x:  8989  y:  4020 ratio: 0.447213
x:  31779  y:  14212 ratio: 0.447214
x:  112349  y:  50244 ratio: 0.447214
x:  161301  y:  72136 ratio: 0.447214
x:  570251  y:  255024 ratio: 0.447214
x:  2016021  y:  901592 ratio: 0.447214
x:  2894429  y:  1294428 ratio: 0.447214
x:  10232739  y:  4576220 ratio: 0.447214


 x^2 - 5 y^2 = 121

jagy@phobeusjunior:~$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Why not, here is $x^2 – 5 y^2 = -121.$

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental

 x^2 - 5 y^2 = -121

x:  2  y:  5 ratio: 2.5  fundamental 
x:  22  y:  11 ratio: 0.5  fundamental 
x:  82  y:  37 ratio: 0.45122  fundamental 
x:  118  y:  53 ratio: 0.449153
x:  418  y:  187 ratio: 0.447368
x:  1478  y:  661 ratio: 0.447226
x:  2122  y:  949 ratio: 0.44722
x:  7502  y:  3355 ratio: 0.447214
x:  26522  y:  11861 ratio: 0.447214
x:  38078  y:  17029 ratio: 0.447214
x:  134618  y:  60203 ratio: 0.447214
x:  475918  y:  212837 ratio: 0.447214
x:  683282  y:  305573 ratio: 0.447214
x:  2415622  y:  1080299 ratio: 0.447214
x:  8540002  y:  3819205 ratio: 0.447214
x:  12260998  y:  5483285 ratio: 0.447214


 x^2 - 5 y^2 = -121

jagy@phobeusjunior:~$

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

Here is a good pair, $x^2 – 11 y^2 = 14$ and then $x^2 – 11 y^2 = 350 = 14 \cdot 25.$

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental

 x^2 - 11 y^2 = 14

Wed Mar 30 11:32:36 PDT 2016

x:  5  y:  1 ratio: 0.2  fundamental 
x:  17  y:  5 ratio: 0.294118  fundamental 
x:  83  y:  25 ratio: 0.301205
x:  335  y:  101 ratio: 0.301493
x:  1655  y:  499 ratio: 0.301511
x:  6683  y:  2015 ratio: 0.301511
x:  33017  y:  9955 ratio: 0.301511
x:  133325  y:  40199 ratio: 0.301511
x:  658685  y:  198601 ratio: 0.301511
x:  2659817  y:  801965 ratio: 0.301511
x:  13140683  y:  3962065 ratio: 0.301511

Wed Mar 30 11:32:56 PDT 2016

 x^2 - 11 y^2 = 14

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental

 x^2 - 11 y^2 = 350

Wed Mar 30 11:29:54 PDT 2016

x:  19  y:  1 ratio: 0.0526316  fundamental 
x:  25  y:  5 ratio: 0.2  fundamental 
x:  41  y:  11 ratio: 0.268293  fundamental 
x:  47  y:  13 ratio: 0.276596  fundamental 
x:  85  y:  25 ratio: 0.294118  fundamental 
x:  157  y:  47 ratio: 0.299363  fundamental 
x:  223  y:  67 ratio: 0.300448
x:  415  y:  125 ratio: 0.301205
x:  773  y:  233 ratio: 0.301423
x:  899  y:  271 ratio: 0.301446
x:  1675  y:  505 ratio: 0.301493
x:  3121  y:  941 ratio: 0.301506
x:  4441  y:  1339 ratio: 0.301509
x:  8275  y:  2495 ratio: 0.301511
x:  15419  y:  4649 ratio: 0.301511
x:  17933  y:  5407 ratio: 0.301511
x:  33415  y:  10075 ratio: 0.301511
x:  62263  y:  18773 ratio: 0.301511
x:  88597  y:  26713 ratio: 0.301511
x:  165085  y:  49775 ratio: 0.301511
x:  307607  y:  92747 ratio: 0.301511
x:  357761  y:  107869 ratio: 0.301511
x:  666625  y:  200995 ratio: 0.301511
x:  1242139  y:  374519 ratio: 0.301511

Wed Mar 30 11:29:55 PDT 2016

 x^2 - 11 y^2 = 350

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

So writes the Pell equation in General form.

$$Ap^2-Bs^2=k$$

If we know any solution of this equation. $( p ; s)$

If we use any solutions of the following equation Pell.

$$x^2-ABy^2=1$$

Then the following solution of the desired equation can be found by the formula.

$$p_2=xp+Bys$$

$$s_2=xs+Ayp$$