Ecuación de Pell

Ecuación de Pell para n = 2 e seis das súas solucións enteiras

Definimos a ecuación de Pell como calquera ecuación diofantiana da forma $x^{2}-ny^{2}=1,$ onde n é un número enteiro non cadrado positivo e procuramos solucións enteiras para x e y. En coordenadas cartesianas, a ecuación represéntase por unha hipérbola, as solucións ocorren sempre que a curva pasa por un punto cuxas coordenadas x e y son ambas as dúas enteiras, como a solución trivial con x = 1 e y = 0. Joseph Louis Lagrange demostrou que, mentres n non sexa un cadrado perfecto, a ecuación de Pell ten infinitas solucións enteiras distintas. Estas solucións pódense usar para aproximar con precisión a raíz cadrada de n por números racionais da forma x/y.

Historia

Esta ecuación estudouse extensamente na India comezando por Brahmagupta, que atopou unha solución enteira para $92x^{2}+1=y^{2}$ no seu traballo Brāhmasphuṭasiddhānta arredor do ano 628. Bhaskara II no século XII e Narayana Pandit no século XIV atoparon solucións xerais á ecuación de Pell e outras ecuacións cadráticas indeterminadas. Bhaskara A II é recoñecido como o autor do método chakravala, baseándose no traballo de Jayadeva e Brahmagupta. Desde a época de Pitágoras en Grecia eran coñecidas as solucións a exemplos específicos da ecuación de Pell, como os números de Pell derivados da ecuación con n = 2. William Brouncker foi o primeiro europeo en resolver a ecuación de Pell. O nome da ecuación de Pell xurdiu cando Leonhard Euler atribuíu erroneamente a solución da ecuación de Brouncker a John Pell.

Solucións

Solución fundamental mediante fraccións continuas

Sexa $p_{i}/q_{i}$ a secuencia de converxentes da fracción continua regular para ${\sqrt {n}}$. Esta secuencia é única. Entón existe un i que dá o valor da solución mínima $(x_{1},y_{1})$ da ecuación de Pell en enteiros $(x_{1}=p_{i},y_{1}=q_{i})$. Este par chámase solución fundamental. A secuencia de enteiros $[a_{0};a_{1},a_{2},\ldots ]$ na fracción continua regular de ${\sqrt {n}}$ é sempre periódica. Pódese escribir na forma $\left[\lfloor {\sqrt {n}}\rfloor ;{\overline {a_{1},a_{2},\ldots ,a_{r-1},2\lfloor {\sqrt {n}}\rfloor }}\right]$, onde $a_{1},a_{2},\ldots ,a_{r-1},2\lfloor {\sqrt {n}}\rfloor$ é a parte periódica que se repite indefinidamente. Así a solución fundamental é

$(x_{1},y_{1})={\begin{cases}(p_{r-1},q_{r-1}),&{\text{ para }}r{\text{ par}}\\(p_{2r-1},p_{2r-1}),&{\text{ para }}r{\text{ impar}}\end{cases}}$

Solucións adicionais a partir da solución fundamental

Unha vez atopada a solución fundamental, todas as solucións restantes pódense calcular a partir da seguinte ecuación

$x_{k}+y_{k}{\sqrt {n}}=(x_{1}+y_{1}{\sqrt {n}})^{k},$

expandindo o lado dereito e igualando os coeficientes de ${\sqrt {n}}$ en ambos os dous lados. Isto produce as relacións de recorrencia

$x_{k+1}=x_{1}x_{k}+ny_{1}y_{k},$

$y_{k+1}=x_{1}y_{k}+y_{1}x_{k}.$

Existe outra recorrencia linear de segunda orde,

$x_{k+2}=2x_{1}x_{k+1}-x_{k},$

$y_{k+2}=2x_{1}y_{k+1}-y_{k}.$

Esta recorrencia permite obter un elemento $(x_{k},y_{k})$ de forma explícita de varios xeitos, por exemplo usando as fórmulas de Binet.

Representación compacta e algoritmos máis rápidos

Aínda que escribir a solución fundamental (x₁, y₁) pode requirir un gran número de díxitos, en moitos casos pode representarse de forma máis compacta na forma

$x_{1}+y_{1}{\sqrt {n}}=\prod _{i=1}^{t}(a_{i}+b_{i}{\sqrt {n}})^{c_{i}}$

usando números enteiros moito máis pequenos a_i, b_i e c_i.

Un exemplo o temos no problema do gando de Arquímedes, que é equivalente á ecuación de Pell $x^{2}-410\,286\,423\,278\,424y^{2}=1$, cuxa solución fundamental ten 206545 díxitos se se escribe explicitamente. Non obstante, a solución tamén é igual a

$x_{1}+y_{1}{\sqrt {n}}=u^{2329},$ onde

$u=x'_{1}+y'_{1}{\sqrt {4\,729\,494}}=(300\,426\,607\,914\,281\,713\,365{\sqrt {609}}+84\,129\,507\,677\,858\,393\,258{\sqrt {7766}})^{2}$

deste xeito $x'_{1}$ e $y'_{1}$ só teñen 45 e 41 díxitos decimais respectivamente fronte aos miles de díxitos da solución non compacta.

Pódense empregar métodos relacionados co método da criba cadrática para a factorización de enteiros e así obter relacións entre números primos na extensión do corpo numérico xerado por √n. Combinando estas relacións atópase unha representación en produto do tipo mencionado anteriormente. O algoritmo resultante é máis eficiente que o método de fracción continua, aínda que segue a ser máis lento que un tempo polinómico. Baixo o suposto da hipótese xeneralizada de Riemann, pódese demostrar que ese tempo é da orde de

$\exp O({\sqrt {\log N\log \log N}}),$

onde N = log n é o tamaño da entrada. Un tempo similar á criba cadrática.

Exemplo

Como exemplo, considere a ecuación de Pell para n = 7, é dicir,

$x^{2}-7y^{2}=1.$

Para ${\sqrt {7}}$ temos a fracción continua $[2;{\overline {1,1,1,4}}]$. Ten un período ten lonxitude $4$, que é un número par, por tanto o converxente que produce a solución fundamental obtense truncando a fracción continua xusto antes do final da primeira aparición do período: $[2,1,1,1]={\frac {8}{3}}$.

Mostramos a secuencia de converxentes para a raíz cadrada de 7

p/q (converxentes)	p2 − 7q2 (Aproximación tipo Pell)
2/1	−3
3/1	+2
5/2	−3
8/3	+1

Se aplicamos a fórmula de recorrencia a esta solución xérase a secuencia infinita de solucións

(1, 0); (8, 3); (127, 48); (2024, 765); (32257, 12192); (514088, 194307); (8193151, 3096720); (130576328, 49353213); ... (secuencia A001081 na OEIS) para x e (secuencia A001080 na OEIS) para y.

Para a ecuación de Pell

$x^{2}-13y^{2}=1.$

a fracción continua ${\sqrt {13}}=[3;{\overline {1,1,1,1,6}}]$ ten un período de duración impar. A solución fundamental aparece logo antes da segunda repetición$[3;1,1,1,1,6,1,1,1,1]={\frac {649}{180}}$. Así, a solución fundamental é $(x_{1},y_{1})=(649,180)$.

A solución máis pequena pode ser moi grande. Por exemplo, a solución máis pequena para $x^{2}-313y^{2}=1$ é (32188120829134849, 1819380158564160), sendo esta a ecuación que Frenicle desafiou a Wallis a resolver.

Lista de solucións fundamentais das ecuacións de Pell

Aquí seguido mostramos unha lista das solucións fundamentais $x^{2}-ny^{2}=1$ con n ≤ 96. Cando n é un cadrado enteiro, non hai solución agás a solución trivial (1, 0). Os valores de x son (secuencia A002350 na OEIS) e os de y son (secuencia A002349 na OEIS).

n	x	y
1	–	–
2	3	2
3	2	1
4	–	–
5	9	4
6	5	2
7	8	3
8	3	1
9	–	–
10	19	6
11	10	3
12	7	2
13	649	180
14	15	4
15	4	1
16	–	–
17	33	8
18	17	4
19	170	39
20	9	2
21	55	12
22	197	42
23	24	5
24	5	1
25	–	–
26	51	10
27	26	5
28	127	24
29	9801	1820
30	11	2
31	1520	273
32	17	3

n	x	y
33	23	4
34	35	6
35	6	1
36	–	–
37	73	12
38	37	6
39	25	4
40	19	3
41	2049	320
42	13	2
43	3482	531
44	199	30
45	161	24
46	24335	3588
47	48	7
48	7	1
49	–	–
50	99	14
51	50	7
52	649	90
53	66249	9100
54	485	66
55	89	12
56	15	2
57	151	20
58	19603	2574
59	530	69
60	31	4
61	1766319049	226153980
62	63	8
63	8	1
64	–	–

n	x	y
65	129	16
66	65	8
67	48842	5967
68	33	4
69	7775	936
70	251	30
71	3480	413
72	17	2
73	2281249	267000
74	3699	430
75	26	3
76	57799	6630
77	351	40
78	53	6
79	80	9
80	9	1
81	–	–
82	163	18
83	82	9
84	55	6
85	285769	30996
86	10405	1122
87	28	3
88	197	21
89	500001	53000
90	19	2
91	1574	165
92	1151	120
93	12151	1260
94	2143295	221064
95	39	4
96	49	5

Conexións

Teoría alxébrica de números

En primeiro lugar a ecuación de Pell está relacionada coa teoría dos números alxébricos, xa que a fórmula

$x^{2}-ny^{2}=(x+y{\sqrt {n}})(x-y{\sqrt {n}})$

é a norma para o anel $\mathbb {Z} [{\sqrt {n}}]$ e para a extensión do corpo cadrático $\mathbb {Q} ({\sqrt {n}})$. Así, un par de números enteiros $(x,y)$ resolve a ecuación de Pell se e só se $x+y{\sqrt {n}}$ é unha unidade con norma 1 en $\mathbb {Z} [{\sqrt {n}}]$ O teorema das unidades de Dirichlet, no que di que todas as unidades de $\mathbb {Z} [{\sqrt {n}}]$ pódense expresar como potencias dunha única unidade fundamental (e multiplicación por un signo), é unha reformulación alxébrica do feito de que todas as solucións da ecuación de Pell poden xerarse a partir da solución fundamental.

Polinomios de Chebyshev

Demeyer mostra unha conexión da ecuación de Pell cos polinomios de Chebyshev: Se $T_{i}(x)$ e $U_{i}(x)$ son os polinomios de Chebyshev do primeiro e do segundo tipo respectivamente, entón estes polinomios satisfan unha forma da ecuación de Pell en calquera anel polinómico $R[x]$ facendo $n=x^{2}-1$ ,

$T_{i}^{2}-(x^{2}-1)U_{i-1}^{2}=1.$

Así, estes polinomios poden ser xerados pola técnica estándar para as ecuacións de Pell, mediante potencias dunha solución fundamental,

$T_{i}+U_{i-1}{\sqrt {x^{2}-1}}=(x+{\sqrt {x^{2}-1}})^{i}.$

Alén diso podemos ver que se $(x_{i},y_{i})$ son as solucións de calquera ecuación de Pell enteira, entón as seguintes solucións son $x_{i}=T_{i}(x_{1})$ e $y_{i}=y_{1}U_{i-1}(x_{1})$.

Fraccións continuas

A relación coas fraccións continuas implica que as solucións da ecuación de Pell forman un subconxunto semigrupo do grupo modular. Así, por exemplo, se p e q satisfan a ecuación de Pell, entón

${\begin{pmatrix}p&q\\nq&p\end{pmatrix}}$

é unha matriz de determinante igual a 1. Os produtos desas matrices toman exactamente a mesma forma e, polo tanto, todos estes produtos dan solucións á ecuación de Pell.

Números suaves

O teorema de Størmer usa as ecuacións de Pell para atopar pares de número suaves consecutivos, que son enteiros positivos cuxos factores primos son todos menores que un valor dado. Como parte desta teoría, Størmer tamén investigou a divisibilidade entre as solucións da ecuación de Pell, en particular, mostrou que cada solución que non sexa a solución fundamental ten un factor primo que non divide n.

Ecuación de Pell negativa

A ecuación de Pell negativa vén dada por

$x^{2}-ny^{2}=-1$.

Pódese resolver polo mesmo método de fraccións continuas e ten solucións se e só se o período da fracción continua ten lonxitude impar. Non obstante, non se sabe a priori que raíces cadradas teñen períodos impares e, polo tanto, non se sabe cando a ecuación de Pell negativa ten solución sen calcular a fracción continua. Unha condición necesaria (mais non suficiente) para ter solución é que n non sexa divisible por 4 ou por un primo da forma 4k + 3. Así, por exemplo, x² − 3ny² = −1 non ten solución, mais x ² − 5ny² = −1 pode tela.

Os primeiros números n para os que x² − ny ² = −1 ten solución son

1, 2, 5, 10, 13, 17, 26, 29, 37, 41, 50, 53, 58, 61, 65, 73, 74, 82, 85, 89, 97, ... (secuencia A031396 na OEIS).

Se a ecuación de Pell negativa ten unha solución para un n particular, a solución fundamental da Pell positiva cálculase elevando ao cadrado a ecuación de Pell:

$(x^{2}-ny^{2})^{2}=(-1)^{2}$ implica

$(x^{2}+ny^{2})^{2}-n(2xy)^{2}=1.$

Posto que $(x+{\sqrt {n}}y)(x-{\sqrt {n}}y)=-1$, as seguintes solucións determínase coa ecuación $i(x_{k}+{\sqrt {n}}y_{k})=(i(x+{\sqrt {n}}y))^{k}$ sempre que $k$ é impar. A relación de recursividade resultante é

$x_{k}=x_{k-2}x_{1}^{2}+nx_{k-2}y_{1}^{2}+2ny_{k-2}y_{1}x_{1},$

$y_{k}=y_{k-2}x_{1}^{2}+ny_{k-2}y_{1}^{2}+2x_{k-2}y_{1}x_{1},$

que dá un conxunto infinito de solucións á ecuación de Pell negativa.

Ecuación de Pell xeneralizada

A ecuación $x^{2}-Dy^{2}=N$ Chámase ecuación de Pell xeneralizada. A ecuación $u^{2}-dv^{2}=N$ é o correspondente resolvente de Pell. Lagrange deu un algoritmo recursivo en 1768 para resolver a ecuación, reducindo o problema ao caso $|N|<{\sqrt {d}}$.

Esas solucións pódense derivar mediante o método das fraccións continuas como se indicaba anteriormente.

Se $(x_{0},y_{0})$ é unha solución de $x^{2}-dy^{2}=N,$ e $(u_{n},v_{n})$ é unha solución de $u^{2}-dv^{2}=1,$ daquela un $(x_{n},y_{n})$ tal que $x_{n}+y_{n}{\sqrt {d}}={\big (}x_{0}+y_{0}{\sqrt {d}}{\big )}{\big (}u_{n}+v_{n}{\sqrt {d}}{\big )}$ é a solución a $x^{2}-dy^{2}=N$, un principio chamado principio multiplicativo. A solución $(x_{n},y_{n})$ chámase múltiplo de Pell da solución $(x_{0},y_{0})$.

Existe un conxunto finito de solucións para $x^{2}-Dy^{2}=N$ tal que cada solución é un múltiplo de Pell dunha solución dese conxunto. En particular, se $(u,v)$ é a solución fundamental de $u^{2}-dv^{2}=1$, daquela cada solución da ecuación é un múltiplo de Pell da solución $(x,y)$ con $|x|\leq {\sqrt {|N|}}\left({\sqrt {|U|}}+1\right)/2$ e $|y|\leq {\sqrt {|N|}}\left({\sqrt {|U|}}+1\right)/{\big (}2{\sqrt {d}}{\big )}$, onde $U=u+v{\sqrt {d}}$.

Se x e y son solucións enteiras positivas da ecuación de Pell con $|N|<{\sqrt {d}}$, entón $x/y$ é un converxente da fracción continua de ${\sqrt {d}}$.

Exemplo

$x^{2}-6y^{2}=3$.

Aplicando aritmética modular, reducindo módulo 3, temos $x^{2}\equiv 0{\pmod {3}}$, e por tanto temos $x=3z$, dando a nova ecuación, $9z^{2}-6y^{2}=3$ equivalente a $-2y^{2}+(3z^{2}-1)=0.$ Se o vemos como un polinomio en y e calculamos o discriminate: $0^{2}-4\cdot (-2)\cdot (3z^{2}-1)=4(6z^{2}-2)$, que para ser solución enteira debe ser un cadrado perfecto, o que implica $6z^{2}-2=t^{2}$.

Posto que 2 < √6 xa podemos resolver a nova ecuación de Pell $t^{2}-6z^{2}=-2$ cos converxentes de √6.

As primeiras solucións para (t,z) son $(2,1),(22,9),(218,89),\ldots$

Como $x=3z,\ y=\pm {\sqrt {4t^{2}}}/(2\cdot (-2))=t/2$ as solucións (x, y) de $x^{2}-6y^{2}=3$ son $(3,1),(27,11),(267,1099),\ldots$

Véxase tamén

Bibliografía

• Edwards, Harold M. (1996) [1977]. Fermat's Last Theorem: A Genetic Introduction to Algebraic Number Theory. Graduate Texts in Mathematics 50. Springer-Verlag. ISBN 0-387-90230-9. MR 0616635. 
• Pinch, R. G. E. (1988). Simultaneous Pellian equations. Math. Proc. Cambridge Philos. Soc. 103. pp. 35–46. Bibcode:1988MPCPS.103...35P. doi:10.1017/S0305004100064598. 
• Whitford, Edward Everett (1912). The Pell equation (PhD Thesis). Columbia University. 
• Williams, H. C. (2002). "Solving the Pell equation". En Bennett, M. A.; Berndt, B. C.; Boston, N.; Diamond, H. G.; Hildebrand, A. J.; Philipp, W. Surveys in number theory: Papers from the millennial conference on number theory. Natick, MA: A K Peters. pp. 325–363. ISBN 1-56881-162-4. Zbl 1043.11027. 

Ligazóns externas

• Weisstein, Eric W. "Pell's equation". MathWorld. 
• O'Connor, John J.; Robertson, Edmund F. "Ecuación de Pell". MacTutor History of Mathematics archive. University of St Andrews. .
• Pell equation solver (n has no upper limit)
• Pell equation solver (n < 10¹⁰, can also return the solution to x² − ny² = ±1, ±2, ±3, and ±4)