The Ring of Integers Modulo

This chapter is about the ring of integers modulo . First we discuss when linear equations modulo have a solution, then introduce the Euler function and prove Fermat's Little Theorem and Wilson's theorem. Next we prove the Chinese Remainer Theorem, which addresses simultaneous solubility of several linear equations modulo coprime moduli. With these theoretical foundations in place, in Section 2.3 we introduce algorithms for doing interesting computations modulo , including computing large powers quickly, and solving linear equations. We finish with a very brief discussion of finding prime numbers using arithmetic modulo .

- Congruences Modulo

- The Chinese Remainder Theorem

- Quickly Computing Inverses and Huge Powers

- Primality Testing
- The Structure of

- Exercises

William 2007-06-01