Skip to main content
\( \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section4.5Why modular arithmetic matters

Subsection4.5.1Starting to see further

This has been fun and all. But why are we doing all this? There are two reasons.

The first is practical. Simply put, modular arithmetic makes it much easier to solve certain otherwise very difficult problems about integers, because we can check whether things are possible when we look at things just modulo \(n\). For instance, we can prove things like:

  • “The polynomial \(x^3-x+1\) has no integer roots”.

  • “The curve \(x^3=y^2-7\) has no lattice points”.

Most practical of all are the rules for using modular arithmetic.

  • First off, always first reduce modulo \(n\), then do our arithmetic (add, multiply, exponentiate). We have seen lots of examples of this.

  • Secondly, always use whichever residue of a number modulo \(n\) is convenient for our purposes.

    For example, to add \([22]+[21]\) modulo \(23\) it might be smarter to use the residues \(-1\in[22]\) and \(-2\in [21]\). The answer \([-3]\) is of course the same as \([22+21]=[43]=[20]\) modulo \(23\).

Sage note4.5.1Checking equality

We can check if two numerical expressions are equal using ==.

There are a few things to be aware of when doing this, of course. One very important such caveat is that with exponentiation, you can only replace the base with something in the same congruence class. Just to make sure you get this, on your own compare \begin{equation*}2^3\text{ (mod }5), \; 7^3 \text{ (mod }5),\; \text{ and }2^8 \text{ (mod }5)\; .\end{equation*} These are quite different.

Referring to our earlier wording, we can assume \([a]^n\) is well-defined, but there is no guarantee that \(a^{[n]}\) makes any sense.

The second reason for doing modular arithmetic is theoretical. We get a new number system! (See Chapter 8.) It's a number system which has new problems, new solutions, and new things to explore. And that's what we'll be doing from now on.

Subsection4.5.2Taking powers

As one example of how modular arithmetic might matter a bit, let's examine the following algorithm for taking ridiculously high powers of numbers (modulo \(n\)). We first need the following interesting fact.

Proof
Example4.5.3

In this case, it will be easier to do examples before stating the algorithm. To compute \(x^{20}\), first we see that \(16\) is the highest power of \(2\) less than \(20\).

  • Compute \(x^2\) modulo \(n\).

  • Square that for \((x^2)^2=x^{2^2}=x^4\) (modulo \(n\)).

  • Then square twice more for \(x^{2^3}=x^8\) and \(x^{2^4}=x^{16}\); we reduce modulo \(n\) at each point.

Now write \(x^{20}\) as \(x\) to a sum of powers of \(2\); \begin{equation*}x^{20}=x^{16+4}=x^{2^4+2^2}=x^{2^2}\cdot x^{2^4}\end{equation*} Then do this final multiplication modulo \(n\) as well. You might want to try it to see you get the same thing.

Example4.5.4

Now let's get really explicit, and calculate \(2^{23}\) (mod \(11\)). First, \begin{equation*}23=2^4+2^2+2+1\text{, so }2^{23}=2^{2^4}\cdot 2^{2^2}\cdot 2^2\cdot 2\, .\end{equation*} Now let's get the powers of \(2\) needed: \begin{equation*}2^2\equiv 4\text{ (mod }11\text{), }\left(2^2\right)^2=4^2\equiv 5\text{ (mod }11\text{), }\end{equation*}\begin{equation*}\left(2^4\right)^2=5^2\equiv 3\text{ (mod }11\text{), and }\left(2^8\right)^2=3^2\equiv 9\text{ (mod }11\text{)}\end{equation*} So we get, as a computation one can do completely without a calculator, \begin{equation*}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\text{)}\end{equation*}

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, so it requires very little memory.