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{align} \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{align} \]

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{align} 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{align}\]

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{align} \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{align}\]

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{align} 4n^2+4n &= 8x^2\\ 4n^2+4n+1 &= 8x^2+1 \\ (2n+1)^2-8x^2 &= 1. \end{align}\]

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{align} [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{align} \]

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 \).