8.6: Modular Arithmetic

On the first page of his masterpiece on number theory, Disquisitiones Arithmeticae, Gauss introduced the notion of “congruence.” Now, Gauss is another guy who managed to cough up a half-decent idea every now and then, so let’s take a look at this one. Gauss said that \(a\) is congruent to \(b\) modulo \(n\) iff \(n \mid (a - b)\). This is written

\[\nonumber a \equiv b \pmod n.\]

For example:

\[\nonumber 29 \equiv 15 \pmod 7\) because \( 7 \mid (29 - 15)\]

It’s not useful to allow a modulus \(n \leq 1\), and so we will assume from now on that moduli are greater than 1.

There is a close connection between congruences and remainders:

Lemma 8.6.1 (Remainder).

\[\nonumber a \equiv b \pmod n\) iff \(\text{rem}(a, n) = \text{rem}(b, n)\]

Proof. By the Division Theorem 8.1.4, there exist unique pairs of integers \(q_1, r_1\) and \(q_2, r_2\) such that:

\[\begin{aligned} a &= q_1n + r1 \\ b &= q_2n + r2, \end{aligned}\]

where \(r_1, r_2 \in [0..n)\). Subtracting the second equation from the first gives:

\[\nonumber a - b = (q_1 - q_2)n + (r_1 - r_2)\]

where \(r_1 - r_2\) is in the interval \((-n, n)\). Now \(a \equiv b \pmod n\) if and only if \(n\) divides the left side of this equation. This is true if and only if \(n\) divides the right side, which holds if and only if \(r_1 - r_2\) is a multiple of \(n\). But the only multiple of \(n\) in \((-n, n)\) is 0, so \(r_1 - r_2\) must in fact equal 0, that is, when \(r_1 ::= \text{rem}(a, n) = r_2 ::= \text{rem}(b, n). \quad \blacksquare\)

So we can also see that

\[\nonumber 29 \equiv 15 \pmod 7\) because \(\text{rem}(29, 7) = 1 = \text{rem}(15, 7)\]

Notice that even though “(mod 7)” appears on the end, the \(\equiv\) symbol isn’t any more strongly associated with the 15 than with the 29. It would probably be clearer to write \(29 \equiv _{\mod 7} 15\), for example, but the notation with the modulus at the end is firmly entrenched, and we’ll just live with it.

The Remainder Lemma 8.6.1 explains why the congruence relation has properties like an equality relation. In particular, the following properties⁷ follow immediately:

Lemma 8.6.2.

\[\nonumber \begin{array}{r} a \equiv a \pmod n & (\text{reflexivity}) \\ a \equiv b \text{ IFF } b \equiv a \pmod n & (\text{symmetry}) \\ (a \equiv b \text{ AND } b \equiv c) \text{ IMPLIES } a \equiv c \pmod n & (\text{transitivity}) \end{array}\]

We’ll make frequent use of another immediate corollary of the Remainder Lemma 8.6.1:

Corollary 8.6.3.

[\nonumber (a \equiv \text{rem}(a, n) \pmod n\]

Still another way to think about congruence modulo \(n\) is that it defines a partition of the integers into \(n\) sets so that congruent numbers are all in the same set. For example, suppose that we’re working modulo 3. Then we can partition the integers into 3 sets as follows:

\[\nonumber \begin{array}{l} \{\ldots, -6, -3, 0, 3, 6, 9, \ldots\} \\ \{\ldots, -5, -2, 1, 4, 7, 10, \ldots\} \\ \{\ldots, -4, -1, 2, 5, 8, 11, \ldots\} \end{array}\]

according to whether their remainders on division by 3 are 0, 1, or 2. The upshot is that when arithmetic is done modulo \(n\), there are really only \(n\) different kinds of numbers to worry about, because there are only \(n\) possible remainders. In this sense, modular arithmetic is a simplification of ordinary arithmetic.

The next most useful fact about congruences is that they are preserved by addition and multiplication:

Lemma 8.6.4 (Congruence). If \(a \equiv b \pmod n\) and \(c \equiv d \pmod n\), then

\[\begin{align} \label{8.6.1} a + c &\equiv b + d \pmod n, \\ \label{8.6.2} ac \equiv bd \pmod n. \end{align}\]

Proof. Let’s start with \ref{8.6.1}. Since \(a \equiv b \pmod n\), we have by definition that \(n \mid (b - a) = (b + c) - (a + c)\), so

\[\nonumber a + c \equiv b + c \pmod n.\]

Since \(c \equiv d \pmod n\), the same reasoning leads to

\[\nonumber b + c \equiv b + d \pmod n.\]

Now transitivity (Lemma 8.6.2) gives

\[\nonumber a + c \equiv b + d \pmod n.\]

The proof for \ref{8.6.2} is virtually identical, using the fact that if \(n\) divides \(b - a\), then it certainly also divides \((bc - ac) \quad \blacksquare\).

 

⁷Binary relations with these properties are called equivalence relations, see Section 9.10.