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{.}\)
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 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.
