3
$\begingroup$

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 ?

$\endgroup$
11
  • $\begingroup$ As I understand from some recent readings the full set of fundamental solutions with some $D$ and $k$ has always been found by trying in a finite set of possible fundamental solutions. For instance in example 4.2 in "Pell's Equation, II" by Keith Conrad for $(D,k)=(7,57)$ he finds $(x,y)=(\pm 8,\pm 1),(\pm 13, \pm4),(\pm 20,\pm 7)$ as fundamental solutions. He finds then redundancy in this so that the first two solutions remain. But there is no method mentioned to find that solutions other than trying up to a determinable upper bound for $(x,y)$. $\endgroup$
    – Gottfried Helms
    Jun 9, 2018 at 10:53
  • 1
    $\begingroup$ It seems difficult to find a definition of what "fundamental" means. In the Conrad-article (or an older one, don't have it at hand at the moment), the "fundamental" solution in an infinite set of solutions, which is connected by the typical recursion formula, is that of the smallest absolute values in $x$ or in $y$ or somehow in both, don't know. So in the example above $(x_{0,0},y_{0,0})=(8,1)$ is one fundamental solution and an infinite set can be generated by the simple, well known, recursion. But the solution $(x_{1,0},y_{1,0})=(13,4)$ can not be reached by the recursion ... $\endgroup$
    – Gottfried Helms
    Jun 9, 2018 at 14:32
  • 1
    $\begingroup$ ... and I understood the text of Conrad such that this makes it a second "fundamental" solution because it is somehow the root of another infinite set of solutions derived from the same recursion rule as with $(x_{0,k},y_{0,k})$ - being "fundamental" meaning it is that solution of the second set with the -somehow- smallest values in $(x_{1,k},y_{1,k})$ . However I didn't remember an explicite definition of this "fundamental"-term in the few readings that I've done about this. $\endgroup$
    – Gottfried Helms
    Jun 9, 2018 at 14:36
  • 1
    $\begingroup$ I have a copy of G.Chrystal (1895), "Algebra - an elementary textbook", Part II as pdf-file. There from page 480 on he describes how to get "initial" or "primary" solutions by checking possible combinations of $(x,y)$ up to $\sqrt D$ whether they come out to be squares. It is very explicite, but I even didn't see the term "fundamental" there or in the near (I didn't search more) $\endgroup$
    – Gottfried Helms
    Jun 9, 2018 at 14:52
  • 1
    $\begingroup$ @GottfriedHelms The idea of separating solutions by orbits under the integral automorphism group is the heart of Siegel's approach to counting representations, in this case for indefinite binary forms. My answer below gives a good enough description for Pell type, as the group is, well, familiar. Oh: the main thing is that there are a finite number of such orbit representative solutions, but not necessarily just one. $\endgroup$
    – Will Jagy
    Jun 11, 2018 at 0:24

2 Answers 2

Reset to default
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Will - Desmos is a nice tool! Do you see the possibility to mark the rational/integral points in some way explicitely - I'm not yet much experienced with Desmos myself... $\endgroup$
    – Gottfried Helms
    Jun 12, 2018 at 8:43
0
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I ask for the FUNDAMENTAL solutions $\endgroup$
    – Peter
    Jun 7, 2018 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.