Modular Arithmetic in Computer Science

If it is 9 o'clock now, what time will it be in 50 hours? You do not count 59; you wrap around the clock. That wrapping idea is modular arithmetic, sometimes called clock arithmetic, and it quietly powers a huge amount of computer science, from hash tables and random number generators to check digits and the encryption that protects online banking.

The Basic Idea

For integers \(a\) and a positive integer \(n\), \(a \bmod n\) is the remainder when \(a\) is divided by \(n\). It always lies between 0 and \(n - 1\). For example, \(50 \bmod 12 = 2\) because \(50 = 4 \times 12 + 2\). So 50 hours after 9 o'clock, the clock shows \(9 + 2 = 11\).

We say \(a\) is congruent to \(b\) modulo \(n\), written

$$ a \equiv b \pmod{n} $$

when \(n\) divides \(a - b\); equivalently, \(a\) and \(b\) leave the same remainder. So \(38 \equiv 2 \pmod{12}\) and \(-1 \equiv 11 \pmod{12}\).

Note that in many programming languages the % operator can return a negative result for negative numbers (in C and Java, -7 % 3 gives -1), while mathematicians and Python give 2. Programmers often write ((a % n) + n) % n to be safe.

Rules That Make It Powerful

If \(a \equiv b\) and \(c \equiv d \pmod{n}\), then

$$ a + c \equiv b + d, \qquad a - c \equiv b - d, \qquad ac \equiv bd \pmod{n} $$

In practice this means you can reduce at every step. You never need to compute a giant number and then take the remainder; you take remainders as you go and the answer is the same. This is exactly why computers can handle numbers hundreds of digits long in cryptography without running out of memory.

Division is the one operation that needs care, and we will deal with it using modular inverses below.

Everyday Computing Examples

• Wrapping indices: in a circular buffer of size 8, the position after index 7 is \((7 + 1) \bmod 8 = 0\).
• Days of the week: if today is Monday, then 100 days later is \(100 \bmod 7 = 2\) days on, so Wednesday.
• Even and odd: \(x \bmod 2\) tells you whether \(x\) is even. For powers of two, \(x \bmod 2^k\) is simply the last \(k\) bits of \(x\), which hardware computes instantly.
• Integer overflow: a 32-bit unsigned integer automatically works modulo \(2^{32}\), so adding 1 to 4,294,967,295 gives 0.
• Hash tables: a key is stored at position \(h(k) = k \bmod m\) in a table of size \(m\).

Worked Example 1: Last Digit of a Huge Power

Find the last digit of \(7^{222}\), that is, \(7^{222} \bmod 10\).

Step 1: Compute small powers modulo 10.

$$ 7^1 \equiv 7, \quad 7^2 = 49 \equiv 9, \quad 7^3 \equiv 9 \times 7 = 63 \equiv 3, \quad 7^4 \equiv 3 \times 7 = 21 \equiv 1 \pmod{10} $$

Step 2: The powers repeat with period 4 because \(7^4 \equiv 1\). Divide the exponent: \(222 = 4 \times 55 + 2\).

Step 3: Use the power rules.

$$ 7^{222} = (7^4)^{55} \cdot 7^2 \equiv 1^{55} \cdot 49 \equiv 9 \pmod{10} $$

The last digit of \(7^{222}\), a number with 188 digits, is 9.

Worked Example 2: Fast Modular Exponentiation

Cryptography needs things like \(a^e \bmod n\) where \(e\) has hundreds of digits. Multiplying \(a\) by itself \(e\) times is impossible, so computers use square-and-multiply: write the exponent in binary and repeatedly square.

Compute \(3^{45} \bmod 7\).

Step 1: Write 45 in binary: \(45 = 32 + 8 + 4 + 1 = 101101_2\).

Step 2: Square repeatedly, reducing mod 7 each time.

• \(3^1 \equiv 3\)
• \(3^2 = 9 \equiv 2\)
• \(3^4 \equiv 2^2 = 4\)
• \(3^8 \equiv 4^2 = 16 \equiv 2\)
• \(3^{16} \equiv 2^2 = 4\)
• \(3^{32} \equiv 4^2 = 16 \equiv 2\)

Step 3: Multiply the powers needed for \(32 + 8 + 4 + 1\).

$$ 3^{45} \equiv 3^{32} \cdot 3^{8} \cdot 3^{4} \cdot 3^{1} \equiv 2 \cdot 2 \cdot 4 \cdot 3 = 48 \equiv 6 \pmod 7 $$

Check with Fermat's little theorem: since 7 is prime, \(3^6 \equiv 1 \pmod 7\). Then \(45 = 6 \times 7 + 3\), so \(3^{45} \equiv 3^3 = 27 \equiv 6 \pmod 7\). Both methods agree. Square-and-multiply needs only about \(2 \log_2 e\) multiplications, so even a 2048-bit exponent takes a few thousand steps instead of an astronomical number.

Worked Example 3: Finding a Modular Inverse

The inverse of \(a\) modulo \(n\) is a number \(x\) with \(ax \equiv 1 \pmod n\). It exists exactly when \(\gcd(a, n) = 1\). We find it with the extended Euclidean algorithm.

Find the inverse of 17 modulo 43.

Step 1: Run Euclid's algorithm.

$$ 43 = 2 \times 17 + 9 $$

$$ 17 = 1 \times 9 + 8 $$

$$ 9 = 1 \times 8 + 1 $$

The last non-zero remainder is 1, so \(\gcd(17, 43) = 1\) and an inverse exists.

Step 2: Work backwards, expressing 1 in terms of 43 and 17.

$$ 1 = 9 - 8 = 9 - (17 - 9) = 2 \times 9 - 17 $$

$$ 1 = 2(43 - 2 \times 17) - 17 = 2 \times 43 - 5 \times 17 $$

Step 3: Reduce modulo 43. The term \(2 \times 43\) vanishes, so \(-5 \times 17 \equiv 1\). The inverse is \(-5 \equiv 38 \pmod{43}\).

Check: \(17 \times 38 = 646 = 15 \times 43 + 1\), so \(17 \times 38 \equiv 1 \pmod{43}\). Correct.

Modular inverses let us "divide" in modular arithmetic, and they are the heart of computing the private key in RSA encryption.

Check Digits: Catching Typing Errors

The ISBN-10 system for books uses modulo 11. For digits \(d_1 d_2 \dots d_{10}\), a valid ISBN satisfies

$$ \sum_{i=1}^{10} i \cdot d_i \equiv 0 \pmod{11} $$

Because 11 is prime, this catches every single wrong digit and every swap of two adjacent digits. The check digit can be 10, written as X. Similar modular checks protect bank card numbers (the Luhn algorithm, modulo 10) and barcodes.

Did You Know?

• Carl Friedrich Gauss introduced the congruence notation \(\equiv\) in his book Disquisitiones Arithmeticae, published in 1801 when he was 24.
• Many pseudo-random number generators use the rule \(x_{k+1} = (a x_k + c) \bmod m\), called a linear congruential generator.
• Euclid's algorithm, described around 300 BC, is still among the oldest algorithms in everyday use.

Key Takeaways

• \(a \bmod n\) is the remainder after division, and \(a \equiv b \pmod n\) means \(n\) divides \(a - b\).
• Addition, subtraction and multiplication can be reduced at every step, keeping numbers small.
• Square-and-multiply computes huge modular powers in about \(\log_2 e\) steps.
• The extended Euclidean algorithm finds modular inverses when \(\gcd(a, n) = 1\).
• Modular arithmetic underpins hashing, check digits, random numbers and cryptography.

For step-by-step solutions to number theory, discrete maths or programming assignments, reach Amathify's experts and PhD scholars through WhatsApp or the Ask a Question form.