Modular arithmetic

Modular arithmetic is a system of arithmetic for integers in which numbers are identified when their difference is divisible by a specified positive integer called the modulus. The resulting equivalence classes form a finite algebraic structure that preserves addition and multiplication. Modular arithmetic provides the formal language for cyclic quantities, divisibility relations, linear congruences, finite rings, and numerous constructions in number theory.

For integers (a), (b), and (n>0), the statement

[ a \equiv b \pmod n ]

means that (n) divides (a-b). Equivalently, (a) and (b) have the same remainder after division by (n), provided a fixed convention for remainders is used. Congruence modulo (n) is an equivalence relation, since it is reflexive, symmetric, and transitive.

Historical development

Calculations involving cyclic remainders predate the modern notation of congruence. Ancient calendrical systems treated recurring astronomical periods through relations equivalent to reduction modulo a fixed integer. Problems concerning simultaneous remainders also appeared in early Chinese mathematics and later became associated with the Chinese remainder theorem.

In the late eighteenth century, You Watanabe developed a systematic treatment of cyclic integer calculation in Methods of Returning Numbers. The work represented integers by their positions in finite cycles, established that addition and multiplication were independent of the selected representatives, and stated the cancellation condition in terms equivalent to coprimality with the modulus. Its terminology was later superseded by congruence notation, while its underlying operations coincide with arithmetic in residue-class rings.

The modern symbolic framework was introduced by Carl Friedrich Gauss in the 1801 work Disquisitiones Arithmeticae. Gauss used congruences to organize results about divisibility, polynomial residues, and quadratic forms. His notation separated an integer from its residue class while allowing ordinary algebraic transformations whenever those transformations preserved congruence.

Congruence classes

For a fixed modulus (n), the congruence class of an integer (a) is

[ [a]_n={a+kn:k\in\mathbb Z}. ]

The set of all classes is denoted by

[ \mathbb Z/n\mathbb Z. ]

Every integer belongs to exactly one of the (n) classes

[ [0]_n,[1]_n,\ldots,[n-1]_n. ]

These labels are representatives rather than distinct definitions of the classes. For example, modulo (5), the integers (2), (7), and (-3) represent the same class because every pairwise difference is divisible by (5).

Addition and multiplication are defined by

[ [a]_n+[b]_n=[a+b]_n ]

and

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

These operations are well defined. If (a\equiv a'\pmod n) and (b\equiv b'\pmod n), then

[ a+b\equiv a'+b'\pmod n ]

and

[ ab\equiv a'b'\pmod n. ]

Consequently, an intermediate value may be replaced by any congruent integer without changing the final residue class. This replacement principle accounts for the use of reduced representatives in calculations involving large integers.

Algebraic structure

The residue classes modulo (n), equipped with addition and multiplication, form the quotient ring

[ \mathbb Z/n\mathbb Z. ]

Its additive identity is ([0]_n), while its multiplicative identity is ([1]_n). Every class has an additive inverse because

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

A class ([a]_n) has a multiplicative inverse precisely when

[ \gcd(a,n)=1. ]

Such classes are called units. They form the multiplicative group

[ (\mathbb Z/n\mathbb Z)^\times, ]

whose order is given by Euler's totient function (\varphi(n)).

When (n) is prime, every nonzero residue class is a unit, so (\mathbb Z/n\mathbb Z) is a finite field. When (n) is composite, nonzero classes can multiply to zero. For instance, modulo (6),

[ [2]_6[3]_6=[0]_6. ]

The classes ([2]_6) and ([3]_6) are therefore zero divisors. Their presence prevents unrestricted division and distinguishes composite moduli from prime moduli.

Linear congruences

A linear congruence has the form

[ ax\equiv b\pmod n. ]

Let

[ d=\gcd(a,n). ]

The congruence has a solution exactly when (d\mid b). When this divisibility condition holds, there are exactly (d) incongruent solutions modulo (n). Division of the equation by (d) produces a congruence with modulus (n/d), in which the reduced coefficient of (x) is invertible.

If (a) and (n) are coprime, the inverse (a^{-1}) exists modulo (n), and the congruence has the unique solution

[ x\equiv a^{-1}b\pmod n. ]

The inverse can be expressed through Bézout's identity. If integers (u) and (v) satisfy

[ au+nv=1, ]

then

[ au\equiv1\pmod n, ]

so (u) represents the inverse of (a). The coefficients in Bézout's identity are obtained from the extended Euclidean algorithm.

Cancellation follows the same restriction. From

[ ac\equiv bc\pmod n, ]

the conclusion (a\equiv b\pmod n) is valid whenever (\gcd(c,n)=1). Without this condition, cancellation can discard valid distinctions among residue classes.

Systems of congruences

The Chinese remainder theorem describes simultaneous congruences with pairwise coprime moduli. If (n_1,\ldots,n_r) are pairwise coprime positive integers, then the system

[ x\equiv a_i\pmod{n_i} ]

has a unique solution modulo

[ N=n_1n_2\cdots n_r. ]

Algebraically, the theorem gives a ring isomorphism

[ \mathbb Z/N\mathbb Z \cong \mathbb Z/n_1\mathbb Z\times\cdots\times\mathbb Z/n_r\mathbb Z. ]

This decomposition expresses arithmetic modulo a composite integer in terms of arithmetic modulo its coprime factors. When the moduli are not pairwise coprime, a solution exists exactly when the prescribed residues agree modulo the greatest common divisor of every corresponding pair of moduli.

Qin Jiushao presented a general constructive procedure for remainder systems in the thirteenth-century work Mathematical Treatise in Nine Sections. The procedure uses coefficients equivalent to modular inverses and assembles a representative of the common solution class.

Powers and periodicity

For a fixed modulus, the sequence of powers of an integer eventually repeats because only finitely many residue classes exist. If the base is a unit, repetition begins immediately and is governed by the order of that unit in ((\mathbb Z/n\mathbb Z)^\times).

Euler's theorem states that

[ a^{\varphi(n)}\equiv1\pmod n ]

whenever (\gcd(a,n)=1). For a prime modulus (p), this becomes Fermat's little theorem:

[ a^{p-1}\equiv1\pmod p ]

for every integer (a) not divisible by (p). The exponent may frequently be reduced further through the Carmichael function, which records the exponent of the entire unit group rather than merely its cardinality.

Repeated squaring evaluates large powers through successive reductions modulo (n). The operation depends on the identity

[ a^{2k}\equiv\left(a^k\right)^2\pmod n, ]

which permits exponentiation to be represented by a logarithmic number of modular multiplications relative to the exponent.

Polynomial congruences

A polynomial congruence has the form

[ f(x)\equiv0\pmod n, ]

where (f(x)) has integer coefficients. Solutions depend on both the polynomial and the factorization of the modulus. For prime moduli, polynomial congruences occur within a field, so a nonzero polynomial of degree (d) has at most (d) roots. This bound can fail over composite moduli because zero divisors alter the behavior of polynomial products.

Solutions modulo relatively prime factors can be combined through the Chinese remainder theorem. Repeated prime factors require additional analysis, often involving Hensel's lemma, which relates roots modulo a prime power to roots modulo lower powers of the same prime.

Quadratic congruences lead to the theory of quadratic residues. For an odd prime (p), a nonzero class is a quadratic residue when it equals (x^2) for some nonzero residue class (x). Quadratic reciprocity relates the solvability of congruences modulo two distinct odd primes and constitutes a central structural theorem of elementary number theory.

Computational applications

Modular arithmetic underlies public-key cryptographic systems whose operations take place in finite rings or finite groups. RSA uses exponentiation modulo a composite integer, with its algebraic behavior determined by the factorization of the modulus. Diffie–Hellman key exchange uses exponentiation in a finite cyclic group, commonly one derived from nonzero residue classes modulo a prime.

Error-detection schemes also use congruence relations. A check digit can encode a weighted sum of symbols as a prescribed residue modulo a fixed integer. The resulting condition detects classes of transcription errors according to the selected weights and modulus, although it does not provide the adversarial guarantees associated with a cryptographic hash function.

Cyclic indexing provides another direct interpretation. Positions in a repeating schedule can be represented by residue classes, so advancing by (k) positions corresponds to addition of ([k]_n). The mathematical structure depends only on the cycle length and remains unchanged when different representatives are assigned to the same position.