Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2009 | Book

Introduction Read chapter Read first chapter

Solving the Pell Equation

Authors: Michael J. Jacobson Jr., Hugh C. Williams

Publisher: Springer New York

Book Series : CMS Books in Mathematics

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

Pell’s Equation is a very simple Diophantine equation that has been known to mathematicians for over 2000 years. Even today research involving this equation continues to be very active, as can be seen by the publication of at least 150 articles related to this equation over the past decade. However, very few modern books have been published on Pell’s Equation, and this will be the first to give a historical development of the equation, as well as to develop the necessary tools for solving the equation.

The authors provide a friendly introduction for advanced undergraduates to the delights of algebraic number theory via Pell’s Equation. The only prerequisites are a basic knowledge of elementary number theory and abstract algebra. There are also numerous references and notes for those who wish to follow up on various topics.

Table of Contents

Frontmatter
1. Introduction
A Diophantine equation is an indeterminate equation whose unknowns are only allowed to assume integral* or sometimes rational values. The study of such equations goes back to the ancients; indeed, they are named after Diophantus of Alexandria (c. 200–284 AD) in honour of his work on them.1. However, it is most likely that the Greek mathematicians were investigating their properties much earlier than this. To take a simple example, consider the equation
$$x^2 + y^2 = z^2$$
(1.1)
, where we constrain a solution (x, y, z) to be a triple of integers.2 Every student of high school geometry is familiar with the solution (3, 4, 5) and some are even made aware of the additional solutions (5, 12, 13) and (8, 15, 17). In fact, as we shall see below, there exists an infinitude of distinct integral solutions of (1.1) for which (x, y, z) = 1.
Michael J. Jacobson Jr., Hugh C. Williams
2. Early History of the Pell Equation
This chapter is devoted to various aspects of the history of the Pell equation before the work of Lagrange. As this topic has already been dealt with in some detail by Konen,1 Whitford,2, and Dickson,3 our discussion here will be brief. We will concentrate on providing a more modern historical perspective and a somewhat different presentation of this material than that given in these earlier works.
Michael J. Jacobson Jr., Hugh C. Williams
3. Continued Fractions
While the techniques of the Indian mathematicians and those of Brouncker, Euler, and Lagrange for solving the Pell equation are different to some degree, they can all be unified by considering the theory of what are called semiregular continued fractions.
Michael J. Jacobson Jr., Hugh C. Williams
4. Quadratic Number Fields
In this chapter we will show how the Pell equation has an important connection to the theory of real quadratic number fields. In order to do this, it will first be necessary to develop some theory of these structures. Several of the results in this section will be given without proof because they are standard elementary results which can be found in several texts.1 We will begin with the definition of an algebraic number
Michael J. Jacobson Jr., Hugh C. Williams
5. Ideals and Continued Fractions
Throughout this chapter we will let \(\mathcal{O} = \left[1, \omega \right]\) be the order of discriminant Δ in the quadratic field \(\mathbb{K} = \mathbb{Q} \left(\sqrt{D}\right)\). If a is any ideal of \(\mathcal{O}\), it is evident that its corresponding ideal class, [a], contains an infinitude of ideals. In order to deal with this difficulty in managing [a], we will restrict our attention to a finite subset of particular ideals of [a]. To this end we provide the following definitions.1
Michael J. Jacobson Jr., Hugh C. Williams
6. Some Special Pell Equations
Let D be a positive non-square integer and let (t, u) denote the fundamental solution of the Pell equation
$$T^2 - DU^2 = 1$$
(6.1)
. In this chapter we will be concerned with Pell equations for which the values of t and u tend to be small. As we shall see later in Chapter 9, this appears to be a very unusual circumstance; for this reason, then, if no other, it is of some interest to investigate this phenomenon. For example, consider the case of D = M2 − 1 for \(M \in \mathbb{Z}^{>0}\). Clearly, (M, 1) is a solution of the Pell equation (6.1). Furthermore, it is easy to verify that this is the fundamental solution. Of course, we might regard such Pell equations as being easy to solve, and in a sense this is the case; however, there are a few problems that do develop.
Michael J. Jacobson Jr., Hugh C. Williams
7. The Ideal Class Group
As we have seen in §4.3 of Chapter 4, solutions of the Pell equation are closely related to the fundamental unit of a real quadratic field. In particular, the regulator, defined in §5.3 to be the logarithm of the fundamental unit, is the number of bits of a fundamental solution up to a small constant factor. In Chapter 6 we have seen that the size of the regulator can vary greatly; indeed, there are many special families of discriminants that yield very small regulators.
Michael J. Jacobson Jr., Hugh C. Williams
8. The Analytic Class Number Formula
In much of what will follow we will be concerned with problems which require knowledge of bounds on hΔ and RΔ. To this end, we need to develop the analytic class number formula,1 a remarkable result which relates hΔ, RΔ, Δ, and a particular value of a function called the Dirichlet L-function.2 In order to derive this formula we first need to discuss some results concerning characters.
Michael J. Jacobson Jr., Hugh C. Williams
9. Some Additional Analytic Results
By (8.9), it is clear that we can evaluate hΔ for any order \(\mathcal{O}\) of discriminant Δ of \(\mathbb{K}\), once we know the unit index n and \(h_\mathbb{K}\). However, if we refer to Corollary 8.35.1 for determining \(h_\mathbb{K}\), we notice that the expression for L(1, χΔ) is an infinite series. The purpose of this section is to derive a closed-form formula for \(h_\mathbb{K}\). To this end we must first consider some properties of a particular Gauss sum.
Michael J. Jacobson Jr., Hugh C. Williams
10. Some Computational Techniques
In the previous chapters, various methods for computing the regulator were presented. Using Shanks’ infrastructure, we have seen in Chapter 7 how to improve the continued fraction algorithm for computing the regulator using the baby-step giant-step method, resulting in an algorithm that computes RΔ unconditionally in time O(Δ1/4+∈) and, using improvements due to Buchmann, Williams, and Vollmer, in time O(R Δ 1/2 Δ∈). In Chapter 8 we have seen how the class number and regulator are intimately connected to L(1, χ) via the analytic class number formula (Corollary 8.35.1), and in Chapter 9 methods for efficiently computing estimates of hΔ or hΔRΔ using the analytic class number formula were discussed.
Michael J. Jacobson Jr., Hugh C. Williams
11. (f, p) Representations of $$\mathcal{O}$$ -ideals
We assume in this chapter and the next that \(\mathcal{O}\) is an order of \(\mathbb{K}\) with positive discriminant Δ. As we have seen in the previous chapter, we can greatly improve the speed of determining RΔ when we make use of the infrastructure technique of Shanks. Unfortunately, however, this requires that we compute distances, and as such quantities are logarithms of quadratic irrationals, they must be transcendental numbers.1 This means, of course, that we cannot compute them to full accuracy but must instead be content with approximations to a fixed number of figures. When Δ is small, this is not likely to cause many difficulties, but when Δ becomes large, we have no real handle on how much round-off or truncation error might accumulate. Numerical analysts pay a great deal of attention to this problem, but, frequently, computational number theorists ignore it, hoping or believing that their techniques are sufficiently robust that serious deviations of their results from the truth will not occur. It must be admitted that this is usually what happens, but if a computational algorithm is to produce a numerical answer that is to be formally accepted as correct, it must contain within it the same aspects of rigour that one would expect within any mathematical proof. This means that we must provide provable bounds on the possible errors in our results.
Michael J. Jacobson Jr., Hugh C. Williams
12. Compact Representations
As we have seen in Chapter 9 (cf. (9.26)), we would expect that
$$R_{\mathbb{K}} \gg \Delta_{\rm \mathbb{K}}^{1/2-\epsilon}$$
holds for a large proportion of all the real quadratic fields. It follows that for such fields,
$$\epsilon_\Delta \gg {\rm exp}(\Delta_{\rm \mathbb{K}}^{1/2-\epsilon})$$
. If
$$\epsilon_\Delta = (x + y\sqrt\Delta)/2$$
, where
$$x, y \in {\rm Z}$$
, then
$$x = \epsilon_\Delta + \bar\epsilon_\Delta$$
,
$$y = (\epsilon_\Delta - \bar\epsilon_\Delta)/{\sqrt \Delta}$$
. Also, since
$$\epsilon_\Delta \mid \overline{\epsilon_\Delta} \mid = 1$$
and
$$\epsilon_\Delta > 1$$
, we see that
$$x, y \gg {\rm exp}(\Delta^{1/2-\epsilon})$$
. When Δ is large, this implies that x and y could be so enormous that it would not be possible to write them out in conventional decimal representation. Indeed, it is clear that the problem of doing so is of exponential complexity in Δ1/2. For example, at the end of §3.3 we mentioned the 30-digit
$$D = 990676090995853870156271607886$$
. By using the ideas mentioned in Chapter 10, it was shown1 that
$$R_\Delta = 4770372955851343.43$$
.
Michael J. Jacobson Jr., Hugh C. Williams
13. The Subexponential Method
Up to this point, all the algorithms we have presented for computing the regulator RΔ of the real quadratic order OΔ, and, hence, for solving Pell’s equation, have exponential complexity in the size of the discriminant Δ. The most exciting recent development has certainly been the discovery of a Las Vegas algorithm1 by Buchmann for computing RΔ and hΔ whose expected running time is subexponential in log ¦Δ¦. This algorithm has enabled the computation of RΔ for discriminants Δ as large as 101 decimal digits, a dramatic improvement over what had been attainable previously. Unfortunately, as we will discuss in more detail below, this improvement comes at a price. Like Lenstra’s algorithm for computing RΔ described in Chapter 10, the complexity result is conditional on the generalized Riemann hypothesis (GRH) for Hecke L-functions and the extended Riemann hypothesis (ERH), but in the case of the subexponential algorithm, the correctness of the output is conditional as well. Nevertheless, the fact that RΔ can be computed in subexponential time, even assuming the GRH and ERH, remains an important breakthrough.
Michael J. Jacobson Jr., Hugh C. Williams
14. Applications to Cryptography
We now live in a world where the security and integrity of our information and communications is not guaranteed, where the number and sophistication of attacks on these systems are increasing rapidly, and where the impact of those attacks can be measured in billions of dollars and in the loss of reputation and personal integrity. Thus, it is essential today, more than ever, to develop techniques that will protect our communications. One essential component of any installation in which secure communication is needed is cryptography. Its use goes back to Julius Caesar, or perhaps even earlier.1
Michael J. Jacobson Jr., Hugh C. Williams
15. Unconditional Verification of the Regulator and the Class Number
We have seen that if ∈Δ is the fundamental unit of \(\mathcal{O} = \left[1, \sqrt{D} \right]\), then
$$t + u\sqrt D = \left\{ \begin{array}{ll} \epsilon_\Delta \;\; {\rm when} \; N(\epsilon_\Delta) = 1 \\ \epsilon_\Delta^2 \;\; {\rm when}\; N(\epsilon_\Delta) = -1\, , \end{array}\right. $$
, where t, u is the fundamental solution of the Pell equation. We have also seen in Chapter 12 that if we have a sufficiently accurate approximation R Δ ′ to RΔ = log ∈Δ, then we can compute a compact representation of ∈Δ, from which it is a simple matter to determine certain properties of t and u. This is of particular importance when ∈Δ is very large, which, as we have pointed out, is often the case when Δ is large.
Michael J. Jacobson Jr., Hugh C. Williams
16. Principal Ideal Testing in $$\mathcal{O}$$
Let i be any given \(\mathcal{O}\)-ideal. In this chapter we will denote by P the problem of determining whether or not i is a principal \(\mathcal{O}\)-ideal. Of course, as we can easily find α and a reduced \(\mathcal{O}\)-ideal b such that b = (α)i, we may consider this problem as applying, instead, to a given reduced \(\mathcal{O}\)-ideal b. Also, since a principal ideal is invertible, we may also assume that b (or i) is invertible. An extended version of P is the problem of determining, once we know that b is principal, a generator β of b. By our observations in Chapter 12, all we really need to determine β is some q, b ∈ \(\mathbb{Q}\) such that ¦log2β − b¦ < q, where q is small, say q ≤ 10. Both of these problems can be solved by the index-calculus method described in §13.4, but because we need the truth of unproved hypotheses to be sure our result is correct, particularly when b has been declared not principal, this technique is conditional. In this chapter we will develop methods for solving P that are either unconditional or are only conditional concerning the runtime; the answer is still mathematically correct (a Las Vegas algorithm). The problem with these processes is that they are unfortunately of exponential complexity.
Michael J. Jacobson Jr., Hugh C. Williams
17. Conclusion
In this section1 we will investigate the Diophantine equation
$$ax^2 + bxy + cy^2 + dx + ey + f = 0\,\,,$$
(17.1)
, where it is required to find integral values of x and y, given a, b, c, d, e, f ∈ \(\mathbb{Z}\). This is the most general form of a quadratic Diophantine equation in two variables and, as such, represents a further generalization of the Pell equation.2 A method for solving this equation was given over 200 years ago by Lagrange,3 and this method has not been improved significantly since that time. The reason for this is that Lagrange’s method works perfectly well as long as the coefficients in (17.1) do not get very large. However, if we put H = max{¦a¦, ¦b¦, ¦c¦, ¦d¦, ¦e¦, ¦f¦}, it has been shown4 that there is an infinite collection of equations of the form (17.1) having integer solutions x, y, but none with max{¦x¦, ¦y¦} ≤ 2H/5. Thus, it is possible for solutions of (17.1) to be very large, even when H is only moderately large. For such cases, Lagrange’s method will likely be far too slow to produce the solutions of (17.1). We will show here how our previously developed results can be used to produce a faster method for solving this equation.
Michael J. Jacobson Jr., Hugh C. Williams
Backmatter
Metadata
Title
Solving the Pell Equation
Authors
Michael J. Jacobson Jr.
Hugh C. Williams
Copyright Year
2009
Publisher
Springer New York
Electronic ISBN
978-0-387-84923-2
Print ISBN
978-0-387-84922-5
DOI
https://doi.org/10.1007/978-0-387-84923-2

Premium Partner

    Image Credits