A slideshow of five photos shows the first photo again after the fifth. 8-bit addition also goes from 255 back to 0, and the week goes from Sunday back to Monday. Calculations like these, which come back to the start after the end, are handled with the remainder of a division.
Five hours after 10 o’clock is 3 o’clock, not 15 o’clock. Dividing 15 by 12 goes around once and leaves 3.
The remainder of dividing a by m is a number from 0 to m − 1. Finding this
remainder is called the modulo operation, written a mod m.
15 mod 12 = 3. Python’s % does this calculation.
The modulo operation also tells even from odd: a % 2 is 0 for even numbers and
1 for odd ones. 8 bits have 256 values, so the result of the
8-bit addition a + b is (a + b) mod 256.
If today is Wednesday, what day is it 100 days from now? 100 mod 7 = 2, so we
drop the 14 weeks and add just 2 days: Friday.
Let the quotients of dividing a and b by m be q₁ and q₂, and the remainders r₁ and r₂.
Adding the two gives the following.
A multiple of m only turns the clock a few more laps, so the remainder of a + b is the same as the remainder of r₁ + r₂.
Multiplication, written out, looks like this.
a × b = m × (m × q₁ × q₂ + q₁ × r₂ + q₂ × r₁) + r₁ × r₂
Everything except r₁ × r₂ has m multiplied in, so the remainder of a × b is also the same as the remainder of r₁ × r₂.
So we can take remainders along the way and keep the numbers small. Even a number too big to fit in a register has a remainder we can find.
Exponentiation by squaring splits the exponent into binary to pick the powers it needs, then finds those powers by squaring again and again and multiplies them.
For example, let’s find the remainder of 3100 divided by 7. As we saw, we can keep only the remainder after each multiplication, but multiplying one at a time still takes 99 multiplications.
| Power | Binary | Remainder mod 7 |
|---|---|---|
| 364 | 1 | 4 |
| 332 | 1 | 2 |
| 316 | 0 | 4 |
| 38 | 0 | 2 |
| 34 | 1 | 4 |
| 32 | 0 | 2 |
| 31 | 0 | 3 |
1100100, that is 64 + 32 + 4, and the rows for the 1s are
highlighted.(4 × 2 × 4) mod 7 = 4.With exponentiation by squaring, 6 squarings and 2 multiplications, 8 in all, are enough. Doubling the exponent adds only one row to the table. So even for an exponent hundreds of digits long, as in internet encryption (RSA), a few thousand multiplications find the remainder.
What are the last two digits of 99⁹⁹, 99 multiplied by itself 99 times? Answer with a number.