How can I find the complete set of fundamental solutions of a pell-like equation?

450 Views Asked by At

Let $D>1$ be a non-square-integer and assume that $$x^2-Dy^2=k$$ with integer $k$ has a solution with integers $x,y$.

How can I find the complete set of fundamental solutions , if I know one solution ?

I tried to use that , assuming that $a^2-Db^2=1$, with the solution $(u/v)$ , the pair $$(au-bvD,av-bu)$$ is a solution as well. If a solution $(x/y)$ is known, can I calculate the fundamental solutions with this approach, or do I need more ?

2

There are 2 best solutions below

1
On

When $k$ is one of $1,-1,p,-p$ for $p$ a prime number, your idea is enough. For prime, you just need to apply your idea to both $(x,y)$ and $(x,-y).$

As the number of prime factors of $k$ increases, more is needed. The reliable method is Conway's Topograph. For the special case of Pell type, we can predict inequalities. All solutions of $x^2 - 2 y^2 = 84847$ with both $x,y > 0$ can be constructed from the first sixteen solutions below by repetitions of the mapping $$ (x,y) \mapsto (3x+4y, 2x+3y) \; .$$ That is to say, the first 16 solutions below all have either $3x-4y \leq 0$ or $-2x+3y \leq 0.$ For these, since $84847 > 0,$ it is always the second inequality, which can be written $y \leq \frac{2}{3} x,$ or $v \leq \frac{2}{3} w$ using the letters in the output. When both numbers are large, $w - v \sqrt 2 = \frac{84847}{w + v \sqrt 2}$ tells us that $v \approx \frac{w}{\sqrt 2} \approx 0.7071 \; w \; ,$ therefore $v$ becomes larger than $\frac{2}{3} w \; $ as both numbers increase.

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
  Automorphism matrix:  
    3   4
    2   3
  Automorphism backwards:  
    3   -4
    -2   3

  3^2 - 2 2^2 = 1

 w^2 - 2 v^2 = 84847

Wed Jun  6 10:41:21 PDT 2018

w:  295  v:  33  SEED   KEEP +- 
w:  297  v:  41  SEED   KEEP +- 
w:  303  v:  59  SEED   KEEP +- 
w:  313  v:  81  SEED   KEEP +- 
w:  335  v:  117  SEED   KEEP +- 
w:  353  v:  141  SEED   KEEP +- 
w:  375  v:  167  SEED   KEEP +- 
w:  407  v:  201  SEED   KEEP +- 
w:  417  v:  211  SEED   BACK ONE STEP  407 ,  -201
w:  457  v:  249  SEED   BACK ONE STEP  375 ,  -167
w:  495  v:  283  SEED   BACK ONE STEP  353 ,  -141
w:  537  v:  319  SEED   BACK ONE STEP  335 ,  -117
w:  615  v:  383  SEED   BACK ONE STEP  313 ,  -81
w:  673  v:  429  SEED   BACK ONE STEP  303 ,  -59
w:  727  v:  471  SEED   BACK ONE STEP  297 ,  -41
w:  753  v:  491  SEED   BACK ONE STEP  295 ,  -33
w:  1017  v:  689
w:  1055  v:  717
w:  1145  v:  783
w:  1263  v:  869
w:  1473  v:  1021
w:  1623  v:  1129
w:  1793  v:  1251
w:  2025  v:  1417
w:  2095  v:  1467
w:  2367  v:  1661
w:  2617  v:  1839
w:  2887  v:  2031
w:  3377  v:  2379
w:  3735  v:  2633
w:  4065  v:  2867
w:  4223  v:  2979
w:  5807  v:  4101
w:  6033  v:  4261
w:  6567  v:  4639
w:  7265  v:  5133
w:  8503  v:  6009
w:  9385  v:  6633
w:  10383  v:  7339
w:  11743  v:  8301
w:  12153  v:  8591
w:  13745  v:  9717
w:  15207  v:  10751
w:  16785  v:  11867
w:  19647  v:  13891
w:  21737  v:  15369
w:  23663  v:  16731
w:  24585  v:  17383
w:  33825  v:  23917
w:  35143  v:  24849
w:  38257  v:  27051
w:  42327  v:  29929
w:  49545  v:  35033
w:  54687  v:  38669
w:  60505  v:  42783
w:  68433  v:  48389
w:  70823  v:  50079
w:  80103  v:  56641
w:  88625  v:  62667
w:  97823  v:  69171
w:  114505  v:  80967

Wed Jun  6 10:41:21 PDT 2018

 w^2 - 2 v^2 = 84847

jagy@phobeusjunior:~$ 

Here is a picture, I put a much lower target number, $x^2 - 2 y^2 = 17$ and $y \leq \frac{2}{3} x$ Shows where the "seed" solutions lie with target 17. enter image description here

=============================================================

Why not, here is what happens when I negate the value of $k$

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental
  Automorphism matrix:  
    3   4
    2   3
  Automorphism backwards:  
    3   -4
    -2   3

  3^2 - 2 2^2 = 1

 w^2 - 2 v^2 = -84847 =   -1 * 7 17 23 31

Wed Jun  6 12:01:02 PDT 2018

w:  5  v:  206  SEED   KEEP +- 
w:  41  v:  208  SEED   KEEP +- 
w:  71  v:  212  SEED   KEEP +- 
w:  101  v:  218  SEED   KEEP +- 
w:  151  v:  232  SEED   KEEP +- 
w:  185  v:  244  SEED   KEEP +- 
w:  215  v:  256  SEED   KEEP +- 
w:  229  v:  262  SEED   KEEP +- 
w:  361  v:  328  SEED   BACK ONE STEP  -229 ,  262
w:  379  v:  338  SEED   BACK ONE STEP  -215 ,  256
w:  421  v:  362  SEED   BACK ONE STEP  -185 ,  244
w:  475  v:  394  SEED   BACK ONE STEP  -151 ,  232
w:  569  v:  452  SEED   BACK ONE STEP  -101 ,  218
w:  635  v:  494  SEED   BACK ONE STEP  -71 ,  212
w:  709  v:  542  SEED   BACK ONE STEP  -41 ,  208
w:  809  v:  608  SEED   BACK ONE STEP  -5 ,  206
w:  839  v:  628
w:  955  v:  706
w:  1061  v:  778
w:  1175  v:  856
w:  1381  v:  998
w:  1531  v:  1102
w:  1669  v:  1198
w:  1735  v:  1244
w:  2395  v:  1706
w:  2489  v:  1772
w:  2711  v:  1928
w:  3001  v:  2132
w:  3515  v:  2494
w:  3881  v:  2752
w:  4295  v:  3044
w:  4859  v:  3442
w:  5029  v:  3562
w:  5689  v:  4028
w:  6295  v:  4456
w:  6949  v:  4918
w:  8135  v:  5756
w:  9001  v:  6368
w:  9799  v:  6932
w:  10181  v:  7202
w:  14009  v:  9908
w:  14555  v:  10294
w:  15845  v:  11206
w:  17531  v:  12398
w:  20521  v:  14512
w:  22651  v:  16018
w:  25061  v:  17722
w:  28345  v:  20044
w:  29335  v:  20744
w:  33179  v:  23462
w:  36709  v:  25958
w:  40519  v:  28652
w:  47429  v:  33538
w:  52475  v:  37106
w:  57125  v:  40394
w:  59351  v:  41968
w:  81659  v:  57742
w:  84841  v:  59992
w:  92359  v:  65308
w:  102185  v:  72256
w:  119611  v:  84578

Wed Jun  6 12:01:02 PDT 2018

 w^2 - 2 v^2 = -84847 =   -1 * 7 17 23 31

jagy@phobeusjunior:~$ 

Another picture, this time $x^2 - 2 y^2 = -17$ and $x \leq \frac{4}{3}y$ enter image description here

1
On

Knowing any solution to the equation.

$$x^2-Dy^2=k$$

And knowing any solution to the equation.

$$a^2-Db^2=1$$

You can find the following solution using the formula.

$$x_2=ax+Dby$$

$$y_2=bx+ay$$