Cómo resolver la siguiente ecuación de Pell?
$$x^{2} - 991y^{2} = 1 $$ donde $(x, y)$ son productos naturales.
La respuesta es $$x = 379,516,400,906,811,930,638,014,896,080$$ $$y = 12,055,735,790,331,359,447,442,538,767$$
Yo no puedo pensar en ninguna manera, aparte de la fuerza bruta. Por favor, ayudar.
También, ¿cuál es la forma general de la solución de cualquier ecuación de Pell?
He leído el artículo de wiki en él, pero no podía conseguir cualquier método general para resolver.
Si $x^2-991y^2=1$, entonces tenemos que $$ \begin{align} \left(\frac{1}{y}\right)^2 &=\left(\frac{x}{y}\right)^2-991\\ &=\left(\frac{x}{y}-\sqrt{991}\right)\left(\frac{x}{y}+\sqrt{991}\right)\tag{1} \end{align} $$ Desde $\frac{x}{y}\stackrel{.}{=}\sqrt{991}\stackrel{.}{=}31.5$, obtenemos que $$ \left|\frac{x}{y}-\sqrt{991}\right|\stackrel{.}{=}\frac1{63}\frac1{y^2}\etiqueta{2} $$ Como se describe en la Sección $5$ de este papel, para obtener una aproximación racional tan cerca como $(2)$, $\dfrac{x}{y}$ debe ser convergente de la continuación de la fracción de $\sqrt{991}$. Desde el próximo continuant, c_n, satisface $$ \frac1{c_n+2}\frac1{y^2}\lt\left|\frac{x}{y}-\sqrt{991}\right|\le\frac1{c_n}\frac1{y^2}\etiqueta{3} $$ el próximo continuant debe ser dentro de unos $1$$62$.
La continuación de la fracción por un número algebraico de grado $2$ eventualmente se repita. La continuación de la fracción de $\sqrt{991}$ es $$ (31, [2, 12, 10, 2, 2, 2, 1, 1, 2, 6, 1, 1, 1, 1, 3, 1, 8, 4, 1, 2, 1, 2, 3, 1, 4, 1, 20, 6, 4, 31, 4, 6, 20, 1, 4, 1, 3, 2, 1, 2, 1, 4, 8, 1, 3, 1, 1, 1, 1, 6, 2, 1, 1, 2, 2, 2, 10, 12, 2, 62]) $$ donde la secuencia entre paréntesis se repite.
La única continuant dentro de$1$$62$$62$. Por lo tanto, la primera solución positiva corresponde a la aproximación racional a $\sqrt{991}$ con la continuación de la fracción $$ (31, 2, 12, 10, 2, 2, 2, 1, 1, 2, 6, 1, 1, 1, 1, 3, 1, 8, 4, 1, 2, 1, 2, 3, 1, 4, 1, 20, 6, 4, 31, 4, 6, 20, 1, 4, 1, 3, 2, 1, 2, 1, 4, 8, 1, 3, 1, 1, 1, 1, 6, 2, 1, 1, 2, 2, 2, 10, 12, 2) $$ que es $$ \color{#C00000}{\frac{x_1}{y_1}}=\color{#C00000}{\frac{379516400906811930638014896080}{12055735790331359447442538767}}\tag{4} $$ La siguiente solución viene de la próxima vez que el próximo continuant es $62$; es decir, para la aproximación racional a $\sqrt{991}$ con la continuación de la fracción $$ (31, 2, 12, 10, 2, 2, 2, 1, 1, 2, 6, 1, 1, 1, 1, 3, 1, 8, 4, 1, 2, 1, 2, 3, 1, 4, 1, 20, 6, 4, 31, 4, 6, 20, 1, 4, 1, 3, 2, 1, 2, 1, 4, 8, 1, 3, 1, 1, 1, 1, 6, 2, 1, 1, 2, 2, 2, 10, 12, 2, 62, 2, 12, 10, 2, 2, 2, 1, 1, 2, 6, 1, 1, 1, 1, 3, 1, 8, 4, 1, 2, 1, 2, 3, 1, 4, 1, 20, 6, 4, 31, 4, 6, 20, 1, 4, 1, 3, 2, 1, 2, 1, 4, 8, 1, 3, 1, 1, 1, 1, 6, 2, 1, 1, 2, 2, 2, 10, 12, 2) $$ que es $$ \color{#C00000}{\frac{x_2}{y_2}}=\color{#C00000}{\frac{288065397114519999215772221121510725946342952839946398732799}{9150698914859994783783151874415159820056535806397752666720}}\tag{5} $$ Podemos obtener todas las soluciones, comenzando con $(x_0,y_0)=(1,0)$$(4)$, el uso de $$ \begin{align} x_n&=759032801813623861276029792160\,x_{n-1}-x_{n-2}\\ y_n&=759032801813623861276029792160\,y_{n-1}-y_{n-2} \end{align}\etiqueta{6} $$
Editar, 6 de abril de 2014: os pongo algunas de las GMP oversize enteros en dos de mis indefinido formularios de programas en C++, así que aquí está el Lagrange ciclo método para hacerlo. La importancia de esto es que no decimales de precisión es necesaria en absoluto, y no de reconocimiento de patrones (ciclo de detección??), no hay memoria es necesaria en absoluto.
Pell 991
0 form 1 62 -30 delta -2
1 form -30 58 5 delta 12
2 form 5 62 -6 delta -10
3 form -6 58 25 delta 2
4 form 25 42 -22 delta -2
5 form -22 46 21 delta 2
6 form 21 38 -30 delta -1
7 form -30 22 29 delta 1
8 form 29 36 -23 delta -2
9 form -23 56 9 delta 6
10 form 9 52 -35 delta -1
11 form -35 18 26 delta 1
12 form 26 34 -27 delta -1
13 form -27 20 33 delta 1
14 form 33 46 -14 delta -3
15 form -14 38 45 delta 1
16 form 45 52 -7 delta -8
17 form -7 60 13 delta 4
18 form 13 44 -39 delta -1
19 form -39 34 18 delta 2
20 form 18 38 -35 delta -1
21 form -35 32 21 delta 2
22 form 21 52 -15 delta -3
23 form -15 38 42 delta 1
24 form 42 46 -11 delta -4
25 form -11 42 50 delta 1
26 form 50 58 -3 delta -20
27 form -3 62 10 delta 6
28 form 10 58 -15 delta -4
29 form -15 62 2 delta 31
30 form 2 62 -15 delta -4
31 form -15 58 10 delta 6
32 form 10 62 -3 delta -20
33 form -3 58 50 delta 1
34 form 50 42 -11 delta -4
35 form -11 46 42 delta 1
36 form 42 38 -15 delta -3
37 form -15 52 21 delta 2
38 form 21 32 -35 delta -1
39 form -35 38 18 delta 2
40 form 18 34 -39 delta -1
41 form -39 44 13 delta 4
42 form 13 60 -7 delta -8
43 form -7 52 45 delta 1
44 form 45 38 -14 delta -3
45 form -14 46 33 delta 1
46 form 33 20 -27 delta -1
47 form -27 34 26 delta 1
48 form 26 18 -35 delta -1
49 form -35 52 9 delta 6
50 form 9 56 -23 delta -2
51 form -23 36 29 delta 1
52 form 29 22 -30 delta -1
53 form -30 38 21 delta 2
54 form 21 46 -22 delta -2
55 form -22 42 25 delta 2
56 form 25 58 -6 delta -10
57 form -6 62 5 delta 12
58 form 5 58 -30 delta -2
59 form -30 62 1 delta 62
60 form 1 62 -30
disc 3964
Automorph, written on right of Gram matrix:
5788591406539787767296194303 361672073709940783423276163010
12055735790331359447442538767 753244210407084073508733597857
Pell automorph
379516400906811930638014896080 11947234168218377212415555918097
12055735790331359447442538767 379516400906811930638014896080
Pell unit
379516400906811930638014896080^2 - 991 * 12055735790331359447442538767^2 = 1
=========================================
991 991
Quiero dar una descripción completa en Cómo detectar cuando fracciones continuas período termina y en el MO pregunta que me enlace a allí. Usted necesita estar muy seguro sobre el uso de dos por dos matrices. Sin embargo, y este es el punto clave, NO es NECESARIO el uso de alta precisión decimal. Todo es aritmética de enteros. La única aproximación es la parte entera de la raíz cuadrada del discriminante, como en $\left\lfloor \sqrt {3964} \right\rfloor = 62.$ La mala noticia es que mi programa se limita al número de s debajo de $2^{31},$, por lo que la "respuesta" al final era una tontería y me acaba de borrar. Oh, esto viene a veces...con este método, además, no es necesario el uso de cualquier ciclo de la detección. El ciclo de $991$ comienza con la forma binaria $\langle 1,62,-30 \rangle$ y termina precisamente cuando nosotros, una vez más, llegar a $\langle 1,62,-30 \rangle.$ No antes, no después. Tengo un corto ejemplo, las tripletas puede repetir la primera entrada, en este caso 9, pero que se hace cuando las tres entradas del partido:
0 form 9 75 -16 delta -4
1 form -16 53 53 delta 1
2 form 53 53 -16 delta -4
3 form -16 75 9 delta 8
4 form 9 69 -40 delta -1
5 form -40 11 38 delta 1
6 form 38 65 -13 delta -5
7 form -13 65 38 delta 1
8 form 38 11 -40 delta -1
9 form -40 69 9 delta 8
10 form 9 75 -16
Permítanme comenzar con una vida más fácil, 91, donde hago de obtener una respuesta, a continuación, mostrar 991 después de:
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./Pell
Input n for Pell
91
0 form 1 18 -10 delta -1
1 form -10 2 9 delta 1
2 form 9 16 -3 delta -5
3 form -3 14 14 delta 1
4 form 14 14 -3 delta -5
5 form -3 16 9 delta 1
6 form 9 2 -10 delta -1
7 form -10 18 1 delta 18
8 form 1 18 -10
disc 364
Automorph, written on right of Gram matrix:
89 1650
165 3059
Pell automorph
1574 15015
165 1574
Pell unit
1574^2 - 91 * 165^2 = 1
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$ ./indefCycle
Input three coefficients a b c for indef f(x,y)= a x^2 + b x y + c y^2
1 0 -991
0 form 1 0 -991 delta 0
1 form -991 0 1 delta 31
2 form 1 62 -30
-1 -31
0 -1
To Return
-1 31
0 -1
0 form 1 62 -30 delta -2
1 form -30 58 5 delta 12
2 form 5 62 -6 delta -10
3 form -6 58 25 delta 2
4 form 25 42 -22 delta -2
5 form -22 46 21 delta 2
6 form 21 38 -30 delta -1
7 form -30 22 29 delta 1
8 form 29 36 -23 delta -2
9 form -23 56 9 delta 6
10 form 9 52 -35 delta -1
11 form -35 18 26 delta 1
12 form 26 34 -27 delta -1
13 form -27 20 33 delta 1
14 form 33 46 -14 delta -3
15 form -14 38 45 delta 1
16 form 45 52 -7 delta -8
17 form -7 60 13 delta 4
18 form 13 44 -39 delta -1
19 form -39 34 18 delta 2
20 form 18 38 -35 delta -1
21 form -35 32 21 delta 2
22 form 21 52 -15 delta -3
23 form -15 38 42 delta 1
24 form 42 46 -11 delta -4
25 form -11 42 50 delta 1
26 form 50 58 -3 delta -20
27 form -3 62 10 delta 6
28 form 10 58 -15 delta -4
29 form -15 62 2 delta 31
30 form 2 62 -15 delta -4
31 form -15 58 10 delta 6
32 form 10 62 -3 delta -20
33 form -3 58 50 delta 1
34 form 50 42 -11 delta -4
35 form -11 46 42 delta 1
36 form 42 38 -15 delta -3
37 form -15 52 21 delta 2
38 form 21 32 -35 delta -1
39 form -35 38 18 delta 2
40 form 18 34 -39 delta -1
41 form -39 44 13 delta 4
42 form 13 60 -7 delta -8
43 form -7 52 45 delta 1
44 form 45 38 -14 delta -3
45 form -14 46 33 delta 1
46 form 33 20 -27 delta -1
47 form -27 34 26 delta 1
48 form 26 18 -35 delta -1
49 form -35 52 9 delta 6
50 form 9 56 -23 delta -2
51 form -23 36 29 delta 1
52 form 29 22 -30 delta -1
53 form -30 38 21 delta 2
54 form 21 46 -22 delta -2
55 form -22 42 25 delta 2
56 form 25 58 -6 delta -10
57 form -6 62 5 delta 12
58 form 5 58 -30 delta -2
59 form -30 62 1 delta 62
60 form 1 62 -30
=========================================
jagy@phobeusjunior:~/old drive/home/jagy/Cplusplus$
Siguiendo el enlace, toma (379,12, que fue calculado por fuerza bruta) como la solución fundamental, podemos obtener la solución general.
Estoy tratando de reemplazar la fuerza bruta con la inteligencia humana(!) utilizando las siguientes: primera , segunda y continuado fracción de $\sqrt{991}$
Aquí están los pasos para encontrar las soluciones para todos los d = m^2 + 2k. En su pregunta d = 991, que pertenece a esta categoría. Los cinco pasos siguientes a dar la primera solución y las soluciones fundamentales.
1) 991 = m^2 + 2k
991 - 31^2 = 2k
De manera que m=31, k=15.
2) ponemos x = m^2 - m + k = 945
y = m - 1 = 30
945^2 - 991*30^2 = 1125 -> 189 - 991*6^2 = 45 -> 63^2 - 991*2^2 = 5
3) Ahora vamos a encontrar el disolvente de la siguiente manera:
x_1 = m^2 + m + 2k = 1022
y_1 = m + 1 = 32
1022^2 - 991*32^2 = 29700 -> 511^2 - 991*16^2 = 7425
x_2 = m^2 - m + 2k = 960
y_2 = m - 1 = 30
960^2 - 991*30^2 = 29700 -> 480^2 - 991*15^2 =7425
A partir de la siguiente multiplicación queremos encontrar el valor del disolvente:
(511 + 16*sqrt991)(480 + 15*sqrt991) -> 483120^2 - 991*15345^2 = 7425^2
4) multiplicamos el disolvente por cualquiera de las soluciones fundamentales para encontrar la segunda solución fundamental:
(483120 + 15345*sqrt991)(945 + 30*sqrt991) -> 24586^2 - 991*781^2 = 45
5) a partir De la multiplicación (24586 + 781*sqrt991)(945 + 30*sqrt991) obtenemos la tercera solución fundamental.
Podemos continuar este proceso indefinidamente a encontrar más y más fundamental de soluciones.
$$x^2 - 991y^2 = 1$$ \begin{align} \left(\frac{1}{y}\right)^2 &=\left(\frac{x}{y}\right)^2-991\\ &=\left(\frac{x}{y}-\sqrt{991}\right)\left(\frac{x}{y}+\sqrt{991}\right)\tag{1} \end--(1)
Asumiendo $y \not= 0$ dividir ambos lados de la ecuación por $y^2$
es decir, $$(x/y)^2 - 991 = (1/y)^2$$
es decir, $(x/y)^2 - (1/y)^2 = 991$
es decir, $(x/y - 1/y)(x/y + 1/y) = (1)(991)$
es decir, $(x/y - 1/y)(x/y + 1/y) = (496 - 495)(496 + 495)$
es decir, $x/y = 496$ $1/y = 495$
es decir, $x = (496/495)$ $y = 1/495$
La ecuación representa una hipérbola de la forma $$x^2/a^2 - y^2/b^2 = 1$$
es decir, la ecuación es $$x^2/(1^2) - y^2/(\sqrt {1/991})^2 = 1$$
los focos de esta hipérbola son los co ordenadas $(\pm c, 0)$
Aquí $c = \sqrt{a^2 + b^2}$
Las asíntotas son $y = \pm (b/a)x$
es decir, Las asíntotas son $y = \pm (1/\sqrt{991})x$
Existe una $CONJUGATE$ $HYPERBOLA$ de la forma $\frac{x^2}{a^2} - \frac{y^2}{b^2} = -1$, para el $HYPERBOLA$ $\frac{x^2}{a^2} - \frac{y^2}{b^2} = 1$
Aquí la ecuación de la $conjugate$ $hyperbola$ es $x^2 - 991(y^2) = -1$
$$x^2 - 991y^2 = -1$$ \begin{align} x_n&=759032801813623861276029792160\,x_{n-1}-x_{n-2}\\ y_n&=759032801813623861276029792160\,y_{n-1}-y_{n-2} \end--(2)
Ahora resolver las ecuaciones (1) y (2) por $x$ $y$
es decir, $(2)(x^2) - (2)(991)(y^2) = 0$
es decir, $(x^2) - (991)(y^2) = 0$
es decir, $(x^2) = (991)(y^2)$
es decir, $\frac{x^2}{y^2} = 991$
es decir, $\left(\frac{x^2}{y^2} - (\sqrt{991})^2\right) = 0$
es decir, $\left(\frac{x}{y} - \sqrt{991}\right)\left(\frac{x}{y} + \sqrt{991}\right) = 0$
es decir, $(\frac{x}{y} = \pm\sqrt{991})$
es decir,$\frac{y}{x} = \pm\frac{1}{\sqrt{991}}$ , las ecuaciones de las asíntotas de la hipérbola
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
