Generalized Pell's equation

Question

We know that

Let $d$ be a positive square free integer and $r$ an integer satify $r^2+|r|\le d$. Suppose $x$ and $y$ are positive integers that satify $x^2-dy^2=r$. Then $\frac xy$ is a convergent to the continued fraction of $\sqrt d$.

What are the positive integer solutions of $x^2-dy^2=r$ when $r^2+|r|>d$?

Answer 1

All solutions to $ w^2 - 13 v^2 = 15249$ can be constructed by applying the mapping $$ (w,v) \mapsto ( \; 649 w + 2340 v \; , \; \; 180 w + 649 v \;) \; \; $$ to the first eight "SEED" solutions in the output below. For example, $$ (143,20) \mapsto ( \; 649 \cdot 143 + 2340 \cdot 20 \; , \; \; 180 \cdot 143 + 649 \cdot 20 \;) = (139607, 38720) \; \; $$

The exact same thing works for the output below that, all solutions to $ w^2 - 13 v^2 = -15249$ from those eight seed solutions. For example, $$ (26,35) \mapsto ( \; 649 \cdot 26 + 2340 \cdot 35 \; , \; \; 180 \cdot 26 + 649 \cdot 35 \;) = (98774, 27395) \; \; $$

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
  Automorphism matrix:  
    649   2340
    180   649
  Automorphism backwards:  
    649   -2340
    -180   649

  649^2 - 13 180^2 = 1

 w^2 - 13 v^2 = 15249 =  3 13 17 23

Sun Jun 10 18:06:19 PDT 2018

w:  143  v:  20  SEED   KEEP +- 
w:  169  v:  32  SEED   KEEP +- 
w:  689  v:  188  SEED   KEEP +- 
w:  1807  v:  500  SEED   KEEP +- 
w:  2743  v:  760  SEED   BACK ONE STEP  1807 ,  -500
w:  7241  v:  2008  SEED   BACK ONE STEP  689 ,  -188
w:  34801  v:  9652  SEED   BACK ONE STEP  169 ,  -32
w:  46007  v:  12760  SEED   BACK ONE STEP  143 ,  -20
w:  139607  v:  38720
w:  184561  v:  51188
w:  887081  v:  246032
w:  2342743  v:  649760
w:  3558607  v:  986980
w:  9398129  v:  2606572
w:  45171529  v:  12528328
w:  59716943  v:  16562500
w:  181209743  v:  50258540

Sun Jun 10 18:08:25 PDT 2018

 w^2 - 13 v^2 = 15249 =  3 13 17 23

jagy@phobeusjunior:~$ 


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

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
  Automorphism matrix:  
    649   2340
    180   649
  Automorphism backwards:  
    649   -2340
    -180   649

  649^2 - 13 180^2 = 1

 w^2 - 13 v^2 = -15249 =   -1 * 3 13 17 23

Sun Jun 10 18:09:21 PDT 2018

w:  26  v:  35  SEED   KEEP +- 
w:  182  v:  61  SEED   KEEP +- 
w:  962  v:  269  SEED   KEEP +- 
w:  1274  v:  355  SEED   KEEP +- 
w:  3874  v:  1075  SEED   BACK ONE STEP  -1274 ,  355
w:  5122  v:  1421  SEED   BACK ONE STEP  -962 ,  269
w:  24622  v:  6829  SEED   BACK ONE STEP  -182 ,  61
w:  65026  v:  18035  SEED   BACK ONE STEP  -26 ,  35
w:  98774  v:  27395
w:  260858  v:  72349
w:  1253798  v:  347741
w:  1657526  v:  459715
w:  5029726  v:  1394995
w:  6649318  v:  1844189
w:  31959538  v:  8863981
w:  84403774  v:  23409395
w:  128208626  v:  35558675

Sun Jun 10 18:11:27 PDT 2018

 w^2 - 13 v^2 = -15249 =   -1 * 3 13 17 23

jagy@phobeusjunior:~$