Modular Arithmetic & Clock Math Cheat Sheet

Key Facts

• The congruence statement $a \equiv b \pmod{n}$ means $a$ and $b$ have the same remainder when divided by $n$.
• $a \equiv b \pmod{n}$ is true exactly when $n$ divides $a-b$, written as $n \mid (a-b)$.
• To reduce a number modulo $n$, divide by $n$ and keep the remainder, so $29 \equiv 5 \pmod{12}$.
• In clock arithmetic, values wrap around after the modulus, so on a $12$-hour clock, $10+5 \equiv 3 \pmod{12}$.
• You can add congruences with the same modulus: if $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $a+c \equiv b+d \pmod{n}$.
• You can multiply congruences with the same modulus: if $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$, then $ac \equiv bd \pmod{n}$.
• A negative number can be reduced by adding the modulus until the result is between $0$ and $n-1$, so $-3 \equiv 9 \pmod{12}$.
• The standard least nonnegative residue modulo $n$ is one of $0,1,2,\ldots,n-1$.

Vocabulary

Modulus

The modulus is the number $n$ that tells how many values are in one complete cycle.

Congruent

Two integers are congruent modulo $n$ if they have the same remainder after division by $n$.

Remainder

The remainder is the amount left after dividing an integer by another integer as evenly as possible.

Residue

A residue is a representative remainder for a congruence class, often chosen from $0$ through $n-1$.

Clock arithmetic

Clock arithmetic is modular arithmetic where numbers wrap around after a fixed cycle such as $12$ or $24$.

Divisibility

Divisibility means one integer divides another with no remainder, written as $a \mid b$.