Arithmetic Modulo $n$
Arithmetic modulo $n$ is arithmetic performed on residue classes modulo $n$. Instead of distinguishing all integers separately, we identify integers that have the same...
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.