citations: https://math.stackexchange.com/questions/1139381/good-and-best-rational-approximations
Much has been said about the Pell equation, largely by people who were not Pell. But Euler called the equation "Pell's equation" and it is hard to un-name something once it has been named.
Here is the Pell equation:
$$ x^2 - D y^2 = 1 \ \ \ \ \ \ \ (\textrm{where} \ x, y \ \textrm{are integers}) $$
As I am not thousands of years old, I cannot confidently claim to know who studied the Pell equation first. But people in ancient India (Brahmagupta was one) were thinking about this long before the same equation emerged in Europe (and probably elsewhere) in the mid-1500s.
But why study this equation at all? What was the motivation? Notice that if we rearrange the Pell equation to get
$$ \left( \frac{x}{y} \right)^2 = D + \frac{1}{y^2}, $$
the solutions $(x, y)$, written as a fraction $x/y$, will give a ratio of two integers which is very close to the square root of $D$. Back in the turmetic-colored days of India, it is said that priests needed to know the square root of two to build altars matching ancient specifications ("a square altar with twice the area of another square altar"). But (again, I wasn't there), given that the hypotenuse of a triangle with two unit side lengths is also $\sqrt{2}$, there were probably mundane reasons for wanting to calculate it. So Indian geniuses from nearly 2,000 years ago invested a lot of time investigating roots.
Naturally, one way of doing so was to study the Pell equation -- even if they didn't yet know it was called the Pell equation. They probably got it wrong and called it the Brahmagupta equation or something.
Now say you were looking to solve the Pell equation. How would you go about it? Guess-and-check is one option. You could notice, for example (as Brahmagupta did) that the solution to the Pell equation for $D=8$ is given by $x=3$, $y=1$:
$$ (3)^2 - 8(1)^2 = 1. $$
This is the smallest solution (in the sense that it's the integer solution for the smallest value of $x$.) But I would say -- and this is just me speaking personally -- that it is somewhat harder to notice that the smallest integer solution to
$$ x^2 - 61 y^2 = 1 $$
is given by $$ (1766319049)^2 - 61(226153980)^2 = 1. $$
Now as I said before, from the structure of the Pell equation we expect that its solutions are very close to rational approximations for $D$. For example, let us observe that
$$ \frac{1766319049}{226153980} - \sqrt{61} \approx 0.000000000000000001. $$
So if we're looking for a solution to the Pell equation, it might make sense to turn the question around and ask, "What are the best rational approximations to $\sqrt{D}$?" and try plugging in some of those numbers.
Oh, before I forget. Notice how the difference between $x/y$ and $\sqrt{D}$ seems to be greater than zero. The difference is positive. Is it always positive? Well, any solution satisifes
$$ \left( \frac{x}{y} \right)^2 = D + \frac{1}{y^2}, $$
has an $x/y$ that has to be at least a little bit larger than $\sqrt{D}$,
$$ \frac{x}{y} - \sqrt{D} > 0. $$
Why did I steal your attention to deviate and make this observation? Here's the amazing point. If we can show that
$$ \frac{x}{y} - \sqrt{D} > \frac{1}{2 y^2} $$
(and that $2$ in the denominator is, believe it or not, essential) then it must be the case that $x/y$ is one of the convergents in the continued fraction for $\sqrt{D}$! That would mean that if we can show that identity, we'd be able to find the solution to the Pell equation buried in the convergents to the continued fraction for $\sqrt{D}$.
And indeed, we have
$$ \left( \frac{x}{y} \right)^2 - D = \left( \frac{x}{y} - \sqrt{D} \right) \left( \frac{x}{y} + \sqrt{D} \right) $$
so that
$$ \left( \frac{x}{y} - \sqrt{D} \right) \left( \frac{x}{y} + \sqrt{D} \right) = \frac{1}{y^2} $$
where we can rearrange to find
$$ \begin{aligned} \frac{x}{y} - \sqrt{D} = \frac{1}{y^2} \left( \underbrace{\frac{1}{x/y + \sqrt{D}}}_{> 2 \sqrt{D}} \right) < \frac{1}{2 \sqrt{D} y^2} \leq \frac{1}{2y^2}. \end{aligned} $$
So that is pretty amazing. The only real thing to show now is that if we have that identity, the ratio x/y is really one of the convergents for the continued fraction...
If you can grant for a moment that the "convergents" of the continued fraction to $D$ are in some sense the "best" ones, then we can proceed. The idea of best is like this. Writing the convergent as a numerator over a denominator, there is no way to get a better approximation unless you make the denominator bigger. So any pair $(x', y')$ that's supposed to be a good approximation to $a$ must have a denominator $y' > y$, where $y$ is the largest denominator in the series of convergents which is less than $y$.
So here goes the proof. Let's suppose we have another $(x', y')$ that satisfy
$$ \frac{x'}{y'} - \sqrt{D} < \frac{1}{2 y'^2} $$
but are not convergents in the continued fraction expansion. We'll show that this cannot be the case because that bound is just too tight. Let $(x,y)$ be one of the convergents of the continued fraction to $D$ so that $y$ is the smallest denominator that's greater than $y'$. Then $x/y$ is a better approximation than $x'/y'$. But we've also claimed that the bound above holds. So we have
$$ \frac{x}{y} - \sqrt{D} \leq \left| \frac{x'}{y'} - \sqrt{D} \right| < \frac{1}{2 y'^2} < \frac{1}{2y^2} $$
Well we have the following amazing theorem: that if $(x,y)$ is a solution to the Pell equation, $|x/y - D| < 1/2y^2$, then $x/y$ must be one of the convergents to $\sqrt{D}$. If that is true,
We'll come back to this a little later. When you're trying to solve a problem, sometimes it helps to look at the problem backwards. If we're trying to solve the Pell equation, the solutions will probably be in the neighborhood of the rational approximations to the square root of D. That much we've already said. But if we had another way to get integer approximations to the square root of D, we might have a way of solving the Pell equation. There is such a way. Take, for example,
$$ x^2 = 2. $$
We can rewrite this as
$$ x = 2/x $$
Looking at the above equation again, we can say that $x/y$ is strictly greater than $\sqrt{D}$ -- since $y^2$ is positive -- and so $$ \frac{x}{y} - \sqrt{D} > 0. $$
$$ \frac{x}{y} - \sqrt{D} = \frac{1}{y^2} \frac{1}{\frac{x}{y} + \sqrt{D}} $$
But we already said that $x/y$ was greater than $\sqrt{D}$, so $x/y + \sqrt{D} > 2 \sqrt{D}$, so
$$ \frac{x}{y} - \sqrt{D} = \frac{1}{y^2} \frac{1}{\frac{x}{y} + \sqrt{D}} < \frac{1}{y^2} \frac{1}{2\sqrt{D}} < \frac{1}{2y^2} $$
You might ask: hm. If the ratios get closer and closer to the square root of $D$, and if a solution to the Pell equation is a ratio of integers, and this ratio of integers is so close as to differ only from $D$ a tiny amount, then what are the odds that $x/y$ is actually one of the well-known rational approximations to $\sqrt{D}$? Well what are the odds that it isn't? Suppose we had some solution to the Pell equation. Naturally it would give us a very good rational approximation to $\sqrt{D}$ -- an extremely good one in fact. But those rational approximations can also be obtained from from the continued fraction expansion of $\sqrt{D}$.
The million-dollar question is: are there any rational approximations of $\sqrt{D}$ that are solutions to the Pell equation but don't appear in the continued fraction expansion of $\sqrt{D}$?
then what are the odds that $x/y$ is actually one of the int
In the 1600s, and challenged by Fermat, Brouncker used continued fractions to solve an equation of the form:
This is the equation
Pell had nothing to do with this equation. But because sometimes citations get mixed up, this is called the Pell equation.