Modular Arithmetic

Clocks, calendars, and cryptographic keys all run on the same arithmetic. The idea is simple: when you reach the top, you wrap around.

The basic idea

Fix a positive integer $n$ called the modulus. Two integers $a$ and $b$ are congruent modulo $n$, written

$a \equiv b \pmod{n}$

if their difference $a - b$ is divisible by $n$. Equivalently, $a$ and $b$ have the same remainder when divided by $n$.

Examples:

• $17 \equiv 2 \pmod{5}$, because $17 - 2 = 15 = 3 \times 5$.
• $-3 \equiv 4 \pmod{7}$, because $-3 - 4 = -7 = (-1) \times 7$.
• $100 \equiv 0 \pmod{10}$, because $100$ is divisible by $10$.

The notation $a \bmod n$ (without the $\equiv$) denotes the remainder: a number in $\{0, 1, \ldots, n-1\}$. So $17 \bmod 5 = 2$.

Clock arithmetic

The familiar 12-hour clock is modular arithmetic with $n = 12$. At 11 o’clock, one hour later is not the 12th hour on an infinite number line — it wraps to 12, and after another hour, to 1. The arithmetic rule is:

$(\text{current hour} + \text{hours elapsed}) \bmod 12$

(with the convention that $0$ is displayed as $12$).

How computation works

Congruence behaves well under addition, subtraction, and multiplication:

$\text{If } a \equiv a' \pmod{n} \text{ and } b \equiv b' \pmod{n}, \text{ then:}$

$a + b \equiv a' + b' \pmod{n}$ $a - b \equiv a' - b' \pmod{n}$ $a \cdot b \equiv a' \cdot b' \pmod{n}$

This means you can reduce intermediate results at each step, which is critical for efficient computation with very large numbers.

Modular arithmetic and groups

The set $\mathbb{Z}/n\mathbb{Z} = \{0, 1, 2, \ldots, n-1\}$ under addition modulo $n$ is a group. This connects modular arithmetic directly to abstract algebra.

For multiplication, the story is more selective: the set of integers relatively prime to $n$, written $(\mathbb{Z}/n\mathbb{Z})^\times$, forms a group under multiplication modulo $n$. Its order (size) is given by Euler’s totient function $\phi(n)$.

For example, $(\mathbb{Z}/7\mathbb{Z})^\times = \{1,2,3,4,5,6\}$ has order $\phi(7) = 6$, and by Fermat’s little theorem, $a^6 \equiv 1 \pmod{7}$ for any $a$ not divisible by $7$.

Inverses modulo $n$

When does $a$ have a multiplicative inverse mod $n$? Exactly when $\gcd(a, n) = 1$. In that case, there exists $b$ such that $ab \equiv 1 \pmod{n}$.

Example: Find the inverse of $3$ modulo $7$.
We need $3b \equiv 1 \pmod 7$. Testing: $3 \times 5 = 15 = 2 \times 7 + 1 \equiv 1 \pmod 7$. So $3^{-1} \equiv 5 \pmod 7$.
In general, this is computed efficiently using the extended Euclidean algorithm.