Modular Arithmetic

Modular arithmetic is a system of arithmetic in which integers are compared and combined according to their remainders upon division by a fixed positive integer, called the modulus. Numbers differing by a multiple of the modulus are treated as equivalent. This produces “wraparound” calculations rather than an indefinitely increasing number line. Modular arithmetic provides a basic language for number theory and underlies important constructions in cryptography. (cs.cornell.edu)

Congruence and remainders

For a positive integer $n$, the notation

means that $n$ divides $a-b$, or equivalently that $a-b=kn$ for some integer $k$. Thus $17\equiv5\pmod{12}$, because their difference is $12$. Negative integers also have residues: $-1\equiv11\pmod{12}$. The statement describes a relationship between integers, not ordinary equality between them. (cs.cornell.edu)

By division with remainder, every integer has a unique expression $a=qn+r$, where $0\leq r<n$. The number $r$ is its least nonnegative residue modulo $n$. Consequently, congruent integers have the same remainder. The expression $a\bmod n$ usually denotes this particular remainder, whereas “$\pmod n$” in a congruence specifies the relation being used. (cs.cornell.edu)

A twelve-hour clock illustrates the idea: advancing five hours from ten gives three, since $10+5\equiv3\pmod{12}$. The clock label twelve represents residue zero. This analogy explains wraparound addition, although the mathematical system also supports multiplication and more general algebraic operations. (pi.math.cornell.edu)

Arithmetic rules

Congruences respect addition, subtraction, and multiplication. If $a\equiv b\pmod n$ and $c\equiv d\pmod n$, then

Intermediate results may therefore be reduced modulo $n$ without changing the final residue. For example, modulo seven, $19\cdot23\equiv5\cdot2\equiv3$. Reducing first often makes calculations substantially smaller. (cs.cornell.edu)

Repeated multiplication also gives $a^k\equiv b^k\pmod n$ for every nonnegative integer $k$. These rules extend to evaluating any polynomial with integer coefficients. However, exponents cannot generally be reduced modulo the same modulus: $2^4\equiv1\pmod5$, whereas $2^{4+5}\equiv2\pmod5$. Exponent reduction requires separate conditions and theorems. (cs.cornell.edu)

Residue classes and algebraic structure

Congruence modulo $n$ is an equivalence relation: it is reflexive, symmetric, and transitive. It partitions the integers into $n$ residue classes. The class containing $a$ is

The collection of classes is denoted $\mathbb Z/n\mathbb Z$, also written $\mathbb Z_n$. Addition and multiplication are defined by $[a]+[b]=[a+b]$ and $[a][b]=[ab]$; the congruence rules ensure that the definitions do not depend on the chosen representatives. (cs.cornell.edu)

In abstract algebra, this structure is a commutative ring with identity. Its additive structure is a cyclic group, connecting it with group theory. If $n$ is a prime number, every nonzero class is invertible, so the ring is a field, specifically a finite field with $n$ elements. Composite moduli instead admit nonzero classes whose product is zero: modulo six, $[2][3]=[0]$. (cs.cornell.edu)

Inverses and linear congruences

A modular multiplicative inverse of $a$ is an integer $u$ satisfying $au\equiv1\pmod n$. It exists exactly when the greatest common divisor $\gcd(a,n)$ equals one. The extended Euclidean algorithm finds integers $u,v$ satisfying $au+nv=1$; reducing this identity modulo $n$ gives the inverse. For instance, three has inverse five modulo seven. (math.stanford.edu)

Division therefore means multiplication by an inverse, not ordinary integer division. Cancellation can fail when the factor is not invertible: $2\cdot1\equiv2\cdot4\pmod6$, but $1\not\equiv4\pmod6$. More generally, cancelling $a$ changes the modulus to $n/\gcd(a,n)$. (cs.cornell.edu)

A linear congruence $ax\equiv b\pmod n$ has a solution precisely when $d=\gcd(a,n)$ divides $b$. When solvable, it has exactly $d$ distinct solutions modulo $n$. For example, $4x\equiv2\pmod6$ has the two solutions $x\equiv2$ and $x\equiv5$. These facts follow by applying the inverse criterion after dividing the coefficients and modulus by $d$. (math.stanford.edu)

Fundamental theorems

Fermat’s little theorem states that $a^p\equiv a\pmod p$ for prime $p$. If $p$ does not divide $a$, this becomes $a^{p-1}\equiv1\pmod p$. Euler’s theorem generalizes the latter statement:

Here Euler’s totient function $\varphi(n)$ counts the integers from one through $n$ that are relatively prime to $n$. (math.stanford.edu)

The Chinese remainder theorem combines congruences with pairwise coprime moduli. Given $x\equiv a_i\pmod{n_i}$, it guarantees one solution class modulo $n_1\cdots n_k$. Thus $x\equiv2\pmod3$ and $x\equiv3\pmod5$ together give $x\equiv8\pmod{15}$. (math.stanford.edu)

Historical development and applications

Carl Friedrich Gauss presented a systematic treatment of congruences in Disquisitiones Arithmeticae, published in 1801. Its opening sections address congruences generally, linear congruences, and residues of powers, establishing the framework for subsequent investigations. (e-rara.ch)

In computer science, modular calculations support hash-table indexing, check digits, and pseudorandom sequences. They also explain decimal divisibility tests: because $10\equiv1\pmod9$, an integer is congruent modulo nine to the sum of its digits. (cs.cornell.edu)

The RSA cryptosystem uses modular exponentiation with a modulus formed from two primes. Its basic mathematical transformation is $c=m^e\bmod n$, with a related private exponent reversing the transformation. Secure encryption requires additional encoding and padding mechanisms beyond this arithmetic operation. (cs.cornell.edu)