Number Theory: In Context and Interactive

Summary: First Steps with Congruence

1. 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.
2. 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.
3. 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{.}\)
4. 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.
5. 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.
6. 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).