9 Real quadratic fields and Pell’s equation
9.1 Setup
Having studied which integers can be written as \(X^2 + Y^2,\) \(X^2 + 2Y^2\) etc, we’re now going to change tack a bit, and study representations of integers in the form \(X^2 - n Y^2\) for \(n > 0.\)
This change of sign might seem insigificant, but it actually changes the whole flavour of the theory. For \(n > 0,\) it’s obvious that there are at most finitely many solutions to \(X^2 + n Y^2 = r\) for any given \(r,\) and all solutions will have \(|X| \leqslant\sqrt{|r|}\) and \(|Y| \leqslant\sqrt{\tfrac{|r|}{n}},\) so we can find all of them with a finite search. However, for \(X^2 - n Y^2 = r,\) it’s perfectly possible that there could be infinitely many solutions; and if solutions do exist, it’s not at all obvious how big they might be, so we can’t rely on finding solutions with a computer search.
Definition 9.1
An equation of the form \(X^2 - n Y^2 = 1,\) for a given \(n \in \mathbb{N}_+,\) is called a Pell equation. More generally, an equation of the form \(X^2 - nY^2 = r,\) for given \(n \in \mathbb{N}_+\) and \(r \in \mathbb{Z},\) is called a generalized Pell equation.
We want to know if Pell and generalized Pell equations have solutions with \((X, Y) \in \mathbb{Z}^2,\) and find a way of describing all such solutions.
Remark 9.2
Note the crucial importance of the condition \(n > 0.\) If we were to allow \(n < 0,\) then it is obvious that there can be at most finitely many solutions for a given \(n\) and \(r,\) and we can find all of them by a routine search. In contrast, when \(n > 0\) (and \(n\) is not a square), we’ll see that the solution set is always either empty or infinite.
The case of \(n\) a perfect square is easy: if \(n = m^2,\) then our equation becomes \((X - mY)(X + mY) = r,\) and since \(X \pm mY\) are integers, they must be in the finite list of divisors of \(r.\) So we can easily find all solutions by considering the prime factorization of \(r.\)
Example 9.3
Let’s find all integer solutions of \(X^2 - 4Y^2 = 9.\)
If \((X, Y)\) is a solution, then \(X - 2Y\) must divide 9, so it is one of \(\{ \pm 1, \pm 3, \pm 9\}.\) Trying each possibility leads to the six solutions \((\pm 5, \pm 2)\) and \((\pm 3, 0).\)
If \(n\) is not a perfect square, then Pell’s equation is closely related to the arithmetic of the ring \(\mathbb{Z}[\sqrt{n}] = \{a + b \sqrt{n} : a, b \in \mathbb{Z}\}.\) Note that since \(n > 0,\) this is a subring of \(\mathbb{R}\) (unlike the rings \(\mathbb{Z}[i],\) \(\mathbb{Z}[\sqrt{-3}],\) \(\mathbb{Z}[\omega]\) from the previous chapters, which are contained in \(\mathbb{C}\) but not in \(\mathbb{R}\)). We’ll mostly focus on \(n = 2.\)
Definition 9.4
If \(x = a + b \sqrt{n} \in \mathbb{Z}[\sqrt{n}],\) we write \(x^* = a - b\sqrt{n},\) and we define \[N(x) = x x^* = a^2 - n b^2.\]
We call this the norm of \(x\) (although it’s not a norm in the sense of analysis). We already used this for \(n = -1, -2, -3\) in the previous chapter (in which case \(x^* = \bar{x}\) is the complex conjugate of \(x,\) and \(N(x)\) is the square of the complex absolute value); but now we want to take \(n > 0.\) Observe that \(x^*\) is still well-defined, since \(\sqrt{n}\) is irrational and so there is a unique way of writing \(x\) as \(a + b\sqrt{n}.\) The map \(N\) still respects multiplication, i.e. \(N(xy) = N(x) N(y).\) However, what’s new is that the map \(N\) can take negative values. For example, \(N(1 + \sqrt{2}) = -1.\)
9.2 Pell’s equation and units
Proposition 9.5
Assume \(n\) is not a perfect square. Then there is a bijection between pairs of integers \((X, Y)\) with \(X^2 - n Y^2 = r,\) and the set \(\{ \alpha \in \mathbb{Z}[\sqrt{n}] : N(\alpha) = r\},\) given by \((X, Y) \mapsto X + Y \sqrt{n}.\) 0◻
Now we have much more structure to work with, because the norm is multiplicative. In particular, if \(r = 1,\) the solution set is actually a group: it is clearly closed under multiplication, and since \(N(x) = 1\) implies \(x^{-1} = x^*,\) it is also closed under inverses. So it is a subgroup of the unit group \(\mathbb{Z}[\sqrt{n}]^\times.\) This allows us to get new solutions from old:
Example 9.6
Consider the equation \(X^2 - 2 Y^2 = 1.\)
One obvious non-trivial solution is \((X, Y) = (3, 2)\); that is, \(N(3 + 2 \sqrt{2}) = 1.\) So \(N((3 + 2 \sqrt{2})^k) = 1\) for all \(k \geqslant 1,\) giving us the solutions \[\begin{aligned} (3 + 2 \sqrt{2})^2 = 17 + 12\sqrt{2} &\Rightarrow 17^2 - 2 \cdot 12^2 = 1\\ (3 + 2 \sqrt{2})^3 = 99 + 70\sqrt{2} &\Rightarrow 99^2 - 2 \cdot 70^2 = 1\\ &\vdots \end{aligned}\] Clearly this cannot repeat (since \(3 + 2 \sqrt{2}\) is a real number and not \(\pm 1,\) so no power of it can be equal to 1). So we obtain infinitely many non-trivial solutions.
Notice that if \((X, Y)\) is a non-trivial solution of the Pell equation, then so is \((\pm X, \pm Y).\) This corresponds to replacing \(u = X + Y\sqrt{n}\) with \(\pm u\) or \(\pm u^{-1}.\) So we can assume \(X, Y > 0,\) which corresponds to assuming \(u > 1.\)
Definition 9.7
A positive-integer solution \((A, B)\) of Pell’s equation is said to be fundamental if for all other positive-integer solutions \((X, Y),\) we have \(A + B \sqrt{n} < X + Y \sqrt{n}.\)
If \((A, B)\) is the fundamental solution, then \(u = A + B \sqrt{n}\) is called the fundamental positive unit of \(\mathbb{Z}[\sqrt{n}].\)
Proposition 9.8
If Pell’s equation has non-trivial solutions (for a given \(n\)), then it has a fundamental solution.
Proof. If \((X, Y)\) is a positive solution, then there are clearly only finitely many pairs of positive integers \((X', Y')\) with \(X' + Y' \sqrt{n} \leqslant X + Y \sqrt{n}\) (since both \(X'\) and \(Y'\) must lie in a bounded range). So there are certainly only finitely many such pairs that are solutions of the equation; and a finite subset of \(\mathbb{R}\) must have a least element.
Example 9.9
Returning to the previous example, if \(X, Y\) are positive with \(X + Y \sqrt{2} < 3 + 2\sqrt{2},\) then \(X < 3 + 2 \sqrt{2} < 5,\) and \(Y < (3 + 2\sqrt{2}) / \sqrt{2} < 4.5.\) So \(1 \leqslant X, Y \leqslant 4,\) and none of these leads to a smaller solution. Thus \((3, 2)\) is the fundamental solution of Pell’s equation for \(n = 2.\)
Proposition 9.10
If Pell’s equation has non-trivial solutions (for a given \(n\)), and \(u\) is the fundamental positive unit, then every solution with \(X, Y > 0\) is of the form \[X + Y \sqrt{n} = u^k\] for a uniquely determined \(k \in \mathbb{N}_+.\)
Equivalently, the full set of solutions (with no assumption on signs) is given by \[X + Y \sqrt{n} = \{\pm u^k : k \in \mathbb{Z}\}.\]
Proof. Let \((X, Y)\) be any solution with \(X, Y > 0,\) and consider \(v = X + Y \sqrt{n}.\) Then \(v > 1,\) but the sequence \(v / u^k\) obviously tends to 0, so there must be a largest \(k\) such that \(v / u^k \geqslant 1.\)
For this \(k,\) the ratio \(v' = v / u^k\) satisfies \(1 \leqslant v' < u.\) If \(1 < v',\) then this would contradict the minimality of \(u\); so we must have \(v' = 1,\) i.e. \(v = u^k\) is a power of \(u.\)
Example 9.11
To complete our \(n = 2\) example, the complete set of solutions to \(X^2 - 2Y^2 = 1\) is given by \[X + Y\sqrt{2} = \pm (3 + 2 \sqrt{2})^k\] for any choice of sign and \(k \in \mathbb{Z}.\)
More algebraically, we’re saying that the group \(\{v \in \mathbb{Z}[\sqrt{n}]^\times : \operatorname{N}(v) = 1\}\) must be either \(\pm 1,\) or the product of \(\pm 1\) and an infinite cyclic group generated by the fundamental positive unit. In fact the former case never occurs:
Theorem 9.12
For any non-square \(n,\) the Pell equation \(X^2 - n Y^2 = 1\) does have non-trivial solutions.
Remark 9.13
We won’t prove this here. It can be deduced from a much more general theorem of Dirichlet about units in a general number field (see Appendix B of Stewart and Tall). Alternatively, there is a more elementary, but still rather difficult, proof in §IV.11 of Davenport’s book, based on studying rational approximations to \(\sqrt{n}.\)
Exercise 9.14
Show that \(\mathbb{Z}[\sqrt{7}]\) does have a fundamental positive unit (and find it explicitly).
9.3 The negative Pell equation
We’ll now consider the case \(r = -1.\) These don’t form a group, obviously; but we can fix this by considering the set of solutions for \(r = -1\) and \(r = +1\) together:
Proposition 9.15
The set of solutions of \(X^2 - n Y^2 = \pm 1\) bijects with the unit group \(\mathbb{Z}[\sqrt{n}]^\times.\) 0◻
Proof. If \(\alpha\) is invertible in \(\mathbb{Z}[\sqrt{n}],\) then \(\operatorname{N}(\alpha)\) is invertible in \(\mathbb{Z},\) so it must be \(\pm 1.\) Conversely, if \(\alpha \in \mathbb{Z}[\sqrt{n}]\) has \(\operatorname{N}(\alpha ) = \pm 1,\) then \(\alpha^{-1} = \pm \alpha^* \in \mathbb{Z}[\sqrt{n}].\)
Arguing exactly as in the previous section, if the set of numbers of the form \(X + Y\sqrt{n}\) with \(X, Y > 0\) and \(X^2 - n Y^2 = \pm 1\) is non-empty, then it has a smallest element, which we call the fundamental unit. For instance, the fundamental unit of \(\mathbb{Z}[\sqrt{2}]\) is \(1 + \sqrt{2},\) which is the square root of the fundamental positive unit \(3 + 2 \sqrt{2}.\)
In general, there are two cases which can arise:
The fundamental unit has \(N(u') = +1.\) In this case, the fundamental unit and fundamental positive unit coincide, we have \(N(\alpha) = 1\) for all \(\alpha \in \mathbb{Z}[\sqrt{n}]^\times,\) and \(X^2 - n Y^2 = -1\) has no solutions.
The fundamental unit has \(N(u') = -1.\) In this case, the fundamental positive unit is the square of the fundamental unit (as we saw for \(n = 2\)), and multiplying by the fundamental unit gives a bijection between solutions of \(X^2 - n Y^2 = -1\) and solutions of \(X^2 - n Y^2 = +1.\) Algebraically, \(\{ \alpha \in \mathbb{Z}[\sqrt{n}]^\times : N(\alpha) = 1\}\) is an index 2 subgroup of \(\mathbb{Z}[\sqrt{n}]^\times,\) and both groups are isomorphic to \(\{\pm 1\} \times \mathbb{Z}.\)
Remark 9.16
If \(n\) is prime, then the fundamental unit always has norm 1 if \(n = 3 \bmod 4,\) and has norm \(-1\) otherwise. For composite \(n\) the situation is more complicated and not fully understood. \(\circledast\)
9.4 Generalized Pell equations
For the generalized Pell equation with \(r \ne \pm 1,\) we need to combine the information we’ve just gathered about units, with information about factorization. Using basically the same argument as before, we can show:
Theorem 9.17
The ring \(\mathbb{Z}[\sqrt{2}]\) is Euclidean, with Euclidean function \(\delta(x) = |N(x)|.\)
Hence it is a PID, and thus a UFD; but we need to remember that – as with any UFD – factorizations are only unique up to units, and we’ve seen that the unit group of \(\mathbb{Z}[\sqrt{2}]\) is quite large.
Theorem 9.18
If \(p \in \mathbb{P},\) then \(X^2 - 2 Y^2 = p\) has integer solutions if and only if \(p = 2\) or \(p \equiv \pm 1 \bmod 8.\)
Proof. The non-trivial point is to show that if \(p\) is odd with \(\left(\frac{2}{p}\right) = 1,\) then \(X^2 - 2Y^2 = p\) has solutions. This is essentially the same argument as we have already seen for \(X^2 + Y^2\) and \(X^2 + 2Y^2,\) with a little more care about signs: if \(t\) is a square root of \(2 \bmod p,\) and \(\alpha = \gcd(t - \sqrt{2}, p),\) then \(N(\alpha)\) must be \(\pm 1\) or \(\pm p.\) But \(\alpha\) is not a unit, since there is a ring homomorphism \(\mathbb{Z}[\sqrt{2}] \to \mathbb{F}_p\) which sends both \(t - \sqrt{2}\) and \(p\) to 0. Hence \(\alpha\) must have norm \(\pm p\); and since \(\alpha\) is only defined up to units, we can multiply by \(1 + \sqrt{2}\) if needed so that \(N(\alpha)= p.\)
Exercise 9.19
Show that if \(p \in \mathbb{P}\) with \(p > 3,\) then \(X^2 - 3 Y^2 = p\) has solutions iff \(p = 1 \bmod 12,\) and \(X^2 - 3 Y^2 = -p\) has solutions iff \(p = -1 \bmod 12.\) (Hint: \(\mathbb{Z}[\sqrt{3}]\) is Euclidean, but its fundamental unit has norm \(+1\)).
To classify all solutions, we need to keep track of which units can occur:
Example 9.20
Consider the equation \(X^2 - 2 Y^2 = 7.\)
I claim that every solution has the form \(X + Y \sqrt{2} = \pm (5 + 3 \sqrt{2}) \cdot (3 + 2\sqrt{2})^k\) or \(\pm(5 - 3 \sqrt{2}) (3 + 2\sqrt{2})^k\) for some \(k \in \mathbb{Z}\); and these possibilities are mutually exclusive.
To see this, note that \(7 = \alpha\beta\) where \(\alpha = 5 + 3 \sqrt{2}\) and \(\beta = 5 - 3 \sqrt{2}.\) Since \(N(\alpha) = N(\beta) = 7\) is prime, they are both indecomposable, and hence prime, elements of \(\mathbb{Z}[\sqrt{2}].\) Moreover, they are not associates (they do not divide each other), since \(\alpha / \beta = \tfrac{43 + 30\sqrt{2}}{7} \notin \mathbb{Z}[\sqrt{2}].\)
If \((X, Y)\) is any solution of \(X^2 - 2Y^2 = 7,\) then \(\gamma = X + Y\sqrt{2}\) satisfies \(\gamma \gamma^* = 7,\) so \(\gamma \mid \alpha \beta.\) Moreover, \(\gamma\) is also indecomposable and hence prime (because \(N(\gamma) = 7\)). Hence either \(\gamma\) is an associate of \(\alpha,\) or \(\gamma\) is an associate of \(\beta.\)
The general picture is as follows. As we’ve seen, the solutions of \(X^2 - 2Y^2 = 1\) are a group. For any \(r,\) multiplication in \(\mathbb{Z}[\sqrt{2}]\) gives a group action of the group of solutions of \(X^2 - 2Y^2 = 1\) on the set of solutions of \(X^2 - 2Y^2 = r.\) Using uniqueness of prime factorisations, we can show that this group action has finitely many orbits (and we can determine the orbits explicitly from the prime factorisation of \(r\)).
Exercise 9.21
Find a similar description of the solutions of \(X^2 - 2 Y^2 = 14\) (you should find that there are again two orbits). How many orbits are there for \(X^2 - 2Y^2 = 119\)?
Remark 9.22
If we replace \(X^2 - 2Y^2\) with \(X^2 - n Y^2,\) for general non-square \(n > 0,\) then it’s still true that the solutions of \(X^2 - n Y^2 = r\) for any \(r\) fall into finitely many orbits up to the action of the units. However, since \(\mathbb{Z}[\sqrt{n}]\) is not always a UFD, there may not be a simple criterion describing the \(r\) for which the equation is solvable.
(It is an open problem whether there are infinitely many square-free \(n > 0\) such that \(\mathbb{Z}[\sqrt{n}]\) is a UFD. \(\circledast\))