Modular congruence ($\equiv$)

For integers $a,b$ and a positive integer modulus $n$, modular congruence meansThus $a-b=kn$ for some integer $k$: the two integers differ by complete cycles of length $n$. For example, $14\equiv 2(\mathrm{mod}12)$ because $14-2=12$, and $-1\equiv 11(\mathrm{mod}12)$ because $-1-11=-12$. A modular congruence need not be an equality of integers.

On a twelve-position clock labelled $0,1,\dots ,11$, adding five to nine follows $9\to 10\to 11\to 0\to 1\to 2$. Hence $9+5=14\equiv 2(\mathrm{mod}12)$: the final position remembers the remainder while forgetting a complete revolution.

The same idea tracks any count repeating every $n$ steps. It also lets us compute sums and products with small residue classes, reducing intermediate results without changing the final class. The justification comes from addition and multiplication being well-defined on residue classes.

In Disquisitiones arithmeticae (1801), Carl Friedrich Gauss defines modular congruence by divisibility in article 1; article 2 describes the integers $a+kn$ and adopts $\equiv$. These passages document his presentation and notation, without claiming that repeating remainders began in 1801. ^[ref]

A quadratic congruence is a modular congruence defined by a degree-two polynomial, with solutions sought among residue classes. For odd $n$ and $a$ invertible modulo $n$, completing the square gives $(2ax+b{)}^2\equiv b^2-4ac(\mathrm{mod}n)$. A Jacobi symbol of $-1$ for a coprime proposed square rules out solutions, whereas a Jacobi symbol of $1$ alone does not establish solubility for a composite modulus.

For a prime $p$ and $k\ge 1$, write $a=b+p^{k}h$. The binomial theorem shows $a^p-b^p$ is divisible by $p^{k+1}$: the linear term contains the extra factor $p$ and every higher term contains at least $p^{2k}$. Iteration gives the displayed modular congruence for every $r\ge 0$, including $p=2$. Applied to Fermat's little theorem, it yields $a^{p^n}\equiv a^{p^{n-1}}(\mathrm{mod}{p}^n)$.

For a positive modulus $n$, a reduced residue system contains exactly one representative of each residue class coprime to $n$. Its size is the Euler totient function $\phi (n)$. Multiplication by any unit modulo n permutes these classes, which proves the Fermat-Euler theorem after multiplying and cancelling their unit product.

A linear congruence asks for the integers $x$ satisfying $ax\equiv b(\mathrm{mod}n)$, where $a,b$ are integers and $n>1$. Let $d=\gcd (a,n)$ be their greatest common divisor. There are solutions exactly when $d$ divides $b$. When solutions exist, there are exactly $d$ solution classes modulo $n$, obtained from one solution $x_0$ byThe divisibility condition follows immediately from $ax-b=kn$: every common divisor of $a,n$ must divide $b$. Conversely, Bézout's identity constructs a solution when $d\mid b$. Differences between any two solutions obey $n\mid a(x-x_0)$, equivalently $n/d\mid x-x_0$, since $a/d$ and $n/d$ are coprime. This explains both the spacing and the number of solution classes.

For a complete example, solve $6x\equiv 9(\mathrm{mod}15)$. Here $d=3$ divides nine. Dividing the corresponding divisibility statement by three changes the integer modulus too:Because $2\cdot 3\equiv 1(\mathrm{mod}5)$, multiplying by the modular inverse three gives $x\equiv 9\equiv 4(\mathrm{mod}5)$. Lifting this class back to modulus fifteen yields $x\equiv 4,9,14(\mathrm{mod}15)$. Direct substitution gives $24$, $54$ and $84$, each with remainder nine after division with remainder by fifteen. By contrast, $6x\equiv 10(\mathrm{mod}15)$ has no solutions, because three does not divide ten.

This is why ordinary-looking division cannot be performed blindly in modular arithmetic. Reducing the equation and its integer modulus together keeps all solutions; retaining modulus fifteen after dividing by three would lose valid classes. When $d=1$, the modular inverse of $a$ exists and gives a unique class $x\equiv a^{-1}b(\mathrm{mod}n)$. The Euclidean algorithm computes the Bézout coefficients needed for this construction. ^[ref]

For integers $a,b$ and positive integers $c,n$, a common factor may be cancelled from a integer congruence provided the modulus is divided by the corresponding greatest common divisor. Let $d=\gcd (c,n)$, $c=d{c}^{\prime }$, and $n=d{n}^{\prime }$. The integers $c^{\prime },n^{\prime }$ are coprime: any common divisor greater than one would give a common divisor of $c,n$ larger than $d$.

By divisibility and Euclid's lemma,This proves the displayed equivalence. If $c$ is coprime to $n$, the modulus stays unchanged and this is ordinary cancellation by a modular multiplicative inverse. If $n\mid c$, the reduced modulus is $1$, so every pair $a,b$ satisfies the reduced integer congruence.

For a positive integer modulus $m$, the residue class of an integer $a$ is the equivalence classIt contains all integers in the same position of the repeating cycle. For example,The residue class is this whole infinite collection; its canonical representative is the least nonnegative residue. Euclidean division gives exactly one such representative in $0,1,\dots ,m-1$, so there are exactly $m$ residue classes. When $m=1$, there is just one, $[0{]}_1=\mathbb{Z}$.

Define addition and multiplication of residue classes byThese definitions must give the same answer whichever integers represent the classes. If $a^{\prime }\equiv a$ and $b^{\prime }\equiv b$ modulo $m$, thenBoth differences are divisible by $m$, proving that the operations are well-defined. For example, $[9{]}_{12}+[5{]}_{12}=[2{]}_{12}$ and $[9{]}_{12}[5{]}_{12}=[9{]}_{12}$, since $45=3\cdot 12+9$. Replacing nine by $-3$ gives the same answers with smaller intermediate integers.

With these operations the residue classes form the finite commutative ring $\mathbb{Z}/m\mathbb{Z}$, a quotient ring. It need not be a field: $[6{]}_{12}[2{]}_{12}=[0{]}_{12}$ although neither factor is the zero class. These zero divisors explain why division requires a unit modulo n. Reducing after each multiplication is especially useful in modular exponentiation, where the unreduced powers can become enormous.

For a positive integer modulus $n$, a residue class $[a{]}_n$ is a unit when it has a modular multiplicative inverse: some integer $u$ satisfies $au\equiv 1(\mathrm{mod}n)$. Modulo twelve, the units are exactlyIn particular, five is its own modular inverse, since $5\cdot 5=25\equiv 1(\mathrm{mod}12)$. Multiplying all twelve residue classes by five gives a permutation; multiplying the outputs by five recovers the inputs. By contrast, multiplying by six gives only zero and six, with six inputs for each output. It cannot be reversed.

In general, the exact criterion isFor the forward direction, $au-kn=1$ implies every common divisor of $a,n$ divides one. Conversely, if their greatest common divisor is one, Bézout's identity supplies $ua+vn=1$, so $u$ is a modular inverse. The extended Euclidean algorithm computes these coefficients. The units form the unit group $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ under multiplication. ^[ref]

Multiplicative cancellation while keeping the same integer modulus is valid for a unit modulo n: from $ca\equiv cb(\mathrm{mod}n)$, multiply by a modular inverse of $c$ to get $a\equiv b(\mathrm{mod}n)$. A nonunit cannot be cancelled as a general rule. For example, $6\cdot 0\equiv 6\cdot 2(\mathrm{mod}12)$, yet $0\not\equiv 2(\mathrm{mod}12)$. Thus division by six cannot undo this multiplication; solving a linear congruence instead keeps track of all possible classes.

This distinction marks the boundary between commutative rings and fields. Modulo a prime number $p>1$, every nonzero residue class is a unit, so $\mathbb{Z}/p\mathbb{Z}$ is a finite field. Modulo twelve it is a commutative ring with zero divisors, and is not a field. For $n=1$, the sole class satisfies $[0{]}_1=[1{]}_1$ and is a unit; this one-element zero ring is not a field. ^[ref]