NTIC Equivalence classes

🔗

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.

🔗

Fact 4.4.3.

Any set (not just $\mathbb{Z}$ ) that has an equivalence relation on it can be broken up into disjoint subsets called equivalence classes. It can be useful to consider these classes as elements of a set of all such classes. Such a set of subsets is called a partition.

🔗

Proof.

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 4.2, we'll see how to do reduction in the exponent under controlled circumstances – with a different modulus.)

🔗

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.