Modular arithmetic — the clock

What just happened?

The hand moved $a$ steps around a dial with $n$ positions. Each time it reaches the end it returns to the start — only where it finally stops matters. That position is the remainder of the division.

Definition — the modular remainder:

We say that $a \equiv r \pmod{n}$ (“a is congruent to r modulo n”) when $a$ and $r$ give the same remainder when divided by $n$. In short: they differ by a multiple of $n$.

The clock analogy:

A 12-hour clock counts modulo 12. 15:00 is $15 \bmod 12 = 3$, i.e. 3:00 in the afternoon — one full lap of the dial plus 3 hours. Likewise $27 \bmod 12 = 3$ (two laps and 3).

Why is this used in cryptography?

The Caesar cipher shifts letters modulo 26 (the alphabet “wraps” from Z to A). RSA and the Diffie–Hellman key exchange rely on exponentiation modulo a large number — operations on the circle of remainders are reversible only for someone who knows the key. Without modular arithmetic there is no modern encryption.

Why you need this for the exam:

Problems with remainders, divisibility and periodicity (e.g. “what day of the week in 100 days”, the last digit of a power) you solve with one trick: compute $a \bmod n$. Write down $n$, compute the remainder — the remainder governs the whole cycle.

Remember: $a \bmod n$ is the remainder of a division — a number on a circle of $n$ positions, where $0 \le r < n$. It is the foundation of cryptography.