Chapter 5 Linear Congruences
There are many questions one can ask of the integers, and in the preceding material we have already encountered many, especially those asking for solutions of simple equations in one or two variables.
One can ask very similar questions (and many more) about the integers modulo \(n\text{.}\) So we will focus on congruences, which are simply equations modulo \(n\) (see Definition 4.6.3). To exemplify this, consider the following similar ideas:
\(2x+3y=5\) (solutions are pairs of integers)
\(2x+3y\equiv 5\text{ (mod }7)\) (solutions would be pairs of equivalence classes \([x],[y]\) modulo 7)
\(2x+3y\equiv 5\text{ (mod }n)\) for any particular \(n\) (solutions would be triplets \([x],[y],n\text{,}\) since it would depend on \(n\))
Try comparing solutions to these by hand; what is similar about them, what is not?
In one sense the latter problems are a big improvement in the level of difficulty. For instance, in the second one you just have to try \(x,y\) from 0 to 6 (the least nonnegative residues) in the congruence \(2x+3y\equiv 5\) (mod \(7\)).
On the other hand, if the third congruence was modulo \(n=10^{100}\text{,}\) that would be less desirable, especially if the techniques for \(\mathbb{Z}\) proved not to be useful with a congruence.
Finally, if we slapped an \(x^2\) in the middle of the congruence, it might very hard indeed to solve quickly. So in this chapter, we will stay focused on the simplest case, of the analogue to linear equations, known as linear congruences (of one variable). This includes systems of such congruences (see Section 5.3).
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.