Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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 ?
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$
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$$
