Modular arithmetic ($\mathbb{Z}/m\mathbb{Z}$)

Modular arithmetic performs addition and multiplication on integers while remembering only their remainders for a fixed positive integer modulus $m$. The relation $a\equiv b(\mathrm{mod}m)$ means that $m$ divides $a-b$: the two integers lie in the same congruence class. For example, $-3$, $2$ and $7$ represent one class modulo $5$. Choosing the least nonnegative residue gives exactly $m$ representatives, $0,1,\dots ,m-1$, even though each congruence class contains infinitely many integers.

A clock supplies a familiar example. Represent the twelve positions by $0,1,\dots ,11$, with $0$ at the position usually labelled twelve. Starting at ten and moving seven positions givesThe integer congruence records the final position; it discards the number of complete revolutions. Adding another twelve changes the elapsed count while preserving the position. The picture also shows a single congruence class modulo five spread along the number line.

The useful surprise is that discarding this information still preserves the arithmetic. If $a\equiv a^{\prime }$ and $b\equiv b^{\prime }$ modulo $m$, then $a+b\equiv a^{\prime }+b^{\prime }$ and $ab\equiv a^{\prime }{b}^{\prime }$ modulo $m$. Thus a large calculation can reduce its intermediate integers after every step. For instance,Replacing $10$ by $-2$ gives the same answers with smaller intermediate values. The congruence classes with these operations form the quotient ring $\mathbb{Z}/m\mathbb{Z}$; their addition alone forms a cyclic group. This passage from integers to a finite arithmetic system is the setting for modular exponentiation, primality testing and the RSA cryptosystem. ^[ref]

Multiplicative cancellation needs extra care. Modulo six, $2\cdot 1\equiv 2\cdot 4$, but $1\not\equiv 4$: multiplication by two has merged distinct congruence classes. Cancelling a factor while retaining the integer modulus is justified when that factor has a modular multiplicative inverse, equivalently when it is coprime to the integer modulus. A linear congruence can consequently have no solutions, one solution class, or several solution classes. The Chinese remainder theorem supplies a complementary operation: splitting a calculation across coprime integer moduli and reconstructing its class modulo their product.

Small remainders can also certify impossibility. A perfect square has residue zero or one modulo four, as checking the four congruence classes shows. Therefore an integer equation $x^2=4k+2$ has no solution. The converse direction needs care: a permitted residue does not guarantee an integer solution, since $5\equiv 1(\mathrm{mod}4)$ but five is not a perfect square. Such local tests provide necessary conditions for Diophantine equations without replacing the full problem.

In Disquisitiones arithmeticae (1801), Carl Friedrich Gauss defines integer congruence in article 1 and adopts the symbol $\equiv$ in article 2. Article 12 derives divisibility tests from powers of ten and explains checking arithmetic by its remainders. These passages show a systematic treatment of the same idea; they are not a claim that remainders were first used in 1801. ^[ref]

A free-running digital counter with modulus $M$ shows only the residue of elapsed ticks. If two observations differ by a true interval $d<M$, their modular difference is congruent to $d$ and is the unique representative in $\{0,\dots ,M-1\}$, proving the displayed identity. It handles a wrap between observations without a conditional branch. A complete elapsed modulus is indistinguishable from zero, so the interval bound is essential. For a $w$-bit timer at frequency $f$, the wrap period is $2^w/f$, and unsigned integer arithmetic in C can implement the difference directly on an appropriate type.

A nonzero residue class $a$ modulo an odd prime number $p$ is a biquadratic residue if $x^4\equiv a(\mathrm{mod}p)$ for some integer $x$.

For an integer $a$ and a positive integer modulus $m$, the modulo operation returns the unique least nonnegative residue $r$ satisfying $a=qm+r$ for an integer $q$ and $0\le r<m$. Equivalently, $r=a-m\lfloor a/m\rfloor$. For example, $-3\mathrm{mod}5=2$. Some programming languages instead use a remainder with the sign of the dividend, so their negative-input convention must be checked before identifying an operator with this mathematical definition.

Computing the remainder $ab\mathrm{mod}m$ while working with bounded integer representatives. Repeated doubling and addition can avoid forming an overflowing product: process the binary digits of $b$, double the current contribution modulo $m$, and add it to the result whenever the current binary digit is 1. The additions themselves must also use an overflow-safe implementation.

For an integer $n\ge 1$, add residue classes by adding their representatives and taking the class modulo $n$. This is well-defined because replacing either representative by a multiple-of-$n$ translate changes the sum by a multiple of $n$. The associativity, identity class $[0{]}_n$ and inverse $[-a{]}_n$ are inherited from integer addition. The result is the additive cyclic group $\mathbb{Z}/n\mathbb{Z}$.

The positive integer $m$ in $a\equiv b(\mathrm{mod}m)$ is the modulus. It specifies which differences are ignored: exactly the integer multiples of $m$. It is distinct from the modulus of a complex number, which measures magnitude.

The least nonnegative residue of an integer $a$ modulo a positive integer modulus $m$ is the unique representative $r$ of its congruence class in $\{0,\dots ,m-1\}$. Euclidean division gives $a=qm+r$. For example, $-3=(-1)\cdot 5+2$, so $-3\mathrm{mod}5=2$; the integer congruence $-3\equiv 2(\mathrm{mod}5)$ does not assert equality of those two integers.

For a positive modulus $m$, integers $a,b$ are congruent when their difference is divisible by $m$. This is an equivalence relation: zero is divisible by $m$, changing sign preserves divisibility, and adding two divisible differences proves transitivity. Addition and multiplication respect it, because $(a+c)-(b+d)=(a-b)+(c-d)$ and $ac-bd=c(a-b)+b(c-d)$. Its equivalence classes are the residue classes used in modular arithmetic.

For every prime $p\ge 5$, $\left(\genfrac{}{}{0ex}{}{2p-1}{p-1}\right)\equiv 1(\mathrm{mod}{p}^3)$. Equivalently, ${\sum }_{k=1}^{p-1}1/k\equiv 0(\mathrm{mod}{p}^2)$, with denominators interpreted through modular inverses.

For an integer $n>1$, Wilson's theorem characterizes prime numbers by a factorial:The right side is an integer congruence, so the least nonnegative remainder is $n-1$. For example, $4!=24\equiv 4(\mathrm{mod}5)$ certifies that five is a prime number, whereas $5!=120\equiv 0(\mathrm{mod}6)$ rules out six. ^[ref]

For an odd prime number $p$, each nonzero congruence class has a unique modular multiplicative inverse. Pair each class with its inverse: each distinct pair contributes one. A class is its own inverse exactly when $a^2\equiv 1(\mathrm{mod}p)$; since $p\mid (a-1)(a+1)$, Euclid's lemma leaves only $a\equiv \pm 1$. Their product is $-1$. The prime number two needs a separate check: $1!\equiv -1(\mathrm{mod}2)$. Conversely, a proper divisor $1<d<n$ divides both $n$ and $(n-1)!$, so the displayed integer congruence would force $d\mid 1$, a contradiction. ^[ref]

The composite numbers have an even sharper pattern: $(n-1)!\equiv 0(\mathrm{mod}n)$ for every composite number $n>4$, but $3!=6\equiv 2(\mathrm{mod}4)$. To check the zero claim, write $n=ab$ with $1<a\le b<n$. If $a<b$, both occur as different factors in the factorial. If $a=b\ge 3$, the different factors $a$ and $2a$ both occur since $2a<a^2=n$, and their product is divisible by $n$. The only excluded case is $a=b=2$. Thus four is an exception to the zero pattern, but still fails Wilson's theorem: its required remainder would be three.

This is an exact primality testing criterion, but direct evaluation is expensive: even reducing modulo $n$ after every multiplication still takes a number of multiplications proportional to $n$, which grows exponentially with the number of binary digits of $n$. The problem is not merely storing a huge factorial. The more useful role of Wilson's theorem is simplifying factorial expressions in modular arithmetic. For instance, if $p>2$ is a prime number, then $(p-1)(p-2)!\equiv -1(\mathrm{mod}p)$ gives $(p-2)!\equiv 1(\mathrm{mod}p)$ by a modular multiplicative inverse.

For an odd prime number $p$, put $m=(p-1)/2$. Both $(p-1)!$ and $p-1$ are divisible by $m$. By Wilson's theorem, they are also congruent modulo $p$, because each is $-1$ modulo $p$. The coprime integers $m,p$ therefore both divide their difference, giving the displayed integer congruence. This combines the prime-modulus factorial identity with an elementary divisibility constraint.

For an odd prime $p$, the even residues are the negatives of the odd residues. If $O=1\cdot 3\cdots (p-2)$, then $(p-1)!\equiv (-1{)}^{(p-1)/2}{O}^2$. Apply Wilson theorem to obtain the displayed congruence. The empty product for $p=3$ is one.

For a prime number $p$ and nonnegative integers $h+k=p-1$, Wilson theorem gives $(-1{)}^{k}h!k!\equiv -1(\mathrm{mod}p)$ by replacing the last $k$ factors of $(p-1)!$ with $-1,-2,\dots ,-k$. For odd $p$, $h,k$ have the same parity; for $p=2$, both signs have the same residue class. Thus $h!k!+(-1{)}^h\equiv 0(\mathrm{mod}p)$, including the endpoint cases $0!=1$.

The congruence class of $a$ modulo a positive integer $N$ is $\{a+Nk:k\in \mathbb{Z}\}$. Two integers have the same class exactly when their difference is divisible by $N$. Addition and multiplication of representatives descend to well-defined operations on $\mathbb{Z}/N\mathbb{Z}$, because replacing a representative by a multiple-of-$N$ translate changes the result by a multiple of $N$.

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]