Pell's Equation

The Pell's equation problem is, given square-free $d>0$, to find all positive integer solutions $(x,y)$ to the equation $x^2-dy^2=1$. Note that if $x+y\sqrt{d}\in\mathbf{Q}(\sqrt{d})$, then

$$\Norm (x+y\sqrt{d}) = (x+y\sqrt{d})(x-y\sqrt{d}) = x^2 -dy^2.$$

The solutions to Pell's equation thus form a finite-index subgroup of the group of units in the ring of integers of $\mathbf{Q}(\sqrt{d})$. Dirichlet's unit theorem implies that for any $d$ the solutions to Pell's equation form an infinite cyclic group, a fact that takes substantial work to prove using only elementary number theory (for example, using continued fractions).

We first solve Pell's equation $x^2 - 5y^2 = 1$ with $d=5$ by finding the units of a field using :

   > R<x> := PolynomialRing(RationalField());
   > K<a> := NumberField(x^2-5);
   > G, phi := UnitGroup(K);
   > G;
   Abelian Group isomorphic to Z/2 + Z
   Defined on 2 generators
   Relations:
       2*G.1 = 0
   > K!phi(G.1);
   -1
   > u := K!phi(G.2); u;
   1/2*(a + 1)
   > u^2;
   1/2*(a + 3)
   > u^3;
   a + 2
   > Norm(u);
   -1
   > Norm(u^3);
   -1
   > Norm(u^6);
   1
   > fund := u^6;
   > fund;
   4*a + 9
   > 9^2 - 5*4^2;
   1
   > fund^2;
   72*a + 161
   > fund^3;
   1292*a + 2889
   > fund^4;
   23184*a + 51841
   > fund^5;
   416020*a + 930249

The MathSciNet review of [Len02] says: ``This wonderful article begins with history and some elementary facts and proceeds to greater and greater depth about the existence of solutions to Pell equations and then later the algorithmic issues of finding those solutions. The cattle problem is discussed, as are modern smooth number methods for solving Pell equations and the algorithmic issues of representing very large solutions in a reasonable way.''

The simplest solutions to Pell's equation can be huge, even when $d$ is quite small. Read Lenstra's paper for some examples from over two thousand years ago.

   K<a> := NumberField(x^2-NextPrime(10^7));
   > G, phi := UnitGroup(K);
   > K!phi(G.2);
       1635802598803463282255922381210946254991426776931429155067472530\
       003400641003657678728904388162492712664239981750303094365756\
       106316392723776016806037958837914778176119741840754457028237\
       899759459100428895693238165048098039*a + 
       517286692885814967470170672368346798303629034373575202975075\
       605058714958080893991274427903448098643836512878351227856269\
       086856679078304979321047765031073345259902622712059164969008\
       6336036036403311756634562204182936222240930