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 them 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.
• But, the problem is that they get big! To calculate \(4^{20}\) mod (\(6\)), I need to reduce a lot, e.g. \[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\, ;\] it's at least a little easier on the ol' noggin (since \(4\equiv -2\) mod (\(6\))), to do \[4^{20}\equiv (-2)^{20}\equiv ((-2)^2)^{10}\equiv 4^{10}\equiv (-2)^{10}\equiv ((-2)^2)^5\equiv 4^5\equiv (-2)^5\equiv ((-2)^2)^2\cdot (-2)\equiv 4^2\cdot (-2)\equiv (-2)^3\equiv -8\equiv 4\, .\] Notice in the second one I never broke single digits! So we sometimes use the set of least absolute residues, the representative of each class which is closest to zero. In this case the least absolute residues are \(\{-2,-1,0,1,2,3\}\) for \(\{[4],[5],[0],[1],[2],[3]\}\).

It turns out that there is a way to make an algorithm for taking crazy high powers of numbers (modulo \(n\)) out of this. We take advantage of the fact that for any number \(a\):

1. \(a^{2^1}=a^2\)
2. \(a^{2^2}=(a^2)^2\)
3. \(a^{2^3}=(a^{2^2})^2\)
4. and in general \(\cdots\)
5. \(a^{2^n}=(a^{2^{n-1}})^2\).

For instance, to compute \(x^{20}\):

• Compute \(x^2\)
• Square that for \((x^2)^2=x^{2^2}\) (modulo \(n\))
• Then square twice more for \(x^{2^3}\) and \(x^{2^4}\) - reducing modulo \(n\) at each point.
• Now write \[x^{20}=x^{2^4+2^2}=x^{2^2}\cdot x^{2^4}\] and do this final multiplication mod (\(n\)) as well!

I can try that with something more annoying - calculating \(2^{23}\) mod (\(11\)): \[23=2^4+2^2+2+1\text{, so }2^{23}=2^{2^4}\cdot 2^{2^2}\cdot 2^2\cdot 2\, .\] \[\text{ Now }2^2\equiv 4\text{ mod (11), }4^2\equiv 5\text{ mod (11), }5^2\equiv 3\text{ mod (11), and }3^2\equiv 9\text{ mod (11),}\] \[\text{so we get }2^{2^4}\cdot 2^{2^2}\cdot 2^2\cdot 2\equiv 9\cdot 5\cdot 4\cdot 2\equiv 18\cdot 20\equiv 7\cdot 9\equiv 63\equiv -3\equiv 8\text{ mod (11) --all by hand!}\]

In general, we can compute \(x^k\) modulo \(n\):

• Write the exponent \(k=\sum_{i=1}^{\ell} k_i 2^i\), where each \(k_i=0\) or \(1\). (This is called the binary representation of \(k\).)
• Compute \(x^2\), \(x^4\), \(x^8\), and so forth as above, each time reducing modulo \(n\).
• Multiply \(\prod_{i=1}^{\ell} x^{k_i 2^i}\) together as in the examples above. Obviously, if \(k_i=0\) (such as for \(i=3\) in the \(x^{20}\) example) you skip it, as it just contributes one to the product.

(Those interested in efficiency should note that this requires roughly two times the number of binary digits of your number operations, or about \(2\log_2 (n)\) operations, as opposed to normal powers which might require \(n\) operations; in addition, you only deal with numbers at most size \(n^2\), as opposed to gigantic ones, when you mod out after each step.)