Modular Arithmetic

Modular arithmetic is the branch of arithmetic for integers that deals only with remainders, ignoring how many times one number divides into another. It builds on Euclid's division algorithm from earlier classes: for any dividend $X$ and divisor $Y$ (with $X > Y$, $Y \neq 0$), there exist unique integers $Q$ (the quotient) and $R$ (the remainder) such that

The modulo operator, written $X \bmod Y = R$, isolates just the remainder from this relationship — it tells you what is left over after $X$ is divided by $Y$. For instance, $29 \bmod 3 = 2$, since dividing 29 by 3 leaves a remainder of 2. A familiar everyday model is a 12-hour clock: 13 o'clock is displayed as 1 o'clock because $13 = 12 \times 1 + 1$, i.e., $13 \bmod 12 = 1$. What matters is not how many full cycles occur, only where the count ends up — this "wrap-around" behaviour is the essence of modular arithmetic.

The values $X$, $Y$ and $Q$ may be positive, negative, or zero (except $Y$, which cannot be zero), but the remainder $R$ is always non-negative and strictly less than $|Y|$. Two special cases are worth remembering: when $X = Y$, the remainder is $0$ (e.g., $3 \bmod 3 = 0$); and when $X < Y$, the remainder is simply $X$ itself (e.g., $7 \bmod 13 = 7$).

Properties of the modulo operator

The modulo operator obeys four properties that make large computations manageable:

Property 1 says that adding any whole multiple of the divisor leaves the remainder unchanged. Properties 2-4 let you reduce each part of a sum, difference, or product first and only then combine them - invaluable when the raw numbers are large. For example, to find $(127\times137\times23\times50\times235\times15)\bmod 7$ you replace each factor by its remainder mod $7$ and multiply those small remainders instead.

Addition, subtraction and multiplication modulo $m$

These properties give rise to three closed operations on remainders. For positive integers $a$, $b$ and a modulus $m$:

Each operation first combines $a$ and $b$ in the ordinary way and then keeps only the remainder on division by $m$, so the result always lies in $\{0, 1, \ldots, m-1\}$. When a subtraction turns out negative, the non-negative remainder is still taken - for instance $11 \ominus_7 43 = (11-43)\bmod 7 = -32 \bmod 7 = 3$, since $-32 = 7\times(-5) + 3$.

Where modular arithmetic is used

Because it captures anything that repeats in cycles, modular arithmetic appears far beyond the classroom: ISBN and bank-account (IBAN) numbers use modulo checksums to catch typing errors, calendars use arithmetic modulo $7$ to find the day of the week for any date, and the twelve-tone musical scale rests on arithmetic modulo $12$ - the same "clock" idea that makes five hours after $10$ o'clock read as $3$ o'clock.

Illustration 2. Using $X = 18$ and $Y = 5$ (so that $X \bmod Y = 18 \bmod 5 = 3$), complete Table 2. For each value of $k$, compute $kY$, then $X + kY$, and finally $(X + kY) \bmod Y$.

Since $X + kY = 18 + 5k$, we tabulate:

What the table shows: every entry in the last column equals $3$, which is exactly $X \bmod Y$. This confirms Property 1 — adding any integer multiple $kY$ of the divisor to $X$ leaves the remainder unchanged: $X \bmod Y = (X + kY) \bmod Y$. (For the negative rows note that remainders stay non-negative, e.g. $-2 = 5\times(-1) + 3$, so $-2 \bmod 5 = 3$.)

---

Illustration 3. Complete the table below, where $A$, $B$ and $C$ are positive integers, and verify the addition property $(A + B) \bmod C = (A \bmod C + B \bmod C) \bmod C$. Here $Z = A \bmod C + B \bmod C$.

In every row the fourth column $(A+B)\bmod C$ matches the last column $Z \bmod C$, verifying the addition property.

---

Illustration 4. Complete the table below, where $A$, $B$ and $C$ are positive integers, and verify the subtraction property $(A - B) \bmod C = (A \bmod C - B \bmod C) \bmod C$. Here $Z = A \bmod C - B \bmod C$.