Pell's Equation

Some Background

Pell's Equation is a classic problem in number theory. It takes the form: x2 − dy2 = 1, where x and y are unknown integers, and d is a positive non-square integer. The equation seeks integer solutions, making it a type of Diophantine equation - equations that require integer solutions. 

Even though the equation is often referred to as "Pell's Equation", John Pell (1611 - 1685) had very little to do with this equation. Euler named the equation after Pell because he mistakenly attributed a solution method discovered by Lord Brouncker as Pell's work. Some people also refer the equation as "Fermat's  Equation" - it was in 1657 that Fermat issued the challenge: find a number y such that dy2 + 1 is a square number. In other words, find a number y such that dy2 + 1 = x2 for some integer x. However, work on this equation dates back much further than these mathematicians mentioned above; it has been studied by Brahmagupta (598 - 668 AD), who evidently provided a method for finding solutions.

But why are mathematicians interested in Pell's equation anyway? In my opinion, I think it's mainly because 

1. Historical interest - the equation has been studied for centuries, with contributions from famous mathematicians, some of them are mentioned above. The historical significance makes it an interesting topic of study from a mathematical heritage perspective.
2. Fundamental nature - the equation represents a simple yet non-trivial example of a quadratic Diophantine equation. Understanding its solutions provides insight into more complex Diophantine equations and helps develop general methods for solving them. 
3. Application in Cryptography and Algorithms - the methods used to solve Pell's Equation can be adapted to algorithms in computer science and cryptography, where the security of systems often relies on the difficulty of solving certain equations.

Solving Pell's Equation

Now we come to the exciting part - how do we solve Pell's equation? The answer should be no surprise to you: by using continued fractions! But before I go into that,  I think there is something I need to clarify first, and that is: for what values of d is there a solution? And by solution here, we really mean the non-trivial solutions. It shouldn't be hard for you to see that for all values of d, (x,y) = (1,0) is always a solution, which we call the trivial solution. And it turns out that, for any given positive non-square integer d (which is exactly the restriction of d in the statement of Pell's equation), Pell's equation always has at least one non-trivial solution, and in fact, infinitely many solutions.

Recall the term "convergent of a number" from my earlier posts, where I showed that it can be computed using two recurrence relations pk and qk: pk/qk = [a0; a1, . . . , ak] = Ck. We will find our solutions (x,y) from the sequences (pk,qk). 

Let's look at an example: x2 − 19y2 = 1, and we have the continued fraction expansion of sqrt(19) = [4; 2, 1, 3, 1, 2, 8, 2, 1, 3, 1, 2, 8, ... ]. The convergents of sqrt(19) are displayed in the table below

We can see that when k=5, we have p5=170, q5=39, and p5−19*q5 = 1. Therefore we have obtained one particular solution for d=19!

Note that the period length of the continued fraction expansion of sqrt(19) is 6, and we obtained a particular solution at the second till last entry in the expansion. Is this true for all values of d? In some sense yes, you will always get pk2 −dqk2 = ±1, when k = period length of the expansion - 1. But for Pell's equation, we really want the right hand side to be equal to 1... Don't worry, this changing sign only depends on the parity of the period length, in simple words, whether if the length is odd or even. 

Let's use n to denote the period length, if n is even, then a particular solution is given by (pn−1, qn−1); if n is odd, then a particular solution is given by (p2n−1, q2n−1).

Recall that I said that Pell's equation has infinitely many solutions earlier on, but usually we are interested in the solutions with the smallest size, which we call the fundamental solution. In fact, it can be shown that all solutions of Pell's equation comes from (pk,qk); and I suppose you can see that the sequences pk and qk are monotonically increasing from the recursive relation which was used to define them, therefore, the fundamental solution is given as exactly in the previous paragraph.

The name "fundamental" not only refers to the size of the solution, but from the fundamental solution we can get to all of the other solutions: if (x1, y1) is the fundamental solution of x2 − dy2 = 1, then every pair of integers (xn, yn) given by (x1 + y1*sqrt(d))^n = xn + yn*sqrt(d) is also a solution. And now it's natural to ask: for a given d, do all the solutions of Pell's equation form a group? Would it be cyclic? The answer is yes for both questions, and this leads onto Group Theory and even Algebraic Number Theory...