NTIC Why modular arithmetic matters

Section 4.5 Why modular arithmetic matters

This has been fun and all. But why are we creating so much machinery? 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. The reason is that we can reduce problems about the (infinitely many) integers to checking whether things are possible when we look at the (finitely many) cases modulo

$n\text{.}$ For instance, we can prove things like these statements without inequalities, calculus, or graphs:

“The polynomial $x^5-x+2$ has no integer roots”. (See Exercise 9.6.4)
“The curve $x^3=y^2-7$ has no lattice points”. (See Fact 15.3.3.)

🔗

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.

🔗

Subsection 4.5.1 Starting to see further

🔗

In order to accomplish all these goals, we will take some time learning how to do such computations. Here are two generic practical rules for using modular arithmetic.

First off, always first reduce modulo $n\text{,}$ then do your arithmetic (add, multiply, exponentiate). We have seen lots of examples of this.
Secondly, always use the most convenient residue (recall Definition 4.4.6) of a number modulo $n\text{.}$

🔗

Example 4.5.1.

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

xxxxxxxxxx
 
mod(22,23)+mod(21,23)==mod(-3,23)

🔗

Sage note 4.5.2. Checking equality.

Use the double equals sign == to check if two numerical expressions are equal, not just = (which assigns a value to a variable).

🔗

Here is a more involved example, which avoids the big numbers which would otherwise occur to do a computation without assistance.

🔗

Example 4.5.3.

Let's calculate $4^{20}$ (mod $6$ ). First we will use least nonnegative residues; write the justification for each step in the margin if you have a print copy!

$\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*}$

On the other hand, we can avoid using numbers of absolute value bigger than five if we carefully select least absolute residues where appropriate! Recall that $4\equiv -2$ (mod $6$ ):

$\begin{equation*} 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 \end{equation*}$

$\begin{equation*} \equiv ((-2)^2)^2\cdot (-2)\equiv 4^2\cdot (-2)\equiv (-2)^2\cdot (-2)\equiv 4\cdot (-2)\equiv (-2)\cdot (-2)\equiv 4\text{.} \end{equation*}$

🔗

There are a few things to be aware of when doing this, of course. To remind you of a very important such caveat, recall Example 4.4.5; with exponentiation, you can only replace the base with something in the same congruence class. Using the language of Proposition 4.3.2, we say that

$[a]^n$ is well-defined, but there is no guarantee that

$a^{[n]}$ makes any sense.

🔗

Example 4.5.4.

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), \; 7^8 \text{ (mod }5)\text{.} \end{equation*}$

The second pair is quite different from the first pair.

🔗

Subsection 4.5.2 Taking 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.

🔗

Fact 4.5.5.

For any integer $a\text{:}$

$a^{2^1}=a^2$
$a^{2^2}=(a^2)^2$
$a^{2^3}=(a^{2^2})^2$

In general,

$\begin{equation*} a^{2^n}=\left(a^{2^{n-1}}\right)^2 \end{equation*}$

That is to say, each “power of $a$ to a power of 2” is the square of the previous “power of $a$ to the previous power of 2”.

🔗

Proof.

What does $a^{2^n}$ even mean? By definition,

\begin{equation*} 2^n=2^{n-1}\cdot 2 = 2^{n-1}+2^{n-1}\text{,} \end{equation*}

so $a^{2^n}$ is the same as

\begin{equation*} a^{2^{n-1}+2^{n-1}}=a^{2^{n-1}}\cdot a^{2^{n-1}}=\left(a^{2^{n-1}}\right)^2 \end{equation*}

🔗

Example 4.5.6.

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

Compute $x^2$ modulo $n\text{.}$
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}\text{;}$ 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.

🔗

Example 4.5.7.

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\text{.} \end{equation*}$

Then 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*}$

xxxxxxxxxx
 
mod(2,11)^23

🔗

Algorithm 4.5.8.

In general, we can compute $x^k$ modulo $n\text{:}$

Write the exponent $k=\sum_{i=1}^{\ell} k_i 2^i\text{,}$ where each $k_i=0$ or $1\text{.}$ (This is called the binary representation of $k\text{.}$ )
Compute $x^2\text{,}$ $x^4\text{,}$ $x^8\text{,}$ and so forth as above, each time reducing modulo $n\text{.}$
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.

🔗

Remark 4.5.9.

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\text{,}$ as opposed to gigantic ones, when you mod out after each step, so it requires very little memory.