Skip to main content

Section 4.4 Equivalence classes

Let's make the previous discussion a bit more rigorous by formally breaking up \(\mathbb{Z}\) into disjoint subsets; by Proposition 4.3.2 we can pick any element of a subset for computations.

Definition 4.4.1.

Assume throughout that we have fixed a modulus \(n\text{.}\)

  • We call any number congruent to \(a\) a residue of \(a\text{.}\)

  • We call the collection of all residues of \(a\) the equivalence class of \(a\text{.}\)

  • We denote this class by the notation

    \begin{equation*} [a]=\{\text{all numbers congruent to }a\text{ modulo }n\} \end{equation*}

    (Sometimes this is notated \([a]_n\text{,}\) but the modulus is nearly always evident from the context.)

Example 4.4.2.

For instance, the equivalence class we began with in Section 4.1 is of numbers congruent to \(1\) modulo \(6\text{,}\) which is the set

\begin{equation*} [1]=\{1, 7, 13, 19, 25, -5, -11, 6001,\ldots\} \end{equation*}

perhaps better written as

\begin{equation*} \{1+6n\mid n\in\mathbb{Z}\}=[1]\text{.} \end{equation*}

These congruence classes are an example of a more general construction.

We consider this to be background; see any intro-to-proof text.

For the relation of congruence modulo \(n\text{,}\) there are only finitely many classes (since there are only \(n\) possible remainders in the division algorithm), which is particularly convenient. The point is you can choose your favorite number in an equivalence class to serve as a representative for all of them, including for the purposes of basic arithmetic (by Proposition 4.3.2). Let's briefly redo part of Example 4.4.4 from this perspective.

Example 4.4.4.

To compute \(2\cdot 2\cdot 2\cdot 2\) modulo \(3\text{,}\) we can note that \(2\equiv -1\) and write

\begin{equation*} 2\cdot 2\cdot 2\cdot 2\equiv -1\cdot -1\cdot -1\cdot -1\equiv 1\text{,} \end{equation*}

which is that \(16\equiv 1\) (mod \(3\)).

Let's solve the ‘magic trick’ at the beginning of Section 4.2 using this concept in a slightly different way.

\begin{equation*} 2^{1000000000}=(2^2)^{500000000}= 4^{500000000}\equiv 1^{500000000}=1\text{ mod }(3)\text{.} \end{equation*}
Example 4.4.5.

Here is something which is not a legal manipulation.

\begin{equation*} 2^{1000000000}\equiv 2^1\equiv 2\text{.} \end{equation*}

Even though \(1000000000\equiv 1\) modulo \(3\text{,}\) clearly the end result is wrong, because \(2^1\not\equiv 1\) (mod \(3\)), which we have now seen twice.

In general, we have only seen reduction modulo \(n\) in the base of a power; nothing is said about the exponent! (Later, in Section 10.5, we'll see how to do reduction in the exponent under controlled circumstances – with a different modulus, using Euler's Theorem.)

As you saw above, knowing the ‘right’ residue can be very helpful. Because of this, we make two sets of them for general use.

Definition 4.4.6.

We call a set of integers with precisely one for each equivalence class a complete residue system or complete set of residues for a given modulus.

Usually, we just use the ‘normal’ remainders; this is called the set of least nonnegative residues.

Sometimes we use the set of least absolute residues, the collection of representatives of each class which are closest to zero.

Example 4.4.7.

For \(n=6\text{,}\) the set of least nonnegative residues is \(\{0,1,2,3,4,5\}\text{,}\) representing the set of equivalence classes \(\{[0],[1],[2],[3],[4],[5]\}\text{.}\) They are easy to think of and understand.

In the same case the least absolute residues are \(\{-2,-1,0,1,2,3\}\text{,}\) standing in respectively for \(\{[4],[5],[0],[1],[2],[3]\}\text{.}\) We used these residues (for \(n=3\)) in Example 4.4.4.