Skip to main content

Chapter 4 Congruences

For this section, it is helpful if you keep "clock arithmetic" in mind. That is \(14:00\) hours is \(2\) o'clock. This will be considered doing arithmetic modulo \(12.\) We will just consider an \(n\) hour clock.

Definition 4.0.1.

Let \(n\in\mathbb{N}.\) Two integers \(a\) and \(b\) are said to be congruent modulo \(n,\) written

\begin{equation*} a \equiv b\pmod{n}, \end{equation*}

provided \(n\vert (a-b).\)

The canonical example of a congruence comes from the division algorithm.

Let \(a\in\mathbb{Z}\) and \(n\in\mathbb{N}.\) Given the division algorithm we know that there exists unique \(q, r\in\mathbb{Z}\) with \(0\leq r\lt n,\) such that

\begin{equation*} a = qn + r. \end{equation*}

The definition of congruence gives

\begin{equation*} a \equiv r\pmod{n}. \end{equation*}

Definition 4.0.3.

If \(a, b\in\mathbb{Z}\) and \(a\equiv b\pmod{n}\) we say that \(a\) is a residue of \(b\) modulo \(n.\)

Remark 4.0.4.

The above examples tells us that modulo \(n\) any integer \(a\) is congruent to one of

\begin{equation*} 0, 1, 2,...,n-1. \end{equation*}

These integers are called the least nonnegative residues modulo \(n\).

Definition 4.0.5.

The set of integers \(\{a_0, a_1,..., a_n-1\}\) is called a complete residue system modulo \(n\) provided

  1. \(a_i \not\equiv a_j\pmod{n},\) whenever \(i\neq j\)

  2. for each integer \(k\) there corresponds an \(a_i\) such that \(k\equiv a_i\pmod{n}.\)

This is a direct consequence of the Division Algorithm.

Let \(a, b\in\mathbb{Z}.\) Suppose \(a \equiv b\pmod{n}.\) Then by definition \(n\vert (a-b).\) Now by the Division Algorithm there are \(q, q', r, r'\in\mathbb{Z}\) with \(>0\leq r, r' \lt n\) so that \(a = qn + r\) and \(b = q'n + r'.\) Now \(n\vert (n(q-q')+(r-r')),\) which says that \(n\vert (r-r').\) Since both \(r, r'\lt n\) this gives \(r-r'=0,\) so that \(r=r'.\)

Suppose that \(a\) and \(b\) have the same nonnegative remainder when divided by \(n,\) say \(r.\) So

\begin{equation*} a-b = qn + r-(q'n + r) = (q-q')n, \end{equation*}

which gives \(n\vert(a-b)\) and so \(a\equiv b\pmod{n}.\)

Let \(n\in\mathbb{N}\) and \(a, b\in\mathbb{Z}.\) Now for \((i)\) we simply note that \(n\vert 0\) so that \(n\vert (a-a)\) and \(a \equiv a\pmod{n}.\) For \((ii),\) if \(a \equiv b\pmod{n},\) then \(n\vert (a-b)\) so that there is a \(k\in\mathbb{Z}\) such that \(kn = (a-b).\) Thus \((-k)n = (b-a),\) so \(n\vert (b-a)\) and we have that \(b \equiv a\pmod{n}.\) For \((iii),\) if \(a \equiv b\pmod{n}\) and \(b \equiv c\pmod{n},\) we have that \(n\vert (a-b)\) and \(n\vert (b-c)\) so that \(n\vert[(a-b)+(b-c)]\) which gives \(n\vert (a-c).\) Thus \(a \equiv c\pmod{n}.\)

Definition 4.0.9.

If a relation has the properties that it is reflexive, symmetric, and transitive, then we call it an equivalence relation.

Thus "\(\equiv\)" to the modulus \(n\) is an equivalence relation, as seen in the previous theorem.

Note that \((ii)\) and \((iii)\) are special cases of \((i),\) so that we will only prove \((i).\) Thus let \(n\in\mathbb{N}\) and \(a, b, c, d \in\mathbb{Z}.\) By a previous theorem we know that both \(a\) and \(b\) have the same remainder when divided by \(n,\) say \(r,\) and \(c\) and \(d\) have the same remainder when divided by \(n,\) say \(r'.\) So there exist \(q, s, q', s'\in\mathbb{Z}\) so that

\begin{align*} a \amp =qn+r\\ b \amp =sn+r\\ c \amp =q'n+r'\\ d \amp =s'n+r' \end{align*}

Using this we have that

\begin{align*} a+c \amp =qn+r+q'n+r'\\ \amp =(q+q')n+(r+r')\\ \amp \equiv(r+r')\pmod{n}\\ \amp \equiv(s+s')n+(r+r')\pmod{n}\\ \amp \equiv(sn+r)+(s'n+r')\pmod{n} \end{align*}

so that \(a + c \equiv b + d\pmod{n}.\) Also we have

\begin{align*} ac \amp =(qn+r)(q'n+r')\\ \amp =qq'n^2+(rq'+r'q)n+rr'\\ \amp \equiv rr'\pmod{n}\\ \amp \equiv ss'n^2+(rs'+r's)n+rr'\pmod{n}\\ \amp \equiv(sn+r)(s'n+r')\pmod{n}\\ \amp \equiv bd \pmod{n} \end{align*}

so that \(ac \equiv bd\pmod{n}.\)

Remark 4.0.11.

The arithmetic, "\(+, -, \cdot\)" with congruences is the same as the arithmetic "\(+, -, \cdot\)" in integers. But here we are only interested in remainders.

We have

\begin{align*} 19 \amp \equiv 11\pmod{4}\\ 6 \amp \equiv 2\pmod{4}\\ 13\amp\equiv 19-6\equiv 11-2\equiv 9\pmod{4}\\ 114\amp\equiv 19\cdot 6\equiv 11\cdot 2\equiv 22 \equiv 2\pmod{4}. \end{align*}

Definition 4.0.13.

The set \(\mathbb{Z}_n := \{0, 1, 2,..., n-1\}\) equipped with addition and multiplication modulo \(n\) is called the ring of integers modulo \(n.\)

Note that every element in \(a\in\mathbb{Z}_n\) has an additive inverse (there is an element \(b\) such that \(a + b \equiv 0\pmod{n}),\) but not every element has a multiplicative inverse (an element \(b\) such that \(ab\equiv 1\pmod{n}\)). As an example let \(n = 10\) and \(a = 2.\) Then the additive inverse of \(5\) is \(5\) since

\begin{equation*} 5 + 5 \equiv 0\pmod{10}. \end{equation*}

But \(5\) does not have a multiplicative inverse. This can be seen just by exhausting the possibilities.

\begin{align*} 5(0) \amp\equiv 0\pmod{10}\\ 5(1) \amp\equiv 5\pmod{10}\\ 5(2) \amp\equiv 0\pmod{10}\\ 5(3) \amp\equiv 5\pmod{10}\\ 5(4) \amp\equiv 0\pmod{10}\\ 5(5) \amp\equiv 5\pmod{10}\\ 5(6) \amp\equiv 0\pmod{10}\\ 5(7) \amp\equiv 5\pmod{10}\\ 5(8) \amp\equiv 0\pmod{10}\\ 5(9) \amp\equiv 5\pmod{10} \end{align*}

A consequence of this is that part \((ii)\) of the preceding theorem is not an "if and only if" statement. The first part of the statement does have a true converse. We see this in the following theorem.

Let \(n\in\mathbb{N}\) and \(a, b, c\in\mathbb{Z}.\) Suppose \(a + c \equiv b + c\pmod{n}.\) Now we know that \(-c \equiv -c\pmod{n}\) by the reflexive property. Thus we have

\begin{equation*} (a + c) + (-c) \equiv (b + c) + (-c) \pmod{n}, \end{equation*}

and so \(a \equiv b \pmod{n}.\)

There is a kind of limited converse for the second part of the statement. First we need to see when \(a\) has an inverse in \(\mathbb{Z}_n.\) This is the same as asking if the linear equivalence

\begin{equation*} ax \equiv 1 \pmod{n} \end{equation*}

has a solution. This is the same as asking if there are \(x\) and \(y\) such that

\begin{equation*} ax + ny = 1 \end{equation*}

has a solution \(x, y,\) and this is true if and only if \(\gcd(a, n) = 1.\) This yields the following theorem.

Let \(n\in\mathbb{N},\) \(a,b,c\in\mathbb{Z}\) and \(\gcd(c,n)=1.\) Suppose \(ac\equiv bc\pmod{n},\) then

\begin{gather*} n\vert(ac-bc)\\ n\vert c(a-b)\\ n\vert(a-b), \end{gather*}

where the last line comes by Euclid's lemma. Thus \(a \equiv b\pmod{n}.\)