The Ring of Integers Modulo $n$

This chapter is about the ring $\mathbb{Z}/n\mathbb{Z}{}$ of integers modulo $n$ . First we discuss when linear equations modulo $n$ have a solution, then introduce the Euler $\varphi$ 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 $n$ , including computing large powers quickly, and solving linear equations. We finish with a very brief discussion of finding prime numbers using arithmetic modulo $n$ .