Chapter 4 First Steps with Congruence
Our next big goal is a better notion of how to deal with divisibility and remainders, one we are all familiar with. That is the notion of congruence!
We will begin by reviewing that notion, and start asking the kinds of questions that one will be able to ask with this notion.
Summary: First Steps with Congruence
This chapter introduces the extremely important notion of congruence.
In Definition 4.1.1 we define \(a\equiv b\) (mod \(n\)), 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 \(n\text{.}\)
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:
In various examples like 4.5.3 and 4.5.4 it becomes clear how to conveniently compute powers in modular arithmetic (and what you can't do).
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).
As always, there are plenty of computational and theoretical Exercises.