Summary: First Steps with Congruence
This chapter introduces the extremely important notion of congruence.
- In Definition 4.1.1 we define
(mod ), and immediately note in Lemma 4.1.2 that it is the same thing as when two numbers have the same remainder. - Before examining more formal properties of congruence, we use Sage to confirm that it is much easier to be Going Modulo First when you try to compute in a congruence.
- We must then show that Congruence is an equivalence relation and that Congruence arithmetic is well-defined, so that we are justified in such computations modulo
- Because any equivalence relation partitions its underlying set, we can talk about the equivalence classes involved here, and about residue systems that are convenient to compute with.
- In the next section, we then see some practicalities:
- The next subsection then shows how to be systematic about this using binary numbers in Algorithm 4.5.8, including several examples. The key is repeated squaring, explained in Fact 4.5.5.
- Finally, in Section 4.6, many questions are raised that should motivate why we would try to explore things that are like equations, but using congruence (recall Definition 4.6.3).