¿El % de la ecuación de Pell-como $X^2-dY^2=k$tiene una recursión simple como $X^2-dY^2=1$?

Question

Si $d \ne 0$ es un no-cuadrado entero, y $(u,v)$ es un número entero solución a la ecuación de Pell $$X^2 - y^2 = 1, \etiqueta{$\star$}$$ a continuación, cada solución de $(x_i,y_i)$ puede ser de forma recursiva calcula utilizando las fórmulas $$\begin{align} x_{n+1} &= ux_n + dvy_n, \\ y_{n+1} &= vx_n + uy_n\tag1 \end{align}$$ n.b. Si $(u,v)$ no es la solución fundamental a ($\star$), la recursividad todavía funciona, aunque usted en lugar de obtener $(x_{n+m},y_{n+m})$ para algunos entero $m$ determinada por la solución de $(u,v)$ es en realidad. Por lo tanto siempre se puede determinar una solución de mayor tamaño ($\star$), aunque no necesariamente a la siguiente más grande de la solución, mediante una única solución de $(x_n,y_n)$ y la recursividad $$\begin{align} x_{n+1} &= x_n^2 + dy_n^2, \\ y_{n+1} &= 2x_ny_n\tag2 \end{align}$$

PREGUNTA: teniendo en cuenta la ecuación $$X^2 - y^2 = k, \qquad k \ne 1,$$ hay una simple similar recursividad para determinar el $(x_{n+1},y_{n+1})$ a sabiendas de que sólo $(x_n,y_n)$ [y posiblemente, aunque no necesariamente, una otra solución $(u,v)$]?

Con $d=6$$k=3$, traté de aplicar la recursividad para $X^2-6Y^2=1$ fundamentales para la solución de $(3,1)$ de la ecuación de $X^2-6Y^2=3$, y terminó con una solución a la ecuación de $X^2-6Y^2=9$. Desde $9=3^2=k^2$, me siento como que podría ser sólo un pequeño ajuste que se hizo a la recursividad, para compensar $k \ne 1$, pero no he encontrado.

Answer 1

Hacen de este una respuesta. Resulta que, el uso de la recursividad que usted describe, el conjunto de todas las soluciones a $x^2 - dy^2 = k$ dividido en un pequeño número de órbitas. La forma más limpia para localizar la "semilla" valores para los diferentes órbitas se Conway topograph método. En esencia, $k=\pm 1$ dar el menor número de órbitas, es decir, uno. No mucho peor para $k$ prime. El número de órbitas aumenta con el número de factores primos de a $k,$ mientras la de los números primos $p$ satisfacer $(d|p)= 1.$ no Hay forma muy fácil de encontrar todos los valores de las semillas al $k$ es un número compuesto.

Ejemplo: $11$ $19$ son primos representado por $x^2 - 5 y^2,$ $11 \cdot 19 = 209.$ Las soluciones a $x^2 - 5 y^2 = 209$ necesita más de una órbita en virtud de su recursividad. Podemos hacer que sea peor lanzando en $29,$ y la solución de $x^2 - 5 y^2 = 6061.$ La única razón por la que no es malo, es que tenemos la clase número uno.

Aquí están las 8 de la semilla de pares que me pasa por $x^2 - 5 y^2 = 6061.$ Si se aplica la asignación de $$(x,y) \mapsto (9x + 20y, 4x + 9y)$$ usted obtiene un par con las entradas más grandes que cualquiera de estos 8. Una prueba de que estos ocho son realmente lo suficientemente lleva más trabajo, aunque no he hecho un montón de ellos y creo que la lista es completa.

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

¿Por qué no? Aquí está una lista más larga, incluyendo parejas del mismo órbitas:

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

EDITAR: es posible hacer una definición de "solución fundamental" que encaja muy bien en la acción del grupo sobre el formulario. Como $x,y$ obtener grandes, sabemos que $y/x \approx 1/\sqrt 5 \approx 0.447213596.$ grandes $x,y,$ también sabemos que podemos hacer una copia de seguridad de la solución por el inverso de la asignación, $$(x,y) \mapsto (9x-20y, -4x+9y)$$ y obtener otra solución positiva $x,y.$, por Lo que, en un guiño a Hurwitz, ¿por qué no llamar a una solución fundamental si $9x-20y < 0$ o $-4x+9y < 0?$ de Que manera, una solución es fundamental si $y/x < 0.45$ o $y/x > 0.4444444.$ a Continuación la lista de las primeras soluciones con la relación de $y/x$ en decimal. Si el decimal es de cerca de $0.44721$, entonces la solución no es fundamental. Esto puede ser actualizado a un "eficaz" conjunto de límites en $x,y$ a mostrar que el conjunto de soluciones es finito. Bueno.

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

Hice el mismo recorrido para $x^2 - 5 y^2 = -6061.$ Aquí la relación de $y/x$ disminuye hasta que se obtiene el menor $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

Answer 2

Sí. La recursividad es sólo el Brahmagupta-Fibonacci de Identidad en el disfraz,

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

Los coeficientes $u,v$ está determinado por la solución fundamental a $u^2 - d v^2=1$. Y basta con conectar inicial $x_1,y_1$$x^2 - d y^2 = k$, si $k=1$ o no, para obtener posteriores. Por ejemplo, el universal recursividad para $d = 6$,

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

está dada por,

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

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

que utiliza los usos $\color{blue}5^2-6\times\color{blue}2^2=1$. Para solicitar la $k=3$ con $3^2-6\times1^2=3$, por lo tanto inicial $x_1,y_1 = 3,1$, obtenemos,

$$x_2, y_2 = 27,11$$

por lo $27^2-6\times11^2=3$, y así sucesivamente.

Answer 3

Pensé que la idea para nombrar algunos de los "fundamentales" de las soluciones, a partir de ayer, fue bastante buena. Yo escribí un programa para hacer eso. Yo quería mostrar lo que puede suceder si el número de destino no es squarefree. En la siguiente salida, $x^2 - 5 y^2 = 121,$ uno de cada tres $(x,y)$ es sólo $11$ veces a la par que resuelve $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:~$

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

Por qué no, aquí es $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:~$

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

Aquí es un buen par de, $x^2 - 11 y^2 = 14$ y, a continuación, $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

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

Answer 4

Así escribe la ecuación de Pell en forma General.

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

Si sabemos que cualquier solución de esta ecuación. $( p ; s)$

Si usamos cualquier solución de la siguiente ecuación de Pell.

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

Entonces se puede encontrar la siguiente solución de la ecuación deseada mediante la fórmula.

$$p_2=xp+Bys$$

$$s_2=xs+Ayp$$