You are here

Solving the Pell Equation

Michael J. Jacobson, Jr. and Hugh C. Williams
Publisher: 
Springer
Publication Date: 
2009
Number of Pages: 
495
Format: 
Hardcover
Series: 
CMS Books in Mathematics
Price: 
79.95
ISBN: 
9780387849225
Category: 
Monograph
[Reviewed by
Thomas Hagedorn
, on
07/15/2009
]

“Solving the Pell Equation” provides a much-needed comprehensive reference work on the methods used to solve the misnamed Pell’s equation x2 – ny2 = 1. Given that this equation has been studied for over two millennia and is introduced to most elementary number theory students, it is surprising that only two books have appeared on Pell’s equation. In 2003, Barbeau published the delightful “Pell’s Equation,” which covers some of the same material as the book under review, but differs in being an exercise-book in algebra for college students. In contrast, “Solving the Pell Equation” is a traditional mathematical monograph that offers encyclopedic in-depth coverage of its topic.

While organized into seventeen chapters, “Solving the Pell Equation” can be broken up into three main areas. The first three chapters give an overview of classical methods for solving Pell’s equation, concluding with the simple continued fraction method commonly seen in an elementary number theory course. The next six chapters then introduce the standard concepts of algebraic number theory (such as ideals, class groups and numbers, the regulator, and the analytic class number formula) needed for a more modern study of Pell’s equation. Solving Pell’s equation is shown to be equivalent to the problem of finding the fundamental unit (with norm 1) of a quadratic number field and some special cases of Pell’s equation are considered.

The third part of the book is perhaps its heart. In chapters 10–13 and 15, the authors present a detailed account of the state of the art computational techniques for solving Pell’s equation for large n. They present Buchmann’s subexponential method (so-called as its complexity cost is probabilistically subexponential in log n) for calculating the regulator of a quadratic number field and show how one can verify that the subexponential’s estimate for the regulator and class number without assumptions such as the Riemann hypothesis.

These chapters are the densest part of the book, presenting state of the art results, many due to the authors, that are scattered throughout the mathematics literature. By presenting a clear exposition of these methods in a single book, the authors have done a great service to the math profession.

The remaining chapters of the book explore how Pell’s equation occurs in cryptography as part of a public key-cryptosystem (Chapter 14), how to use the methods developed in the book to find unconditional methods for determining whether an ideal is principal and finding its generator (Chapter 16), and generalizations of Pell’s equation (Chapter 17).

The book is very well-written and filled with many interesting asides. The authors consistently give a historical overview of the subject and how the methods develop. The only disappointment I had reading the book was the comparatively small set of examples. As one of the book’s stated goals is to provide “a relatively gentle introduction for senior undergraduates,” a much larger set of examples, particularly in the latter, more dense material, would increase the number of students at every level who could profitably read this text. There are also some minor typographical errors in the book (e.g. page xix, first line, definition of ρ).

I highly recommend the book to anyone with an interest in Pell’s equation and its modern study.


Tom Hagedorn is Associate Professor of Mathematics at The College of New Jersey.

 

Preface.- Introduction.- Early History of the Pell Equation.- Continued Fractions.- Quadratic Number Fields.- Ideals and Continued Fractions.- Quadratic Number Fields.- Ideals and Continued Fractions.- Some Special Pell Equations.- The Ideal Class Group.- The Analytic Class Number Formula.- Some Additional Analytic Results.- Some Computational Techniques.- (f, p) Representations of O-ideals.- Compact Representations.- The Subexponential Method.- Applications to Cryptography.- Unconditional Verification of the Regulator and the Class Number.- Principal Ideal Testing in O.- Conclusion.- Appendix.- References.- Index.