ABSTRACT
This chapter introduces the basic facts about congruences. See the number theory texts [99], [78] and [98] for more about congruences. Gauss introduced congruences in 1801 in [45]. A congruence is a statement about divisibility. It is a notation that simplifies reasoning about divisibility. It suggests proofs by its analogy to equations. Congruences are familiar to us as “clock arithmetic.” Four hours after 10 AM it will be 2 PM. How do we get the 2 from the 10 and the 4? We add four to ten and then subtract 12. We have used a congruence modulo 12.
