# 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.

• Take $(x_n,y_n)$ a solution of $X^2-dY^2=k$ but $(u,v)$ a solution of $X^2-dY^2=1$. Then try the recursion again. – WimC Mar 29 '16 at 20:23
• You can always get a larger solution (not necessarily the next larger solution) by using the exact same recursion. The point is that the recursion is equivalent to the formula $x_{n+1}+y_{n+1}\sqrt d = (x_n + y_n\sqrt d)(u+v\sqrt d)$, together with the fact that the norm map $a+b\sqrt d \mapsto a^2-bd^2$ respects multiplication. So given a solution $x_1,y_1$ to $X^2-dY^2=k$ and a solution $(u,v)$ to $X^2-dY^2=1$, you can find lots of solutions to the $k$-equation by "multiplying" by $(u,v)$ repeatedly (using the recursion). – Greg Martin Mar 29 '16 at 20:23
• @GregMartin from Siegel's methods for counting solutions to quadratic form equal to a constant (or any represented quadratic form), we know that all solutions split into a finite number of orbits under the action of the automorphism group of the quadratic form. I have tried to popularize the Conway method for indefinite binary forms on this site, not really successful; it shows well how to find representatives for the orbits. – Will Jagy Mar 29 '16 at 22:44
• The recursion $(1)$ applies to all $k$. However, the recursion $(2)$ is a square, only for $k=1$, and is the reason why you got $k^2=9$. – Tito Piezas III Mar 29 '16 at 23:41

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.

• Could you offer a little more explanation here? Can you show more steps in how you got the recursive equations in your example? I don't understand how the Identify given is used – Peter Mitrano Dec 31 '18 at 20:34

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

• As we know, $x^2-dy^2=k$ may have more than one fundamental solution for $k>1$. For $x^2 - 5y^2=6061$, then we have four as, $x,y$, $$79,\; 6\\81,\;10\\129,\;46\\159,\;62$$ Using the negative case of the mapping, $$(x,y) \mapsto (9x + 20y, 4x \color{red}\pm 9y)$$ yields the other four in your list. – Tito Piezas III Mar 30 '16 at 0:14
• @TitoPiezasIII sure, there is the improper automorphism $(x,y) \mapsto (x,-y).$ What is your definition of fundamental solution? After answering, I thought (from a Hurwitz idea) that a solution with $x,y > 0$ but either $9x - 20y < 0$ or $-4x + 9y < 0$ could be a definition, as then the inverse mapping $(x,y) \mapsto (9x-20y, -4x+9y)$ takes it to a negative one. – Will Jagy Mar 30 '16 at 0:47
• Let us define $M = x+\sqrt{d}\,y$. Perhaps the $x,y$ with the smallest $M$ in an orbit would be the fundamental one in that particular orbit. – Tito Piezas III Mar 30 '16 at 1:09
• @TitoPiezasIII your idea for naming "fundamental" solutions for Pell type equations has turned out very well. I'm calling them seeds, no matter. Fairly good and error free presentation at math.stackexchange.com/questions/1737385/… Much, much quicker to work with than Conway's method, which nobody else liked anyway. Admitted, more work is needed for less symmetric $a x^2 + b xy + c y^2 = t$ with $b^2 - 4ac> 0$ but not a square. – Will Jagy Apr 12 '16 at 19:22
• @WillJagy: Ok, thanks for the link. – Tito Piezas III Apr 13 '16 at 0:02

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