How do I find another generalized Pell equation solution after finding the fundamental solution?

Question

If I have a solution $(x_0, y_0)$ to $x^2 - Dy^2 = k$ where D > 1 is not a square, how do I find another solution $(x_1,y_1)$ to $x^2 - Dy^2 = k$ without knowing the solution $(u,v)$ to $u^2 - Dv^2 = 1$ ?

I can find the first solution with Conway's topograph quite easily. However, the second solution shows up at the end of the period in the river of Conway's topograph (the river shows up in the topograph of indefinite binary quadratic forms).

I have read multiple answers to similar questions, but the prerequisite for solving the problem is to first find a fundamental solution to $x^2 - Dy^2 = 1$, which I do not have.

Edit 1: Forgot to mention that $D$ is too large to try computing the continued fraction. I tried this code implementing the algorithm for this, and it took a long time. Also, $k$ is not necessarily prime, I am looking for a general solution.

---

Here's what I have tried on my own:

I used this code to test out the chakravala method but it was slow.

• I have read Barbeau's book on the Pell Equation and started Buell's book.
• I read chapters 9-11 of An Illustrated Theory of Numbers.
• I read The Sensual (Quadratic) Form but only understood the chapters about the topograph.

Answer 1

Why do you want to find more integral solutions without ever using information about integral solutions to the equation $x^2 - Dy^2 = 1$?

The main structure theorem about integral solutions to $x^2 - Dy^2 = k$ is threefold:

(i) when $(x_0,y_0)$ is an integral solution to $x^2 - Dy^2 = k$, so are the coefficients of $(x_0 + y_0\sqrt{D})(a+b\sqrt{D})$ where $(a,b)$ is an arbitrary solution to $x^2 - Dy^2 = 1$,

(ii) there are finitely many integral solutions $(x_0,y_0),\ldots,(x_m,y_m)$ to $x^2 - Dy^2 = k$ such that every other integral solution to this equation occurs as coefficients of $(x_i+y_i\sqrt{D})(a+b\sqrt{D})$ for some $i = 1,\ldots,m$ and $a^2 - Db^2 = 1$,

(iii) in terms of one $(a,b)$ where $a^2 - Db^2 = 1$ and $a, b \geq 1$, you can find the finitely many solutions $(x_i,y_i)$ for (ii) in an explicit box in the plane.

See Theorem 3.3 and Corollary 3.5 here. Section 4 there has several worked examples.

You say in your answer that "$D$ is too large to try computing the continued fraction" of $\sqrt{D}$. What kind of $D$ are you using? If you find enough integral solutions to $x^2 - Dy^2 = k$, then taking a suitable ratio $(x+y\sqrt{D})/(x'+y'\sqrt{D})$ for some of them is going to give you a solution to $x^2 - Dy^2 = 1$, so bypassing the direct use of solutions to the Pell equation in solving he generalized Pell equation is going to amount to solving the Pell equation by another method. So maybe you should look at a survey paper on ways to solve Pell equations, like Lenstra's AMS Notices article https://www.ams.org/notices/200202/fea-lenstra.pdf.

Answer 2

All solutions of equation $a^2-91b^2=-10$ derives from modulo polynomial $a+bx\equiv(-x\pm9)(-1574-165x)^j\pmod{x^2-91}$ where $j=$0,1,2,....

pari/gp code:

{
  D= 91; C= -10;
  Q= bnfinit('x^2-D,1);
  fu= Q.fu[1]; print("Fundamental Unit: "fu);
  N= bnfisintnorm(Q, C); print("Fundamental Solutions (Norm): "N);
  for(k=1, #N, n= N[k];
   print("\n\nNorm: "n"\n");
   for(j=0, 8,
    s= lift(n*fu^j);
    X= abs(polcoeff(s, 0)); Y= abs(polcoeff(s, 1));  
    if(X^2-D*Y^2==C, if(Y, if(X==floor(X), if(Y==floor(Y),
     y= Y; x= X; 
     print("("x", "y")    j = "j);
    ))))
   )
  )
};

Output:

Fundamental Unit: Mod(-165*x - 1574, x^2 - 91)
Fundamental Solutions (Norm): [-x + 9, -x - 9]


Norm: -x + 9

(9, 1)    j = 0
(849, 89)    j = 1
(2672661, 280171)    j = 2
(8413535979, 881978219)    j = 3
(26485808589231, 2776467153241)    j = 4
(83377317025363209, 8740317716424449)    j = 5
(262471767510034792701, 27514517394837012211)    j = 6
(826261040744272502059539, 86615692018629198015779)    j = 7
(2601069493791202326448636071, 272666170960127320516660081)    j = 8


Norm: -x - 9

(9, 1)    j = 0
(29181, 3059)    j = 1
(91861779, 9629731)    j = 2
(289180851111, 30314390129)    j = 3
(910341227435649, 95429690496361)    j = 4
(2865753894786571941, 300412635368154299)    j = 5
(9021392350446901034619, 945698880709259236891)    j = 6
(28399340253452949670408671, 2977059776060112709578569)    j = 7
(89401114096477535115545461689, 9371783229338354100494098321)    j = 8

Answer 3

here is a method for standard Pell

Method described by Prof. Lubin at Continued fraction of $\sqrt{67} - 4$

$$ \sqrt { 91} = 9 + \frac{ \sqrt {91} - 9 }{ 1 } $$ $$ \frac{ 1 }{ \sqrt {91} - 9 } = \frac{ \sqrt {91} + 9 }{10 } = 1 + \frac{ \sqrt {91} - 1 }{10 } $$ $$ \frac{ 10 }{ \sqrt {91} - 1 } = \frac{ \sqrt {91} + 1 }{9 } = 1 + \frac{ \sqrt {91} - 8 }{9 } $$ $$ \frac{ 9 }{ \sqrt {91} - 8 } = \frac{ \sqrt {91} + 8 }{3 } = 5 + \frac{ \sqrt {91} - 7 }{3 } $$ $$ \frac{ 3 }{ \sqrt {91} - 7 } = \frac{ \sqrt {91} + 7 }{14 } = 1 + \frac{ \sqrt {91} - 7 }{14 } $$ $$ \frac{ 14 }{ \sqrt {91} - 7 } = \frac{ \sqrt {91} + 7 }{3 } = 5 + \frac{ \sqrt {91} - 8 }{3 } $$ $$ \frac{ 3 }{ \sqrt {91} - 8 } = \frac{ \sqrt {91} + 8 }{9 } = 1 + \frac{ \sqrt {91} - 1 }{9 } $$ $$ \frac{ 9 }{ \sqrt {91} - 1 } = \frac{ \sqrt {91} + 1 }{10 } = 1 + \frac{ \sqrt {91} - 9 }{10 } $$ $$ \frac{ 10 }{ \sqrt {91} - 9 } = \frac{ \sqrt {91} + 9 }{1 } = 18 + \frac{ \sqrt {91} - 9 }{1 } $$

Simple continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccc} & & 9 & & 1 & & 1 & & 5 & & 1 & & 5 & & 1 & & 1 & & 18 & \\ \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 9 }{ 1 } & & \frac{ 10 }{ 1 } & & \frac{ 19 }{ 2 } & & \frac{ 105 }{ 11 } & & \frac{ 124 }{ 13 } & & \frac{ 725 }{ 76 } & & \frac{ 849 }{ 89 } & & \frac{ 1574 }{ 165 } \\ \\ & 1 & & -10 & & 9 & & -3 & & 14 & & -3 & & 9 & & -10 & & 1 \end{array} $$

$$ \begin{array}{cccc} \frac{ 1 }{ 0 } & 1^2 - 91 \cdot 0^2 = 1 & \mbox{digit} & 9 \\ \frac{ 9 }{ 1 } & 9^2 - 91 \cdot 1^2 = -10 & \mbox{digit} & 1 \\ \frac{ 10 }{ 1 } & 10^2 - 91 \cdot 1^2 = 9 & \mbox{digit} & 1 \\ \frac{ 19 }{ 2 } & 19^2 - 91 \cdot 2^2 = -3 & \mbox{digit} & 5 \\ \frac{ 105 }{ 11 } & 105^2 - 91 \cdot 11^2 = 14 & \mbox{digit} & 1 \\ \frac{ 124 }{ 13 } & 124^2 - 91 \cdot 13^2 = -3 & \mbox{digit} & 5 \\ \frac{ 725 }{ 76 } & 725^2 - 91 \cdot 76^2 = 9 & \mbox{digit} & 1 \\ \frac{ 849 }{ 89 } & 849^2 - 91 \cdot 89^2 = -10 & \mbox{digit} & 1 \\ \frac{ 1574 }{ 165 } & 1574^2 - 91 \cdot 165^2 = 1 & \mbox{digit} & 18 \\ \end{array} $$

Putting the $(x_n, y_n)$ pairs that solve $x_n^2 - 91 y_n^2 = -10$ in increasing order, we get recurrences $$ x_{n+4} = 3148 x_{n+2} - x_n,$$

$$ y_{n+4} = 3148 y_{n+2} - y_n.$$

The pairs are $$ (-849, 89) $$ $$ (-9, 1) $$ $$ ( 9, 1) $$ $$ (849, 89) $$ $$ (29181, 3059) $$ $$ (2672661, 280171) $$