There are a few issues and ideas we didn’t get a chance to touch on during today’s lecture. Let’s take a brief look at some of them here.

Modular Exponentiation

Today in class we saw an example in which we computed $5^{110}\pmod{131}$ using repeated squaring. However, there was nothing inherently special about our choice to use repeated squaring. We could have computed this in a variety of different ways. Let’s take a look at some other options and compare the advantages and disadvantages of each. Let’s start with an example involving much smaller numbers, say by computing $5^8\pmod{7}$.

The Direct Approach

We could start with the direct approach, simply computing $5^8$ and then dividing by 7. One computes $5^8=390625$, and dividing that by 7 gives $5^8 = 55803\cdot 7+4$. So we can conclude that $5^8\equiv 4\pmod{7}$.

This approach worked well here, where the number under consideration wasn’t too large, but it wouldn’t have been quite so easy in the case of $5^{110}$. The number $5^{110}$ can be computed (e.g., using WolframAlpha), but it’s a number with 77 decimal digits! If we are only interested in finding the remainder of $5^{110}$ upon division by 131, working with a 77-digit number is perhaps not the most efficient use of resources.

The Divide-and-Conquer Approach

An alternative option is to divide the process of computing the exponential into smaller steps. For example, to compute $5^8\pmod{7}$ we could first compute $5^4\pmod{7}$, and then square the answer. One computes $5^4 = 625 = 89\cdot 7+2$, and so $5^4 \equiv 2\pmod{7}$. We can then compute $5^8\equiv (5^4)^2\equiv (2)^2\equiv 4\pmod{7}$. This approach took a few additional steps to compute (compared with the direct approach), but it had the advantage of greatly decreasing the size of the numbers we needed to work with. That is, rather than having to deal with  $5^8=390625$ we only had to deal with $5^4=625$, which we were then able to replace with its remainder mod 7.

This is the essence behind many of the “tricks” used in modular arithmetic to speed calculations. If you break down a calculation into many smaller steps, then after each step you can replace numbers with their remainders, which helps keep the numerics from getting out of hand. In the case of exponentiation, this means breaking up the exponent into smaller pieces and separately computing the base raised to those powers. How you break up the exponent is entirely up to you.

For example, you could calculate $5^8\pmod{7}$ as follows:
5^8\equiv 5^{3\cdot 2+2}\equiv (5^3)^2\cdot 5^2\equiv (125)^2\cdot 25\equiv 6^2\cdot 4\equiv 36\cdot 4\equiv 1\cdot 4\equiv 4\pmod{7}.
\] Note that at the fourth step we used the equivalence $125\equiv 6\pmod{7}$ to simplify the expression. We could have been even sneakier, and used the equivalence $125\equiv -1\pmod{7}$ to make the subsequent calculations even more simple.

We can take this same approach with $5^{110}\pmod{131}$. For example, we could make the following computation:
5^{110}&\equiv 5^{10\cdot 11}\equiv (5^{10})^{11}\equiv ((5^2)^5)^{11}\equiv ((25)^5)^{11}\pmod{131}\\
&\equiv (9765625)^{11}\equiv (99)^{11}\equiv 8953382542587164451099\pmod{131}\\
&\equiv 60\pmod{131}.
The numbers might look pretty big, but the largest number in the above calculation is “only” 22 digits long. That’s a big improvement over the direct approach, which required a 77-digit number. Here you can see the trade-off: number of steps versus size of numbers involved. If you want to stick to small numbers, you’ll need to break the calculation up into many steps.

The Successive-Squaring Approach

One systematic method to approach all modular exponentiation calculations is to break up the exponent according to powers of two, i.e., to look at the binary expansion of the exponent. For our small example, we are trying to compute $5^8\pmod{7}$, so this would mean rewriting the exponent as $8=2^3$. That is, we would make the computation
5^8\equiv 5^{2^3}\equiv ((5^2)^2)^2\equiv ((25)^2)^2\equiv ((4)^2)^2\equiv (16)^2\equiv 2^2\equiv 4\pmod{7}.
\] Note that we could have made this calculation a bit easier to follow if we simply constructed a list of the successive squares of 5 modulo 7:
5^2&\equiv 25\equiv 4\pmod{7}\\
5^4&\equiv (5^2)^2\equiv 4^2\equiv 16\equiv 2\pmod{7}\\
5^8&\equiv (5^4)^2\equiv 2^2\equiv 4\pmod{7}.
Each time we are using the reduced form of the previous square to help us compute the next square. Notice how breaking up the computation into many smaller steps, and reducing modulo 7 whenever we can, keeps the numerics from getting out of control.

In class, this is the procedure we used to compute $5^{110}\pmod{131}$. We first found the binary representation of 110, namely $110=64+32+8+4+2$, and we then computed the first six successive squares of 5 modulo 131:
5^2&\equiv 25\pmod{131}\\
5^4&\equiv (5^2)^2\equiv (25)^2\equiv 101\pmod{131}\\
5^8&\equiv (5^4)^2\equiv (101)^2\equiv 114\pmod{131}\\
5^{16}&\equiv (5^8)^2\equiv (114)^2\equiv 27\pmod{131}\\
5^{32}&\equiv (5^{16})^2\equiv (27)^2\equiv 74\pmod{131}\\
5^{64}&\equiv (5^{32})^2\equiv (74)^2\equiv 105\pmod{131}.
We then could compute
5^{110}\equiv 5^{64}\cdot 5^{32}\cdot 5^8\cdot 5^4\cdot 5^2\equiv (105)(74)(114)(101)(25)\equiv 60\pmod{131}.
\] Even in this last computation, we could have broken it up into several steps. For example, we could have first computed $(105)(74)\equiv 41\pmod{131}$, then multiplied by 114 (and reduced modulo 131), then multiplied by 101 (and reduced modulo 131), and then multiplied by 25 (and reduced modulo 131). At every step, we’re allowed to reduce modulo 131 before proceeding. It’s our choice. If we do, we pay the cost of taking an additional step, but we get the reward of keeping our numbers small.

There was nothing inherently special about our choice to use successive squaring. We could just have easily used successive cubes, or some combination of squares and cubes, or any other combination of powers. The only real reason to stick with successive squaring is that it is methodical and tends to keep the numbers as small as possible.

Divisibility Rules

At some point in your life you probably learned some “tricks” for checking numbers for divisibility. For example, you may have heard that a number is divisible by 3 if (and only if) the sum of its (decimal) digits is divisible by 3. So the number 123 is divisible by 3 (since its digits sum to 1+2+3=6, which is divisible by 3), whereas the number 245 is not (since its digits sum to 2+4+5=11, which is not divisible by 3). These rules can all be easily verified with modular arithmetic.

For example, let’s verify the above rule. Take any integer $N$ and write it in decimal form. Using our notation in class, we would write $N=(a_m a_{m-1}\cdots a_1a_0)_{10}$. This is simply shorthand for the equality
N = a_m 10^m + a_{m-1}10^{m-1}+\cdots +a_1 10+a_0.
\] Since $10\equiv 1\pmod{3}$, looking at the above equation modulo 3 gives the equivalence
N \equiv a_m (1)^m+a_{m-1}(1)^{m-1}+\cdots a_1 (1)+a_0\pmod{3},
\] or simply
N\equiv a_m+a_{m-1}+\cdots +a_1+a_0\pmod{3}.
\] Thus, each integer $N$ has the same remainder modulo 3 as the sum of its decimal digits. It follows that 3 divides $N$ (i.e., $N\equiv 0\pmod{3}$) if and only if 3 divides the sum of the decimal digits of $N$ (i.e., $a_m+\cdots+a_0\equiv 0\pmod{3}$).

Similar computations establish other such rules, such as the fact that 9 divides $N$ iff 9 divides the sum of the decimal digits of $N$, and that 11 divides $N$ iff 11 divides the alternating sum of the decimal digits of $N$. Try checking them yourself!