NTIC Linear Congruences

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).