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

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 ?

• 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)$. – Gottfried Helms Jun 9 '18 at 10:53
• 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 ... – Gottfried Helms Jun 9 '18 at 14:32
• ... 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. – Gottfried Helms Jun 9 '18 at 14:36
• 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) – Gottfried Helms Jun 9 '18 at 14:52
• @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. – Will Jagy Jun 11 '18 at 0:24

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.

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

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$

• 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... – Gottfried Helms Jun 12 '18 at 8:43

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

• I ask for the FUNDAMENTAL solutions – Peter Jun 7 '18 at 8:18