Modular Arithmetic

Clock arithmetic — a n keeps only the remainder.

The idea

Modular arithmetic is arithmetic that keeps only remainders. Clocks work this way: five hours after ten o'clock is three o'clock, because $10 + 5 = 15$ and the dial starts over at twelve, so only the remainder $3$ survives.

Fix a positive integer $n$, the modulus. Dividing an integer $a$ by $n$ leaves a remainder, written $a \bmod n$, which is one of $0, 1, \ldots, n-1$. When two integers $a$ and $b$ leave the same remainder — equivalently, when $n$ divides $a - b$ — we write $a \equiv b \pmod{n},$ read as $a$ is congruent to $b$ modulo $n$.

Congruence respects addition and multiplication: if $a \equiv a'$ and $b \equiv b'$, then $a + b \equiv a' + b'$ and $ab \equiv a'b'$. So at any point in a calculation we may replace a number by any other congruent to it, which keeps the numbers small.

Ways to work on it

• Walkthrough. What a n and a b n mean, with addition and multiplication.
• Practice. Reduce and combine with random small moduli.
• Hardest. Compute a^k n for small random values.

Not sure where to start? Take the ten-question placement test.