What we will now embark upon is asking all the same questions (and many more) about the integers modulo \(n\) that we asked about the integers themselves. So we will focus on congruences, which are simply equations modulo \(n\). For example, one could ask for solutions to any of these 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\), since it would depend on \(n\))

If you think about it, these are actually a big improvement in the level of difficulty. After all, 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 congruence was modulo \(n=10^{100}\), that would be less desirable. Or if we had \(x^2\), it might get a lot harder to solve quickly.

In this chapter, we will stay focused on the simplest case, of the analogue to linear equations, known as linear congruences.