11
$\begingroup$

If $d \ne 0$ is a non-square integer, and $(u,v)$ is an integer solution to the Pell equation $$ X^2 - dY^2 = 1, \tag{$\star$} $$ then each solution $(x_i,y_i)$ can be recursively calculated using the formulas \begin{align} x_{n+1} &= ux_n + dvy_n, \\ y_{n+1} &= vx_n + uy_n\tag1 \end{align} n.b. If $(u,v)$ is not the fundamental solution to ($\star$), the recursion still works, though you will instead get $(x_{n+m},y_{n+m})$ for some integer $m$ determined by which solution $(u,v)$ actually is. Thus you can always determine a larger solution to ($\star$), though not necessarily the next largest solution, using only a single solution $(x_n,y_n)$ and the recursion \begin{align} x_{n+1} &= x_n^2 + dy_n^2, \\ y_{n+1} &= 2x_ny_n\tag2 \end{align}

QUESTION: Considering the equation $$ X^2 - dY^2 = k, \qquad k \ne 1, $$ is there a similar simple recursion to determine $(x_{n+1},y_{n+1})$ knowing only $(x_n,y_n)$ [and possibly, though not necessarily, one other solution $(u,v)$]?

With $d=6$ and $k=3$, I tried applying the recursion for $X^2-6Y^2=1$ to the fundamental solution $(3,1)$ of the equation $X^2-6Y^2=3$, and ended up with a solution to the equation $X^2-6Y^2=9$. Since $9=3^2=k^2$, I feel like there might be just a small adjustment to be made to the recursion, to compensate for $k \ne 1$, but I haven't found it.

$\endgroup$
4
  • 3
    $\begingroup$ Take $(x_n,y_n)$ a solution of $X^2-dY^2=k$ but $(u,v)$ a solution of $X^2-dY^2=1$. Then try the recursion again. $\endgroup$ – WimC Mar 29 '16 at 20:23
  • 2
    $\begingroup$ You can always get a larger solution (not necessarily the next larger solution) by using the exact same recursion. The point is that the recursion is equivalent to the formula $x_{n+1}+y_{n+1}\sqrt d = (x_n + y_n\sqrt d)(u+v\sqrt d)$, together with the fact that the norm map $a+b\sqrt d \mapsto a^2-bd^2$ respects multiplication. So given a solution $x_1,y_1$ to $X^2-dY^2=k$ and a solution $(u,v)$ to $X^2-dY^2=1$, you can find lots of solutions to the $k$-equation by "multiplying" by $(u,v)$ repeatedly (using the recursion). $\endgroup$ – Greg Martin Mar 29 '16 at 20:23
  • $\begingroup$ @GregMartin from Siegel's methods for counting solutions to quadratic form equal to a constant (or any represented quadratic form), we know that all solutions split into a finite number of orbits under the action of the automorphism group of the quadratic form. I have tried to popularize the Conway method for indefinite binary forms on this site, not really successful; it shows well how to find representatives for the orbits. $\endgroup$ – Will Jagy Mar 29 '16 at 22:44
  • $\begingroup$ The recursion $(1)$ applies to all $k$. However, the recursion $(2)$ is a square, only for $k=1$, and is the reason why you got $k^2=9$. $\endgroup$ – Tito Piezas III Mar 29 '16 at 23:41
6
$\begingroup$

Yes. The recursion is just the Brahmagupta-Fibonacci Identity in disguise,

$$(u x + d v y)^2 - d(v x + u y)^2 = (u^2 - d v^2) (x^2 - d y^2) = k$$

The coefficients $u,v$ are determined by the fundamental solution to $u^2 - d v^2=1$. And you simply plug in initial $x_1,y_1$ to $x^2 - d y^2 = k$, whether $k=1$ or not, to get subsequent ones. For ex, the universal recursion for $d = 6$,

$$x^2-6y^2 = k$$

is given by,

$$x_{n+1} = \color{blue}5\,x_n + 12y_n$$

$$y_{n+1} = \color{blue}2\,x_n + 5y_n$$

which uses uses $\color{blue}5^2-6\times\color{blue}2^2=1$. To apply for $k=3$, using $3^2-6\times1^2=3$, hence initial $x_1,y_1 = 3,1$, we get,

$$x_2, y_2 = 27,11$$

so $27^2-6\times11^2=3$, and so on.

$\endgroup$
1
  • $\begingroup$ Could you offer a little more explanation here? Can you show more steps in how you got the recursive equations in your example? I don't understand how the Identify given is used $\endgroup$ – Peter Mitrano Dec 31 '18 at 20:34
5
$\begingroup$

Make this an answer. It turns out that, using the recursion you describe, the set of all solutions to $x^2 - dy^2 = k$ split into a small number of orbits. The cleanest way to locate the "seed" values for the different orbits is Conway's topograph method. In essence, $k=\pm 1$ give the smallest number of orbits, namely one. Not much worse for $k $ prime. The number of orbits increases with the number of prime factors of $k,$ as long as the primes $p$ satisfy $(d|p)= 1.$ There is no truly easy way to find all the necessary seed values when $k$ is such a composite number.

Example: $11$ and $19$ are primes represented by $x^2 - 5 y^2,$ and $11 \cdot 19 = 209.$ The solutions to $x^2 - 5 y^2 = 209$ need more than one orbit under your recursion. We can make it worse by throwing in $29,$ and solving $x^2 - 5 y^2 = 6061.$ The only reason it is not bad is that we have class number one.

Here are the 8 seed pairs I get for $x^2 - 5 y^2 = 6061.$ If you apply the mapping $$ (x,y) \mapsto (9x + 20y, 4x + 9y) $$ you get a pair with larger entries than any of these 8. A proof that these eight really are enough takes more work, although I have done plenty of these and think the list is complete.

x:  79  y:  6
x:  81  y:  10
x:  129  y:  46
x:  159  y:  62
x:  191  y:  78
x:  241  y:  102
x:  529  y:  234
x:  591  y:  262

Why not? Here is a longer list, including pairs from the same orbits:

x:  79  y:  6
x:  81  y:  10
x:  129  y:  46
x:  159  y:  62
x:  191  y:  78
x:  241  y:  102
x:  529  y:  234
x:  591  y:  262
x:  831  y:  370
x:  929  y:  414
x:  2081  y:  930
x:  2671  y:  1194
x:  3279  y:  1466
x:  4209  y:  1882
x:  9441  y:  4222
x:  10559  y:  4722
x:  14879  y:  6654
x:  16641  y:  7442
x:  37329  y:  16694
x:  47919  y:  21430
x:  58831  y:  26310
x:  75521  y:  33774
x:  169409  y:  75762
x:  189471  y:  84734
x:  266991  y:  119402
x:  298609  y:  133542
x:  669841  y:  299562
x:  859871  y:  384546
x:  1055679  y:  472114
x:  1355169  y:  606050
x:  3039921  y:  1359494
x:  3399919  y:  1520490
x:  4790959  y:  2142582
x:  5358321  y:  2396314
x:  12019809  y:  5375422
x:  15429759  y:  6900398
x:  18943391  y:  8471742
x:  24317521  y:  10875126

EDIT: it is possible to make a definition of "fundamental solution" that fits well into the group action on the form. As $x,y$ get large, we know that $y/x \approx 1/\sqrt 5 \approx 0.447213596.$ For large $x,y,$ we also know we can back up the solution by the inverse mapping, $$ (x,y) \mapsto (9x-20y, -4x+9y) $$ and get another solution with positive $x,y.$ So, in a nod to Hurwitz, why not call a solution fundamental if either $9x-20y < 0$ or $-4x+9y < 0?$ That way, a solution is fundamental if either $y/x < 0.45$ or $y/x > 0.4444444.$ Below I list the first few solutions with the ratio $y/x$ in decimal. If that decimal is close to $0.44721$ then the solution is not fundamental. This can be upgraded to an "effective" set of bounds on $x,y$ to show that the set of fundamental solutions is finite. Good.

x:  79  y:  6 ratio: 0.0759494  fundamental 
x:  81  y:  10 ratio: 0.123457  fundamental 
x:  129  y:  46 ratio: 0.356589  fundamental 
x:  159  y:  62 ratio: 0.389937  fundamental 
x:  191  y:  78 ratio: 0.408377  fundamental 
x:  241  y:  102 ratio: 0.423237  fundamental 
x:  529  y:  234 ratio: 0.442344  fundamental 
x:  591  y:  262 ratio: 0.443316  fundamental 
x:  831  y:  370 ratio: 0.445247
x:  929  y:  414 ratio: 0.44564
x:  2081  y:  930 ratio: 0.446901
x:  2671  y:  1194 ratio: 0.447024
x:  3279  y:  1466 ratio: 0.447088
x:  4209  y:  1882 ratio: 0.447137
x:  9441  y:  4222 ratio: 0.447198
x:  10559  y:  4722 ratio: 0.447201
x:  14879  y:  6654 ratio: 0.447207
x:  16641  y:  7442 ratio: 0.447209
x:  37329  y:  16694 ratio: 0.447213
x:  47919  y:  21430 ratio: 0.447213
x:  58831  y:  26310 ratio: 0.447213
x:  75521  y:  33774 ratio: 0.447213
x:  169409  y:  75762 ratio: 0.447214
x:  189471  y:  84734 ratio: 0.447214

I did the same run for $x^2 - 5 y^2 = -6061.$ Here the ratio $y/x$ decreases until it gets lower than $0.45$

x:  8  y:  35 ratio: 4.375  fundamental 
x:  28  y:  37 ratio: 1.32143  fundamental 
x:  112  y:  61 ratio: 0.544643  fundamental 
x:  128  y:  67 ratio: 0.523438  fundamental 
x:  188  y:  91 ratio: 0.484043  fundamental 
x:  212  y:  101 ratio: 0.476415  fundamental 
x:  488  y:  221 ratio: 0.452869  fundamental 
x:  628  y:  283 ratio: 0.450637  fundamental 
x:  772  y:  347 ratio: 0.449482
x:  992  y:  445 ratio: 0.448589
x:  2228  y:  997 ratio: 0.447487
x:  2492  y:  1115 ratio: 0.447432
x:  3512  y:  1571 ratio: 0.447323
x:  3928  y:  1757 ratio: 0.447301
x:  8812  y:  3941 ratio: 0.447231
x:  11312  y:  5059 ratio: 0.447224
x:  13888  y:  6211 ratio: 0.447221
x:  17828  y:  7973 ratio: 0.447218
x:  39992  y:  17885 ratio: 0.447214
x:  44728  y:  20003 ratio: 0.447214
x:  63028  y:  28187 ratio: 0.447214
x:  70492  y:  31525 ratio: 0.447214
x:  158128  y:  70717 ratio: 0.447214
x:  202988  y:  90779 ratio: 0.447214
$\endgroup$
12
  • $\begingroup$ As we know, $x^2-dy^2=k$ may have more than one fundamental solution for $k>1$. For $x^2 - 5y^2=6061$, then we have four as, $x,y$, $$79,\; 6\\81,\;10\\129,\;46\\159,\;62$$ Using the negative case of the mapping, $$ (x,y) \mapsto (9x + 20y, 4x \color{red}\pm 9y) $$ yields the other four in your list. $\endgroup$ – Tito Piezas III Mar 30 '16 at 0:14
  • $\begingroup$ @TitoPiezasIII sure, there is the improper automorphism $(x,y) \mapsto (x,-y).$ What is your definition of fundamental solution? After answering, I thought (from a Hurwitz idea) that a solution with $x,y > 0$ but either $9x - 20y < 0$ or $-4x + 9y < 0$ could be a definition, as then the inverse mapping $(x,y) \mapsto (9x-20y, -4x+9y)$ takes it to a negative one. $\endgroup$ – Will Jagy Mar 30 '16 at 0:47
  • 1
    $\begingroup$ Let us define $M = x+\sqrt{d}\,y$. Perhaps the $x,y$ with the smallest $M$ in an orbit would be the fundamental one in that particular orbit. $\endgroup$ – Tito Piezas III Mar 30 '16 at 1:09
  • 1
    $\begingroup$ @TitoPiezasIII your idea for naming "fundamental" solutions for Pell type equations has turned out very well. I'm calling them seeds, no matter. Fairly good and error free presentation at math.stackexchange.com/questions/1737385/… Much, much quicker to work with than Conway's method, which nobody else liked anyway. Admitted, more work is needed for less symmetric $a x^2 + b xy + c y^2 = t$ with $b^2 - 4ac> 0$ but not a square. $\endgroup$ – Will Jagy Apr 12 '16 at 19:22
  • 1
    $\begingroup$ @WillJagy: Ok, thanks for the link. $\endgroup$ – Tito Piezas III Apr 13 '16 at 0:02
2
$\begingroup$

I thought the idea for naming some "fundamental" solutions, from yesterday, was pretty good. I wrote a program to do that. I wanted to show what can happen if the target number is not squarefree. In the following output, $x^2 - 5 y^2 = 121,$ one out of three $(x,y)$ is just $11$ times a pair that solves $x^2 - 5 y^2 = 1.$

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental

 x^2 - 5 y^2 = 121

x:  11  y:  0 ratio: 0  fundamental 
x:  21  y:  8 ratio: 0.380952  fundamental 
x:  29  y:  12 ratio: 0.413793  fundamental 
x:  99  y:  44 ratio: 0.444444
x:  349  y:  156 ratio: 0.446991
x:  501  y:  224 ratio: 0.447106
x:  1771  y:  792 ratio: 0.447205
x:  6261  y:  2800 ratio: 0.447213
x:  8989  y:  4020 ratio: 0.447213
x:  31779  y:  14212 ratio: 0.447214
x:  112349  y:  50244 ratio: 0.447214
x:  161301  y:  72136 ratio: 0.447214
x:  570251  y:  255024 ratio: 0.447214
x:  2016021  y:  901592 ratio: 0.447214
x:  2894429  y:  1294428 ratio: 0.447214
x:  10232739  y:  4576220 ratio: 0.447214


 x^2 - 5 y^2 = 121

jagy@phobeusjunior:~$

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

Why not, here is $x^2 - 5 y^2 = -121.$

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental

 x^2 - 5 y^2 = -121

x:  2  y:  5 ratio: 2.5  fundamental 
x:  22  y:  11 ratio: 0.5  fundamental 
x:  82  y:  37 ratio: 0.45122  fundamental 
x:  118  y:  53 ratio: 0.449153
x:  418  y:  187 ratio: 0.447368
x:  1478  y:  661 ratio: 0.447226
x:  2122  y:  949 ratio: 0.44722
x:  7502  y:  3355 ratio: 0.447214
x:  26522  y:  11861 ratio: 0.447214
x:  38078  y:  17029 ratio: 0.447214
x:  134618  y:  60203 ratio: 0.447214
x:  475918  y:  212837 ratio: 0.447214
x:  683282  y:  305573 ratio: 0.447214
x:  2415622  y:  1080299 ratio: 0.447214
x:  8540002  y:  3819205 ratio: 0.447214
x:  12260998  y:  5483285 ratio: 0.447214


 x^2 - 5 y^2 = -121

jagy@phobeusjunior:~$

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

Here is a good pair, $x^2 - 11 y^2 = 14$ and then $x^2 - 11 y^2 = 350 = 14 \cdot 25.$

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental

 x^2 - 11 y^2 = 14

Wed Mar 30 11:32:36 PDT 2016

x:  5  y:  1 ratio: 0.2  fundamental 
x:  17  y:  5 ratio: 0.294118  fundamental 
x:  83  y:  25 ratio: 0.301205
x:  335  y:  101 ratio: 0.301493
x:  1655  y:  499 ratio: 0.301511
x:  6683  y:  2015 ratio: 0.301511
x:  33017  y:  9955 ratio: 0.301511
x:  133325  y:  40199 ratio: 0.301511
x:  658685  y:  198601 ratio: 0.301511
x:  2659817  y:  801965 ratio: 0.301511
x:  13140683  y:  3962065 ratio: 0.301511

Wed Mar 30 11:32:56 PDT 2016

 x^2 - 11 y^2 = 14

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

jagy@phobeusjunior:~$ ./Pell_Target_Fundamental

 x^2 - 11 y^2 = 350

Wed Mar 30 11:29:54 PDT 2016

x:  19  y:  1 ratio: 0.0526316  fundamental 
x:  25  y:  5 ratio: 0.2  fundamental 
x:  41  y:  11 ratio: 0.268293  fundamental 
x:  47  y:  13 ratio: 0.276596  fundamental 
x:  85  y:  25 ratio: 0.294118  fundamental 
x:  157  y:  47 ratio: 0.299363  fundamental 
x:  223  y:  67 ratio: 0.300448
x:  415  y:  125 ratio: 0.301205
x:  773  y:  233 ratio: 0.301423
x:  899  y:  271 ratio: 0.301446
x:  1675  y:  505 ratio: 0.301493
x:  3121  y:  941 ratio: 0.301506
x:  4441  y:  1339 ratio: 0.301509
x:  8275  y:  2495 ratio: 0.301511
x:  15419  y:  4649 ratio: 0.301511
x:  17933  y:  5407 ratio: 0.301511
x:  33415  y:  10075 ratio: 0.301511
x:  62263  y:  18773 ratio: 0.301511
x:  88597  y:  26713 ratio: 0.301511
x:  165085  y:  49775 ratio: 0.301511
x:  307607  y:  92747 ratio: 0.301511
x:  357761  y:  107869 ratio: 0.301511
x:  666625  y:  200995 ratio: 0.301511
x:  1242139  y:  374519 ratio: 0.301511

Wed Mar 30 11:29:55 PDT 2016

 x^2 - 11 y^2 = 350

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

$\endgroup$
0
$\begingroup$

So writes the Pell equation in General form.

$$Ap^2-Bs^2=k$$

If we know any solution of this equation. $( p ; s)$

If we use any solutions of the following equation Pell.

$$x^2-ABy^2=1$$

Then the following solution of the desired equation can be found by the formula.

$$p_2=xp+Bys$$

$$s_2=xs+Ayp$$

$\endgroup$

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.