yeolyi.comSeongyeol's CS

Modular arithmetic

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.

Clock arithmetic

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.

Number of slots m 12
Slots moved from 0, a 15
01234567891011
15 = 12 × 1 + 31 full lap and 3 more slots.15 mod 12 = 3

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.

Computing with remainders

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

a = m × q₁ + r₁, b = m × q₂ + r₂

Adding the two gives the following.

a + b = m × (q₁ + q₂) + (r₁ + r₂)

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

Days later 10
Then days later 5
MonTueWedThuFriSatSun
(10 + 5) mod 7 = 15 mod 7 = 1(3 + 5) mod 7 = 8 mod 7 = 1

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.

Times multiplied by 3 10
Multiplying straight through310 = 5904959049 mod 7 = 4Holding the biggest number that comes up takes a 16-bit register.
Taking the remainder after each multiplication
3264513264
The biggest number that comes up is 18, so a 5-bit register is enough.

Fast exponentiation

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.

Exponent 100
PowerBinaryRemainder mod 7
36414
33212
31604
3802
3414
3202
3103
3100 = 364 × 332 × 343100 mod 7 = (4 × 2 × 4) mod 7 = 46 squarings and 2 multiplications, 8 in all · 99 one at a time
  1. Each row of the table is the row below it squared, divided by 7, keeping the remainder.
  2. 100 in binary is 1100100, that is 64 + 32 + 4, and the rows for the 1s are highlighted.
  3. The remainder of a product is the remainder of the product of the remainders, so the remainder of 3100 = 364 × 332 × 34 divided by 7 is (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.

Challenge

What are the last two digits of 99⁹⁹, 99 multiplied by itself 99 times? Answer with a number.