Primality testing for beginners, by Lasse Rempe-Gillen and Rebecca Waldecker.

Visit the official website of the book.

Summary


In 2002, Agrawal, Kayal and Saxena announced the stunning result that there is a deterministic polynomial-time algorithm to test whether a number is prime. Their proof (“Primes is in P”, Annals of Mathematics 160 (2004), 781-793) amazingly requires nothing beyond a Chebyshev-type inequality on the prime number function and some facts from undergraduate commutative algebra.

The goal of our book – an English adaptation of our German version from 2009 – is to completely present this contemporary mathematical result without requiring any background beyond basic arithmetic and an aptitude for logical thought. We try to carefully develop the required background in elementary number theory (starting with the induction principle) and the theory of computation before presenting a complete and rigorous proof of the AKS theorem.

As such, the book is intended to be accessible to good beginning mathematics undergraduates and motivated high-school students.

Errata


p. 133, l. 6. In the reminder of the statement of the Fermat-Euler theorem, "a" should be replaced by "1". (We thank Dierk Schleicher for pointing this out.)