La ecuación de Pell

Abstract

Sea d un número natural que no es un cuadrado. La ecuación x2 − dy2 = 1 recibe el nombre de ecuación de Pell y surge en diferentes problemas de teoría de números. Esta sencilla ecuación tiene una historia larga y asombrosamente rica, que va desde la antigua Grecia hasta nuestros días. Aparece por primera vez oculta en el problema del ganado del Arquímedes (251 a.C.) y ha sido estudiada por matemáticos de todas las épocas, que incluyen a Arquímedes, Diofanto, Brahmagupta, Bhaskara II, Fermat, Brouncker, Euler, Lagrange y Lenstra. Fue Lagrange el que en 1768 puso fin a un larga búsqueda, a afirmaciones injustificadas y métodos de resolución empíricos, al demostrar rigurosamente que la ecuación posee infinitas soluciones enteras, que todas ellas se obtienen a partir de la llamada solución fundamental y que esta última se puede calcular mediante un algoritmo basado en la expansión en fracciones continuas simples del radical √d. En la actualidad esta ecuación sigue siendo objeto de investigación y existe un criptosistema fundamentado en ella. En este trabajo explicamos detalladamente cómo se resuelve la ecuación de Pell a través de la teoría de fracciones continuas. Analizamos en primer lugar la relación entre esta ecuación y el anillo Z[√d ] derivada de la factorización x2−dy2 = (x+y√d)(x−y√d). En este marco demostramos que la ecuación de Pell siempre admite una solución mínima positiva, denominada solución fundamental, y que cualquier otra solución positiva es potencia de ella. Desarrollamos después la parte necesaria de la teoría de fracciones continuas para describir el vínculo entre la solución fundamental y el parámetro d. Mostramos que la solución fundamental viene dada por un convergente de la expansión en fracciones continuas simples de √d y que este convergente queda determinado por la longitud del periodo de la expansión. A lo largo del trabajo presentamos los algoritmos que permiten calcular las soluciones de la ecuación de Pell y los implementamos en el ordenador con el software Mathematica. Finalmente, como aplicación de los resultados y algoritmos expuestos, resolvemos el problema del ganado de Arquímedes, un problema de la antigüedad que tardó más de 2000 años en ser resuelto y cuyas soluciones completas no pudieron ser calculadas hasta la aparición de los primeros ordenadores. Abstract: Let d be a positive integer that is not a square. The equation x2 − dy2 = 1 is called Pell’s equation and it arises in different problems in number theory. This simple equation has a long and amazingly rich history, ranging from ancient Greece to the present day. It appears implicitly in Archimedes’ cattle problem for the first time (251 B.C.) and it has been studied by mathematicians of all times, including Archimedes, Diophantus, Brahmagupta, Bhaskara II, Fermat, Brouncker, Euler, Lagrange and Lenstra. In 1768 Lagrange finally ended a long search when proving rigorously that this equation has infinitely many integer solutions, that all of them are obtained from the so called fundamental solution, and that the latter can be calculated by using an algorithm based on the expression of √d as an infinite simple continued fraction. He proved so several conjectures on this equation formulated through history and found the reason why the different empirical methods known for resolution worked. Pell’s equation is still today under research and there is a cryptosystem based on it. In this work we explain in full detail how to solve Pell’s equation by using the theory of continued fractions. We first discuss the relation between this equation and the ring Z[√d ], arising from the factorization x2 − dy2 = (x + y√d)(x− y√d). In this framework we prove that Pell’s equation always admit a minimal positive integer solution, called the fundamental solution, and that any other positive solution is obtained by taking powers of it. Then we develop the necessary part of the theory of continued fractions to describe the link between the fundamental solution and the parameter d. We prove that the fundamental solution is a convergent of the infinite simple continued fraction expansion of √d and show that this convergent is determined by the length of the period of such an expansion. Throughout this work we present the algorithms that allow us to calculate the solutions of Pell’s equation and we implement them as computer programs using the software Mathematica. Finally, as an application of the results and algorithms expounded here, we solve Archimedes’ cattle problem, an ancient problem that took more than 2000 years to be solved and whose complete solutions could not be calculated in full until the first computers appeared.