You are here

Higher Arithmetic: An Algorithmic Introduction to Number Theory

Harold M. Edwards
American Mathematical Society
Publication Date: 
Number of Pages: 
Student Mathematical Library 45
[Reviewed by
Luiz Henrique de Figueiredo
, on

Despite sharing a title with a classic book by Davenport, this book is different in spirit, as suggested by the word "algorithmic". Actually, the "algorithmic" part of the title is a bit misleading: while the book does contain several algorithms in pseudo-code, it does not discuss complexity at all — no analysis is done of the running time of those algorithms. For that and more, I recommend the excellent book by Bach and Shallit.

What Edwards really means by "algorithmic" is that all problems are solved by an explicit construction that can be performed in a finite number of steps. There are no existence theorems per se, only explicit constructions. And in this the book succeeds very well.

The book has 31 short chapters, each followed by a short list of exercises and computations. Solutions for the exercises are provided at the end of the book. The first half of the book contains the usual material of introductory number theory: congruences, the Euclidean algorithm, the fundamental theorem of arithmetic, Euler's φ-function, primitive roots, primality testing, and RSA cryptography. The pace in this part is brisk, with no distractions.

The second half of the book concentrates on the solution of the Diophantine equation Ax2 + B = y2. This solution culminates with the quadratic reciprocity law and is based on what is essentially the ideal theory of the field Q(√A), which Edwards calls "modules of hypernumbers". Edwards argues that this approach is simpler than Gauss's theory of composition of binary quadratic forms. This part of the book is an extended version of chapter 3 of his Essays in Constructive Mathematics . This is unusual material, or at least it is presented in an unusual fashion, and the pace slows, which is a good thing.

Edwards' book is not the usual introduction to number theory, which is refreshing. It is well placed in the AMS Student Mathematical Library , whose mission is to "spark students' interests in modern mathematics and increase their appreciation for research" and to "motivate students to do mathematics rather than merely learn it". Any student that manages to go through Edwards' book will certainly learn much number theory and a lot on how to do mathematics.


[1] H. Davenport. The higher arithmetic. An introduction to the theory of numbers . Cambridge University Press, 1999. ISBN: 0-521-63446-6

[2] E. Bach and J. Shallit. Algorithmic number theory. Vol. 1. Efficient algorithms . MIT Press, 1996. ISBN: 0-262-02405-5

Luiz Henrique de Figueiredo is a researcher at IMPA in Rio de Janeiro, Brazil. His main interests are numerical methods in computer graphics, but he remains an algebraist at heart. He is also one of the designers of the Lua language.

  • Numbers
  • The problem $A\square + B = \square$
  • Congruences
  • Double congruences and the Euclidean algorithm
  • The augmented Euclidean algorithm
  • Simultaneous congruences
  • The fundamental theorem of arithmetic
  • Exponentiation and orders
  • Euler's $\phi$-function
  • Finding the order of $a\bmod c$
  • Primality testing
  • The RSA cipher system
  • Primitive roots $\bmod\ p$
  • Polynomials
  • Tables of indices $\bmod\ p$
  • Brahmagupta's formula and hypernumbers
  • Modules of hypernumbers
  • A canonical form for modules of hypernumbers
  • Solution of $A\square + B = \square$
  • Proof of the theorem of Chapter 19
  • Euler's remarkable discovery
  • Stable modules
  • Equivalence of modules
  • Signatures of equivalence classes
  • The main theorem
  • Which modules become principal when squared?
  • The possible signatures for certain values of $A$
  • The law of quadratic reciprocity
  • Proof of the Main Theorem
  • The theory of binary quadratic forms
  • Composition of binary quadratic forms
  • Cycles of stable modules
  • Answers to exercises
  • Bibliography
  • Index