Summary: Linear Congruences
In this chapter we begin the process of shifting from solving equations as ‘sentences for equality’ to solving congruences as ‘sentences for congruence’. We start with the simplest context, linear congruences.
- In Proposition 5.1.1 and Proposition 5.1.3 we have a full characterization of solutions to the basic linear congruence \(ax\equiv b\) (mod \(n\)).
- To use the previous section in situations where a solution exists, we need Strategies that work for simplifying congruences. The cancellation propositions 5.2.6 and 5.2.7 are key tools.
- It is an ancient question as to how to solve systems of linear congruences, and the Chinese Remainder Theorem is the prime tool for this. We also introduce The Inverse of a Number in this section.
- In the next section we then make this explicit in Algorithm 5.4.1, and practice it. In the future the corollary Proposition 5.4.5 will prove very useful.
- In the last section there are several more advanced topics which we briefly mention to inspire readers, but do not pursue – notably, Qin’s solution for the situation when we have Moduli which are not coprime.
There are once again many Exercises, but it is worth mentioning that this is a chapter where making up your own congruences (or systems of congruences) is a great way to get extra practice.