Section5.4Equivalence classes

It's time for some definitions. Assume we have fixed a modulus \(n\).

  • I call a number congruent to \(a\) a residue of \(a\).
  • I call the collection of all residues of \(a\) the equivalence class of \(a\).
  • We denote this class by the notation \[[a]=\{\text{all numbers congruent to }a\text{ modulo }n\}\; .\]

So, for instance, the equivalence class we started with is \[[1]=\{1, 7, 13, 19, 25, -5, -11, 6001,\ldots\}\] or perhaps better written as \[\{1+6n\mid n\in\mathbb{Z}\}=[1]\; .\]

The point is you can choose your favorite number in an equivalence class to serve as a representative for all of them. For the congruence relation, there are only finitely many classes, otherwise the division algorithm would be meaningless - there are only \(n\) possible remainders!

Here is another way to solve the above problem using this concept. \[2^{1000000000}=(2^2)^{500000000}= 4^{500000000}\equiv 1^{500000000}=1\, .\]

Here is something which would not have been legal. \[2^{1000000000}\equiv 2^1\equiv 2\, .\] Even though \(1000000000\equiv 1\) modulo \(3\), clearly it is wrong, because \(2^1\not\equiv 1\) mod (\(3\))! In general, you can only reduce in the base of a power, not the exponent. (Later we'll see how to do reduction in the exponent under controlled circumstances - with a different modulus.

Subsection5.4.1Residue Systems

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

Subsection5.4.2Taking powers

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!
You might want to try it to see you get the same thing.

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