Let's make the previous discussion a bit more rigorous.
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 \begin{equation*}[a]=\{\text{all numbers congruent to }a\text{ modulo }n\}\; .\end{equation*}(Sometimes this is notated \([a]_n\), but the modulus is nearly always evident from the context.)
For instance, the equivalence class we started with is \begin{equation*}[1]=\{1, 7, 13, 19, 25, -5, -11, 6001,\ldots\}\end{equation*} or perhaps better written as \begin{equation*}\{1+6n\mid n\in\mathbb{Z}\}=[1]\; .\end{equation*}
The point is you can choose your favorite number in an equivalence class to serve as a representative for all of them. To connect to before, for the congruence relation, there are only finitely many classes, otherwise the division algorithm would be meaningless. After, all, there are only \(n\) possible remainders.
Let's solve the ‘magic trick’ above using this concept in a slightly different way. \begin{equation*}2^{1000000000}=(2^2)^{500000000}= 4^{500000000}\equiv 1^{500000000}=1\, .\end{equation*}
Here is something which is not a legal manipulation. \begin{equation*}2^{1000000000}\equiv 2^1\equiv 2\, .\end{equation*} Even though \(1000000000\equiv 1\) modulo \(3\), clearly the end result is wrong, because \(2^1\not\equiv 1\) (mod \(3\)), which was the right answer. In general, we have only see you can reduce in the base of a power; nothing is said about the exponent! (Later 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. 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. This is just what you think it is; for \(n=6\), it 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.
The problem is that they get big! To calculate \(4^{20}\) (mod \(6\)), I need to reduce a lot, e.g. \begin{equation*}4^{20}\equiv (4^2)^{10}\equiv 16^{10}\equiv 4^{10}\equiv (4^2)^5\equiv 16^5\equiv 4^5\equiv (4^2)^2\cdot 4\equiv 4^2\cdot 4\equiv 4\cdot 4\equiv 4\end{equation*} It's at least a little easier on the ol' noggin to mostly use \(4\equiv -2\) (mod \(6\)) like this: \begin{equation*}4^{20}\equiv (-2)^{20}\equiv ((-2)^2)^{10}\equiv 4^{10}\equiv (-2)^{10}\equiv ((-2)^2)^5\equiv 4^5\end{equation*}\begin{equation*}\equiv (-2)^5\equiv ((-2)^2)^2\cdot (-2)\equiv 4^2\cdot (-2)\equiv (-2)^3\equiv -8\equiv 4\, .\end{equation*} Notice in the second one I never broke single digits! So we sometimes use the set of least absolute residues, the collection of representatives of each class which are closest to zero. In this case the least absolute residues are \(\{-2,-1,0,1,2,3\}\) for \(\{[4],[5],[0],[1],[2],[3]\}\).
