# 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

$$
0,1,2,\ldots,n-1.
$$

For example, modulo $5$,

$$
7\equiv2\pmod5,
\qquad
13\equiv3\pmod5.
$$

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$,

$$
5+6=11\equiv4\pmod7.
$$

Therefore,

$$
[5]_7+[6]_7=[4]_7.
$$

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

$$
9+5\equiv2\pmod{12}.
$$

## Subtraction Modulo $n$

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

For example, modulo $9$,

$$
3-7=-4.
$$

Since

$$
-4\equiv5\pmod9,
$$

we have

$$
3-7\equiv5\pmod9.
$$

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

$$
0,1,\ldots,n-1.
$$

## Multiplication Modulo $n$

Multiplication modulo $n$ is defined by

$$
[a]_n[b]_n=[ab]_n.
$$

For example, modulo $8$,

$$
5\cdot7=35\equiv3\pmod8.
$$

Thus

$$
[5]_8[7]_8=[3]_8.
$$

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$,

$$
3^1\equiv3,
$$

$$
3^2\equiv9,
$$

$$
3^3\equiv27\equiv7,
$$

$$
3^4\equiv21\equiv1.
$$

After that, the pattern repeats:

$$
3^5\equiv3,
\qquad
3^6\equiv9.
$$

Such periodic behavior is common in modular arithmetic.

## Additive Identity and Additive Inverses

The class

$$
[0]_n
$$

is the additive identity because

$$
[a]_n+[0]_n=[a]_n.
$$

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

$$
[-a]_n.
$$

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

$$
3+4=7\equiv0\pmod7.
$$

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

## Multiplicative Identity and Units

The class

$$
[1]_n
$$

is the multiplicative identity:

$$
[a]_n[1]_n=[a]_n.
$$

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

$$
[a]_n[b]_n=[1]_n.
$$

Equivalently,

$$
ab\equiv1\pmod n.
$$

This occurs exactly when

$$
\gcd(a,n)=1.
$$

For example, modulo $8$,

$$
3\cdot3=9\equiv1\pmod8,
$$

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

But $[2]_8$ has no inverse because

$$
\gcd(2,8)=2.
$$

## Zero Divisors

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

$$
[a]_n[b]_n=[0]_n.
$$

For example, modulo $6$,

$$
[2]_6[3]_6=[6]_6=[0]_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

$$
1\le a\le p-1,
$$

then

$$
\gcd(a,p)=1.
$$

Therefore $[a]_p$ is a unit.

The set

$$
\mathbb{Z}/p\mathbb{Z}
$$

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

For example, modulo $5$,

$$
[2]_5^{-1}=[3]_5,
$$

because

$$
2\cdot3=6\equiv1\pmod5.
$$

## 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$,

$$
[5]_{12}
$$

is a unit because

$$
\gcd(5,12)=1.
$$

But

$$
[4]_{12}
$$

is not a unit because

$$
\gcd(4,12)=4.
$$

Also,

$$
[3]_{12}[4]_{12}=[12]_{12}=[0]_{12},
$$

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

$$
\mathbb{Z}/n\mathbb{Z}
$$

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