16.2 Modular Arithmetic

Modular arithmetic is a way of doing arithmetic where numbers “wrap around” after reaching a certain value, called the modulus. In this chapter we focus on the general ideas, notation, and basic techniques that are specific to modular arithmetic. Detailed applications (such as to cryptography) are left to their own chapter.

The idea of working “modulo $n$”

Fix a positive integer $n \ge 2$. In modular arithmetic “modulo $n$”, you treat two integers as the same if they differ by a multiple of $n$.

For example, when working modulo $12$ (as on a 12‑hour clock):

• $14$ and $2$ are treated as the same because $14 - 2 = 12$ is a multiple of $12$.
• $25$ and $1$ are treated as the same because $25 - 1 = 24 = 2 \cdot 12$.

This “wrapping around” behavior is what makes modular arithmetic look like clock arithmetic.

The integer $n$ is called the modulus.

Congruence notation

The central relation in modular arithmetic is called congruence.

For integers $a,b$ and a positive integer $n$:

$$
a \equiv b \pmod{n}
$$

is read “$a$ is congruent to $b$ modulo $n$” and means:

$$
n \text{ divides } (a - b),
$$

or in symbols, $n \mid (a-b)$.

Equivalently, $a$ and $b$ have the same remainder when divided by $n$.

Examples:

• $17 \equiv 5 \pmod{12}$ because $17 - 5 = 12$.
• $23 \equiv 3 \pmod{10}$ because $23 - 3 = 20$, a multiple of $10$.
• $-1 \equiv 4 \pmod{5}$ because $-1 - 4 = -5 = (-1)\cdot 5$.

If $a \equiv b \pmod{n}$, we sometimes say “$a$ and $b$ are in the same congruence class modulo $n$.”

Remainders and representatives

Every integer $a$ can be written as

$$
a = qn + r
$$

where $q$ is an integer and $r$ is an integer with $0 \le r < n$. The number $r$ is the remainder of $a$ upon division by $n$.

The remainder $r$ is a convenient representative of the congruence class of $a$ modulo $n$:

$$
a \equiv r \pmod{n}.
$$

For example, modulo $7$:

• $15 = 2\cdot 7 + 1$, so $15 \equiv 1 \pmod{7}$.
• $-3 = (-1)\cdot 7 + 4$, so $-3 \equiv 4 \pmod{7}$.

In modular arithmetic we often replace a number by any convenient representative of its class.

Basic properties of congruence

Congruence modulo $n$ behaves like equality in many ways:

• Reflexive: $a \equiv a \pmod{n}$ for all integers $a$.
• Symmetric: If $a \equiv b \pmod{n}$, then $b \equiv a \pmod{n}$.
• Transitive: If $a \equiv b \pmod{n}$ and $b \equiv c \pmod{n}$, then $a \equiv c \pmod{n}$.

So congruence is an equivalence relation on the integers: it groups integers into classes of numbers that are “the same modulo $n$”.

There are exactly $n$ distinct congruence classes modulo $n$, which you may think of as

$$
[0],[1],[2],\dots,[n-1],
$$

where $[r]$ is the set of all integers congruent to $r$ modulo $n$.

Arithmetic with congruences

The main power of modular arithmetic is that ordinary operations (addition, subtraction, multiplication, and sometimes division) behave nicely with congruences.

Let $a \equiv b \pmod{n}$ and $c \equiv d \pmod{n}$. Then:

• Addition:
  $$
  a + c \equiv b + d \pmod{n}.
  $$
• Subtraction:
  $$
  a - c \equiv b - d \pmod{n}.
  $$
• Multiplication:
  $$
  ac \equiv bd \pmod{n}.
  $$

Intuitively: you can replace each number with any congruent number (mod $n$) and get a congruent result.

Using remainders, these rules often translate as:

• Reduce each number to a remainder modulo $n$.
• Do the arithmetic with those remainders.
• If needed, reduce the result again modulo $n$.

Worked examples

1. Compute $38 + 57$ modulo $9$:
• $38 \equiv 2 \pmod{9}$ (since $38 = 4\cdot 9 + 2$),
• $57 \equiv 3 \pmod{9}$ (since $57 = 6\cdot 9 + 3$),

so

$$
38 + 57 \equiv 2 + 3 = 5 \pmod{9}.
$$

2. Compute $37 \cdot 42$ modulo $5$:
• $37 \equiv 2 \pmod{5}$,
• $42 \equiv 2 \pmod{5}$,

so

$$
37\cdot 42 \equiv 2\cdot 2 = 4 \pmod{5}.
$$

3. Compute $7^5$ modulo $6$:

It is easier to reduce at each step:

• $7 \equiv 1 \pmod{6}$.
• Thus $7^5 \equiv 1^5 = 1 \pmod{6}$.

We avoided calculating $7^5 = 16807$ directly.

Powers and repeated multiplication

By iterating multiplication, we get:

If $a \equiv b \pmod{n}$, then for any positive integer $k$,

$$
a^k \equiv b^k \pmod{n}.
$$

This is crucial when working with large powers: we repeatedly reduce intermediate results modulo $n$ to keep computations small.

Modular addition and multiplication tables

Just as with ordinary arithmetic, we can build addition and multiplication tables modulo $n$ using only the representatives $0,1,\dots,n-1$.

For example, modulo $5$:

• Addition table row “3”:
• $3+0 \equiv 3$,
• $3+1 \equiv 4$,
• $3+2 \equiv 5 \equiv 0$,
• $3+3 \equiv 6 \equiv 1$,
• $3+4 \equiv 7 \equiv 2$.
• Multiplication table row “3”:
• $3\cdot 0 \equiv 0$,
• $3\cdot 1 \equiv 3$,
• $3\cdot 2 \equiv 6 \equiv 1$,
• $3\cdot 3 \equiv 9 \equiv 4$,
• $3\cdot 4 \equiv 12 \equiv 2$.

These tables show how “arithmetic on a clock with $n$ hours” works for each pair of residues.

Inverses modulo $n$

In ordinary arithmetic, the multiplicative inverse of a nonzero number $a$ (like $1/a$) is a number that satisfies

$$
a \cdot \frac{1}{a} = 1.
$$

Modulo $n$, we ask a similar question: can we find an integer $x$ such that

$$
ax \equiv 1 \pmod{n}?
$$

If such an $x$ exists, then $x$ is called a multiplicative inverse of $a$ modulo $n$. We sometimes write $x = a^{-1} \pmod{n}$, although this is just notation; it means $ax \equiv 1 \pmod{n}$.

When does an inverse exist?

A key fact in modular arithmetic is:

• An integer $a$ has a multiplicative inverse modulo $n$ if and only if $\gcd(a,n) = 1$ (that is, $a$ and $n$ are relatively prime).

If $\gcd(a,n) = 1$, there will be at least one integer $x$ such that $ax \equiv 1 \pmod{n}$, and in fact all solutions are congruent to each other modulo $n$.

Examples:

1. Modulo $7$:
• $3$ has an inverse modulo $7$ because $\gcd(3,7) = 1$.

Try small multiples:

$$
3\cdot 1 = 3,\quad
3\cdot 2 = 6,\quad
3\cdot 3 = 9 \equiv 2,\quad
3\cdot 4 = 12 \equiv 5,\quad
3\cdot 5 = 15 \equiv 1 \pmod{7}.
$$

So $3\cdot 5 \equiv 1 \pmod{7}$, meaning $5$ is an inverse of $3$ modulo $7$.

• $2$ also has an inverse modulo $7$ (since $\gcd(2,7)=1$):

$$
2\cdot 4 = 8 \equiv 1 \pmod{7},
$$

so $2^{-1} \equiv 4 \pmod{7}$.

2. Modulo $8$:
• Consider $a = 2$. We have $\gcd(2,8) = 2 \ne 1$, so $2$ has no multiplicative inverse modulo $8$.
• Consider $a = 3$. Here $\gcd(3,8) = 1$, so $3$ does have an inverse:

$$
3\cdot 3 = 9 \equiv 1 \pmod{8},
$$

so $3^{-1} \equiv 3 \pmod{8}$.

The method of actually finding inverses systematically, especially for larger numbers, will be handled where the Euclidean algorithm is discussed; here we focus on the modular meaning.

Units modulo $n$

The elements that do have multiplicative inverses modulo $n$ are called units modulo $n$. They are precisely the congruence classes $[a]$ with $\gcd(a,n)=1$.

For example, modulo $10$, the units are the classes represented by $1,3,7,9$, since each of these is relatively prime to $10$.

Modular division (solving linear congruences)

Division in modular arithmetic is subtler than addition and multiplication. We do not simply “divide both sides” in all cases. Division modulo $n$ is only allowed when the divisor has a multiplicative inverse modulo $n$.

A basic type of problem is the linear congruence:

$$
ax \equiv b \pmod{n},
$$

where $a,b,n$ are given integers, and we want integer solutions $x$.

Case 1: $\gcd(a,n) = 1$

If $\gcd(a,n) = 1$, then $a$ has an inverse modulo $n$, say $a^{-1}$. Multiplying both sides by $a^{-1}$ gives:

$$
x \equiv a^{-1} b \pmod{n},
$$

and this is the unique solution modulo $n$ (all other solutions differ from this by a multiple of $n$).

Example:

Solve $3x \equiv 5 \pmod{7}$.

• From above, $3^{-1} \equiv 5 \pmod{7}$.
• Multiply both sides by $3^{-1}$:

$$
x \equiv 3^{-1}\cdot 5 \equiv 5\cdot 5 = 25 \equiv 4 \pmod{7}.
$$

So all integer solutions are $x = 4 + 7k$ for integers $k$.

Case 2: $\gcd(a,n) \ne 1$

If $\gcd(a,n) = d > 1$, there are two possibilities:

• If $d$ does not divide $b$, the congruence has no solutions.
• If $d$ does divide $b$, then there are exactly $d$ different solutions modulo $n$.

The systematic solution uses the greatest common divisor and simplification; the full method is naturally tied to the Euclidean algorithm and is usually treated alongside it. For this chapter, the main modular idea is:

• You can “cancel” a common factor $d$ from $a$, $b$, and $n$ only if $d$ divides $b$ and $d$ divides $n$.

Example:

Solve $4x \equiv 6 \pmod{10}$.

• $\gcd(4,10) = 2$, and $2$ divides $6$, so solutions exist.
• Divide the entire congruence by $2$:

$$
2x \equiv 3 \pmod{5}.
$$

• Now $\gcd(2,5) = 1$, so $2$ has an inverse modulo $5$.

We check:

$$
2\cdot 3 = 6 \equiv 1 \pmod{5},
$$

so $2^{-1} \equiv 3 \pmod{5}$.

• Multiply both sides by $3$:

$$
x \equiv 3\cdot 3 = 9 \equiv 4 \pmod{5}.
$$

This gives solutions modulo $5$ as $x \equiv 4 \pmod{5}$. But our original modulus was $10$, and since we divided by $2$, there are $2$ distinct classes modulo $10$ that correspond:

$$
x \equiv 4 \pmod{5} \iff x \equiv 4 \text{ or } 9 \pmod{10}.
$$

Indeed,

• $4$ satisfies $4x = 4\cdot 4 = 16 \equiv 6 \pmod{10}$,
• $9$ satisfies $4\cdot 9 = 36 \equiv 6 \pmod{10}$.

So the full solution set is $x \equiv 4,9 \pmod{10}$.

Common patterns and shortcuts

Modular arithmetic often reveals patterns that are hidden in ordinary arithmetic. Some typical uses:

• Checking divisibility: For instance, “sum of digits” rules for divisibility by $3$ or $9$ can be expressed using congruences modulo $3$ or $9$.
• Last digits: The last decimal digit of a number depends only on the number modulo $10$.
• Parity (even/odd): This is arithmetic modulo $2$.

Although detailed divisibility tests and their proofs belong elsewhere, modular arithmetic gives the language and structure to express them succinctly. For example:

• Saying “$a$ is odd” can be written as $a \equiv 1 \pmod{2}$.
• Saying “$a$ leaves remainder $r$ when divided by $n$” is $a \equiv r \pmod{n}$.

Systems of congruences (preview of the Chinese remainder idea)

Sometimes you want a number that simultaneously satisfies several modular conditions, like:

$$
\begin{cases}
x \equiv 2 \pmod{3}, \\
x \equiv 1 \pmod{5}.
\end{cases}
$$

The general theory of when such systems have solutions and how to find them efficiently is covered by the Chinese Remainder Theorem, which is treated in more advanced contexts. For now, the modular viewpoint is:

• Each congruence restricts $x$ to one congruence class modulo its modulus.
• We seek an integer that lies in all of those classes at once.

The key condition (that the moduli be relatively prime) and the construction of solutions will properly be handled when that theorem is studied. Here it is enough to recognize this as a modular arithmetic problem.

Modular arithmetic as arithmetic on congruence classes

Conceptually, you can think of working modulo $n$ as doing arithmetic not on individual integers, but on their congruence classes:

• The classes are $[0],[1],\dots,[n-1]$.
• Addition and multiplication are defined by
  $$
  [a] + [b] = [a+b],\qquad [a]\cdot[b] = [ab],
  $$
  where the right‑hand sides are reduced modulo $n$.

This viewpoint emphasizes that modular arithmetic is a kind of “arithmetic system” in its own right, with its own elements and rules, rather than just a notation trick on the usual integers.

In later topics, this structural idea connects modular arithmetic to larger themes in number theory and algebra, and to its applications such as cryptography, hashing, and error‑detecting codes.