NTIC Equivalence classes

Section 4.4 Equivalence classes

Let's make the previous discussion a bit more rigorous by formally breaking up

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

We call any number congruent to $a$ a residue of $a .$
We call the collection of all residues of $a$ the equivalence class of $a .$
We denote this class by the notation

$[a] = {all numbers congruent to a modulo n}$

(Sometimes this is notated $[a]_{n},$ 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,$ which is the set

[1] = {1, 7, 13, 19, 25, - 5, - 11, 6001, \dots}

perhaps better written as

{1 + 6 n ∣ n \in Z} = [1] .

🔗

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

🔗

Fact 4.4.3.

Any set (not just $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,

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,$ we can note that $2 \equiv - 1$ and write

2 \cdot 2 \cdot 2 \cdot 2 \equiv - 1 \cdot - 1 \cdot - 1 \cdot - 1 \equiv 1,

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.

2^{1000000000} = (2^{2})^{500000000} = 4^{500000000} \equiv 1^{500000000} = 1 mod (3) .

🔗

Example 4.4.5.

Here is something which is not a legal manipulation.

2^{1000000000} \equiv 2^{1} \equiv 2 .

Even though $1000000000 \equiv 1$ modulo $3,$ clearly the end result is wrong, because $2^{1} ≢ 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,$ the set of least nonnegative residues is ${0, 1, 2, 3, 4, 5},$ representing the set of equivalence classes ${[0], [1], [2], [3], [4], [5]} .$ They are easy to think of and understand.

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