Arithmetic Modulo $n$

Modular Arithmetic

Arithmetic modulo $n$ is arithmetic performed on residue classes modulo $n$. Instead of distinguishing all integers separately, we identify integers that have the same remainder after division by $n$.

Thus, modulo $n$, every integer is represented by one of

For example, modulo $5$,

So in arithmetic modulo $5$, the integer $7$ behaves like $2$, and the integer $13$ behaves like $3$.

Addition Modulo $n$

To add two residue classes modulo $n$, add representatives and then reduce the result modulo $n$.

For example, modulo $7$,

Therefore,

The sum wraps around after reaching $7$. This is why modular arithmetic is often called clock arithmetic. On a clock modulo $12$,

Subtraction Modulo $n$

Subtraction works in the same way. Subtract first, then reduce modulo $n$.

For example, modulo $9$,

Since

we have

Negative numbers cause no difficulty because every integer has a unique representative among

Multiplication Modulo $n$

Multiplication modulo $n$ is defined by

For example, modulo $8$,

Thus

Multiplication modulo $n$ is associative, commutative, and distributive over addition, because these laws hold for ordinary integers and congruence respects arithmetic.

Powers Modulo $n$

Powers are repeated multiplication modulo $n$. They are computed by reducing intermediate results.

For example, modulo $10$,

After that, the pattern repeats:

Such periodic behavior is common in modular arithmetic.

Additive Identity and Additive Inverses

The class

is the additive identity because

Every class has an additive inverse. The inverse of $[a]_n$ is

For example, modulo $7$, the additive inverse of $[3]_7$ is $[4]_7$, since

Thus addition modulo $n$ behaves like addition in a finite cyclic system.

Multiplicative Identity and Units

The class

is the multiplicative identity:

However, not every nonzero residue class has a multiplicative inverse.

A class $[a]_n$ has a multiplicative inverse modulo $n$ if there exists a class $[b]_n$ such that

Equivalently,

This occurs exactly when

For example, modulo $8$,

so $[3]_8$ is its own inverse.

But $[2]_8$ has no inverse because

Zero Divisors

A nonzero residue class $[a]_n$ is called a zero divisor if there exists a nonzero class $[b]_n$ such that

For example, modulo $6$,

Thus $[2]_6$ and $[3]_6$ are zero divisors.

Zero divisors occur precisely because $6$ is composite. In contrast, modulo a prime $p$, there are no zero divisors among nonzero classes.

Prime Moduli

When the modulus $p$ is prime, arithmetic modulo $p$ has especially good behavior.

Every nonzero class modulo $p$ has a multiplicative inverse. Indeed, if

then

Therefore $[a]_p$ is a unit.

The set

is then a finite field. This means addition, subtraction, multiplication, and division by nonzero elements are all possible.

For example, modulo $5$,

because

Composite Moduli

When $n$ is composite, the arithmetic of $\mathbb{Z}/n\mathbb{Z}$ is more complicated.

Some nonzero classes may fail to have inverses, and some may be zero divisors.

For example, modulo $12$,

is a unit because

But

is not a unit because

Also,

so both $[3]_{12}$ and $[4]_{12}$ are zero divisors.

Role in Number Theory

Arithmetic modulo $n$ is one of the central tools of number theory. It reduces questions about infinitely many integers to questions about a finite set of residue classes.

This makes many problems tractable. Congruences can test divisibility, solve equations, analyze powers, study primes, and construct cryptographic systems.

The passage from integers to

is therefore a fundamental move: it replaces global arithmetic by finite arithmetic while preserving the divisibility information encoded by the modulus.