Pell’s equation and simple continued fractions

Theorem 1.

Let $d$ be a positive integer which is not a perfect square, and let $(x,y)$ be a solution of $x^{2}-dy^{2}=1$. Then $\frac{x}{y}$ is a convergent in the simple continued fraction expansion of $\sqrt{d}$.

Proof.

Suppose we have a non-trivial solution $x,y$ of Pell’s equation, i.e. $y\neq 0$. Let $x,y$ both be positive integers. From

 $\left(\frac{x}{y}\right)^{2}=d+\frac{1}{y^{2}}$

we see that $\left(\frac{x}{y}\right)^{2}>d$, hence $\frac{x}{y}>\sqrt{d}$. So we get

 $\displaystyle\left|\frac{x}{y}-\sqrt{d}\right|=\frac{1}{y^{2}\left(\frac{x}{y}% +\sqrt{d}\right)}$ $\displaystyle<\frac{1}{y^{2}\left(2\sqrt{d}\right)}$ $\displaystyle<\frac{1}{2y^{2}}.$

This implies that $\frac{x}{y}$ is a convergent of the continued fraction of $\sqrt{d}$. ∎

Title Pell’s equation and simple continued fractions PellsEquationAndSimpleContinuedFractions 2013-03-22 13:21:04 2013-03-22 13:21:04 Thomas Heye (1234) Thomas Heye (1234) 9 Thomas Heye (1234) Theorem msc 11D09