Pell's Equation

Pell's equation is the equation

$$x^2-ny^2 = 1,$$

where $n$ is a nonsquare positive integer and $x,y$ are integers. It can be shown that there are infinitely many solutions to the equation, and the solutions are easy to generate recursively from a single fundamental solution, namely the solution with $x,y$ positive integers of smallest possible size.

The solutions to Pell's equation have long been of interest to mathematicians, not least because of their value as approximations for $\sqrt{n}$: if $x^2-ny^2=1,$ then the fraction $\frac xy$ is a good approximation for $\sqrt{n}.$

Even small values of $n$ can lead to fundamental solutions which are quite large. For example, for $n = 61$ the solution with smallest positive $x$ is $(1766319049,226153980).$

The theory of solutions to the equation is connected with continued fractions, and gives an accessible introduction to some ideas from algebraic number theory.

A very useful way to combine solutions of the equation into new solutions is furnished by Brahmagupta's identity

$$(x^2-ny^2)(a^2-nb^2) = (xa+nyb)^2 - n(xb+ya)^2.$$

Brahmagupta was an Indian mathematician in the $7^\text{th}$ century AD who was one of the first to study Pell's equation in general. (The famous Swiss mathematician Leonhard Euler named the equation after the $17^\text{th}$ century British mathematician John Pell, to whom he mistakenly attributed a solution method discovered by Pell's contemporary Lord Brouncker; this name has unfortunately persisted despite evidence of work on the equation from more than a millennium earlier by Brahmagupta and others.)

Brahmagupta used this identity to combine two solutions $(x,y)$ and $(a,b)$ to Pell's equation into a third solution $(xa+nyb,xb+ya)$. This solution is sometimes called the composition of $(x,y)$ and $(a,b)$. In addition, "near-solutions" can often be composed to produce solutions.

Find a solution to $x^2-7y^2 = 1$.

---

Note that $3^2-7\cdot 1^2 = 2$. Applying Brahmagupta's identity with $(x,y) = (a,b) = (3,1)$ gives

$$\begin{aligned} \big(3^2-7\cdot 1^2\big)\big(3^2-7\cdot 1^2\big) &= \big(3(3)+7(1)(1)\big)^2-7\big(3(1)+1(3)\big)^2 \\ 2 \cdot 2 &= 16^2-7\cdot 6^2. \end{aligned}$$

So $16^2-7\cdot 6^2 = 4$, and dividing by $2^2$ gives $8^2-7\cdot 3^2 = 1$. $_\square$

The numbers $xa+nyb$ and $xb+ya$ in Brahmagupta's identity seem to come from out of nowhere, but in fact they appear quite naturally when the identity is expressed in terms of products of numbers of the form $x+y\sqrt{n}$. This is most naturally expressed via a concept from basic algebraic number theory.

Suppose $\alpha$ is a root of an irreducible polynomial $f(T)$ with rational coefficients. Then the norm of $\alpha$, denoted $N(\alpha)$, is the product of the roots of $f(T)$. $\big($If $f$ is monic, this is $(-1)^k$ times the constant term of $f$, where $k$ is the degree of $f.\big)$

If $\alpha = x+y\sqrt{n}$, then $(\alpha-x)^2 = ny^2$, so $\alpha$ is a root of the polynomial $T^2-2xT+\big(x^2-ny^2\big)$. If $n$ is not a square, this is irreducible, and $N(\alpha) = \big(x+y\sqrt{n}\big)\big(x-y\sqrt{n}\big) = x^2-ny^2.$

Now let $\beta = a+b\sqrt{n}$. Then $\alpha\beta = \big(x+y\sqrt{n}\big)\big(a+b\sqrt{n}\big) = (xa+nyb)+(xb+ya)\sqrt{n}$. Notice that the coefficients of $\alpha\beta$ are the expressions in Brahmagupta's identity; that is, the composition of solutions $(x,y)$ and $(a,b)$ corresponds to the product of the associated expressions $x+y\sqrt{n}$ and $a+b\sqrt{n}$. Then

$$N(\alpha)N(\beta) = \big(x^2-ny^2\big)\big(a^2-nb^2\big) = (xa+nyb)^2-n(xb+ya)^2 = N(\alpha\beta).$$

So Brahmagupta's identity says that the norm of $x+y\sqrt{n}$ is multiplicative. In fact, this is true in general, although the proof requires some advanced machinery.

Suppose $x_1^2-ny_1^2 = 1$. Applying Brahmagupta's identity repeatedly gives an infinite sequence of solutions $(x_1,y_1),(x_2,y_2), (x_3,y_3), \ldots$ to the equation $x^2-ny^2 = 1$, where

$$\begin{aligned} x_k &= x_{k-1}x_1 + ny_{k-1}y_1 \\ y_k &= x_{k-1}y_1 + y_{k-1}x_1. \end{aligned}$$

These solutions are said to be generated by $(x_1,y_1)$.

Note that if $x_1+y_1\sqrt{n} = \alpha$, then $x_2+y_2\sqrt{n} = \alpha^2$, $x_3+y_3\sqrt{n} = \alpha^3$, and so on. The solutions $(x_k,y_k)$ correspond to $\alpha^k = x_k+y_k\sqrt{n}$.

Suppose Pell's equation has a nontrivial solution for $n$. Let $(x,y)$ be the fundamental solution, i.e. the solution with the smallest possible positive values of $x$ and $y$. Then every solution to Pell's equation in positive integers is generated by $(x,y)$.

Note that the real number $\alpha = x+y\sqrt{n}$ is the smallest number greater than $1$ of this form whose norm is $1$. Suppose $(a,b)$ is another solution to Pell's equation with $a,b>0$, and let $\beta = a+b\sqrt{n}$. Then for some $k \ge 1$,

$$\alpha^k \le \beta < \alpha^{k+1}.$$

Then $\gamma = \frac{\beta}{\alpha^k} = \big(a+b\sqrt{n}\big)\big(x-y\sqrt{n}\big)^k$ can be expanded out to give $\gamma = c+d\sqrt{n}$ for some $c,d$. Note that $c,d$ are nonnegative since $1 \le \gamma < \alpha$. Since $\alpha$ was minimal, the only possibility is that $\gamma = 1$ and $\beta = \alpha^k$. So $(a,b)$ is generated by $(x,y)$. $_\square$

To see the ideas of the proof in action, suppose $n = 2$. It's clear by inspection that the fundamental solution is $(3,2)$. So any other solution $(a,b)$ in positive integers satisfies $a+b\sqrt{2} = \big(3+2\sqrt{2}\big)^k$ for some $k$. Any larger solution can be repeatedly divided by $3+2\sqrt{2}$ to produce a smaller one. For instance, note that $99^2-2\cdot 70^2 = 1$. So

$$\begin{aligned} \frac{99+70\sqrt{2}}{3+2\sqrt{2}} &= \big(99+70\sqrt{2}\big)\big(3-2\sqrt{2}\big) = 17 + 12\sqrt{2} \\ \frac{17+12\sqrt{2}}{3+2\sqrt{2}} &= \big(17+12\sqrt{2}\big)\big(3-2\sqrt{2}\big) = 3 + 2 \sqrt{2}, \end{aligned}$$

so $99+70\sqrt{2} = \big(3+2\sqrt{2}\big)^3.$ If repeated division by $3+2\sqrt{2}$ did not eventually produce $3+2\sqrt{2}$, it would produce a smaller solution, which would violate the minimality of $(3,2)$.

What are the first 3 triangular numbers that are also perfect squares?

---

Recall that the $n^\text{th}$ triangle number is $T_{n}$ = $\frac{n(n+1)}{2}$. Set this equal to $x^{2}$. Now multiply both sides by 8 and expand:

$$\begin{aligned} 4n^2+4n &= 8x^2\\ 4n^2+4n+1 &= 8x^2+1 \\ (2n+1)^2-8x^2 &= 1. \end{aligned}$$

Now set $u = 2n+1, v = 2x$ to get $u^2-2v^2 = 1$. As seen above, the solutions are generated by $(3,2)$, and the first three are $(u,v) = (3,2), (17,12), (99,70),$ so $(n,x) = (1,1), (8,6), (49,35)$.

$T_1 = 1$, $T_8 = 36$, and $T_{49} = 1225$ are all squares, as expected. $_\square$

Suppose that $n$ is not a square. The irrational number $\sqrt{n}$ has a simple continued fraction expansion. For shorthand, write

$$a_1+\frac1{a_2+\frac1{a_3+\frac1{\ddots}}} = [a_1,a_2,a_3,\ldots].$$

To derive the continued fraction expansion of $\sqrt{3}$, subtract the floor, invert what is left, and repeat:

\[ \begin{align} \sqrt{3} &= 1+\big(\sqrt{3}-1\big) \\
&= 1 + \frac2{\sqrt{3}+1} \\ &= 1+ \frac1{\hspace{1.5mm} \frac{\sqrt{3}+1}2\hspace{1.5mm} } \\ &= 1+\frac1{1+\frac{\sqrt{3}-1}2} \\ &= 1+\frac1{1+\frac1{\sqrt{3}+1}} \\ &= 1+\frac1{1+\frac1{2+\big(\sqrt{3}-1\big)}}, \end{align} \]

and the process will repeat to give

$$\sqrt{3} = 1 + \frac1{1+\frac1{2+\frac1{1+\frac1{2+\frac1{\ddots}}}}}= [1,1,2,1,2,\ldots] = [1,\overline{1,2,}].$$

$($The bar indicates that $1,2,$ repeat indefinitely, similar to a bar over repeating decimal digits.$)$

Here are some facts about the continued fraction expansion of $\sqrt{n}$, presented without proof.

(1) The continued fraction expansion is of the form $[a_0,\overline{a_1,a_2,\ldots,a_k}]$ for some integers $a_i$.
(2) $a_0 = \lfloor \sqrt{n} \rfloor$, and $a_k = 2a_0$.
(3) $a_1,a_2,\ldots,a_{k-1}$ is a palindrome, i.e. $a_1 = a_{k-1}$, $a_2 = a_{k-2}$, etc.
(4) Pell's equation always has nontrivial solutions. The fundamental solution is $$\frac{x}{y} = \begin{cases} [a_0,a_1,\ldots,a_{k-1}] &\text{if } k \text{ is even} \\ [a_0,a_1,\ldots,a_{2k-1}] &\text{if } k \text{ is odd}. \end{cases}$$ (5) The equation $x^2-ny^2=-1$ has solutions if and only if $k$ is odd; in this case, the minimal solution is $[a_0,a_1,\ldots,a_{k-1}]$.

In particular, fact (4) gives an algorithm to find the fundamental solution to Pell's equation for any $n$.

The continued fraction expansion of $\sqrt{21}$ is $[4,\overline{1,1,2,1,1,8}]$. Since $k = 6$, the fundamental solution to Pell's equation is the numerator and denominator of

$$\begin{aligned} [4,1,1,2,1,1] &= 4+\frac1{1+\frac1{1+\frac1{2+\frac1{1+\frac11}}}} \\ &= 4+\frac1{1+\frac1{1+\frac1{\hspace{1.5mm} \frac52\hspace{1.5mm} } }} \\ &= 4+\frac1{1+\frac1{\hspace{1.5mm} \frac75 \hspace{1.5mm}}}\\ &= 4+\frac1{\hspace{1.5mm} \frac{12}7\hspace{1.5mm} } \\ &= \frac{55}{12}. \end{aligned}$$

Check: $55^2-21(12)^2 = 1.$

On the other hand, the continued fraction expansion of $\sqrt{13}$ is $[3,\overline{1,1,1,1,6}]$, with $k=5$, so the fundamental solution is the numerator and denominator of

$$[3,1,1,1,1,6,1,1,1,1] = \frac{649}{180}.$$

And $\frac{x}{y} = [3,1,1,1,1] = \frac{18}{5}$ gives a solution to $x^2-13y^2 = -1$.