A clock reads $11$. Five hours later it reads $4$, not $16$. This is not a failure of arithmetic; it is a change in the question. We have stopped asking for equality of integers and started asking whether two integers have the same remainder after division by $12$. Congruence is the language that makes this shift precise. The same pattern appears whenever an infinite arithmetic problem has a finite shadow. To decide whether an integer is even, we do not need the integer itself; its remainder modulo $2$ is enough. To study the last digit of a power, we reduce modulo $10$. To solve a Diophantine equation, we first ask whether it has any solution after reducing modulo a carefully chosen integer. Congruence turns divisibility into an [equivalence relation](/page/Equivalence%20Relation), and the resulting arithmetic of residue classes is the entry point to modular arithmetic, finite rings, and much of elementary number theory. [example: A Clock Calculation] Suppose a clock has $12$ positions and currently shows $11$. After $5$ hours, the integer count is \begin{align*} 11+5=16. \end{align*} To convert this integer count back to a clock position, divide by $12$: \begin{align*} 16=1\cdot 12+4. \end{align*} The remainder is $4$, so the clock shows $4$. This does not mean that $16=4$ as integers. Instead, \begin{align*} 16-4=12. \end{align*} Since $12=1\cdot 12$, the difference between $16$ and $4$ is a multiple of the modulus $12$. The clock keeps exactly the information that remains after multiples of $12$ are ignored. [/example] The clock example also warns us against a common mistake. Congruence is not approximate equality. It is exact equality after a chosen loss of information. The modulus records precisely what information has been discarded, and the rest of the theory studies which parts of ordinary arithmetic survive that loss. ## Definition Before we can calculate with remainders, we need a relation that records when two integers produce the same remainder. Divisibility provides the right test because two integers have the same remainder modulo $n$ exactly when their difference is divisible by $n$. Throughout this page, a modulus is a positive integer $n \in \mathbb{N}$. [definition: Congruence Modulo $n$] Let $n \in \mathbb{N}$. For $a,b \in \mathbb{Z}$, we say that $a$ is congruent to $b$ modulo $n$, and write \begin{align*} a &\equiv b \pmod{n}, \end{align*} if \begin{align*} n &\mid (a-b). \end{align*} [/definition] The integer $n$ is called the modulus. The case $n=1$ collapses all integers into a single congruence class, since every integer is divisible by $1$. For most arithmetic applications, the useful moduli are $n\geq 2$, where congruence keeps some information and discards the rest. The definition is phrased using divisibility rather than remainders because divisibility behaves well under addition, subtraction, and multiplication. Remainders are useful for computation; divisibility is better for structure. [example: Same Remainder, Same Congruence] Modulo $7$, the integers $31$ and $10$ have difference \begin{align*} 31-10 = 21. \end{align*} Since \begin{align*} 21 = 3\cdot 7, \end{align*} the integer $7$ divides $31-10$. By the definition of congruence modulo $7$, this gives \begin{align*} 31 \equiv 10 \pmod{7}. \end{align*} The same conclusion appears from division with remainder. We have \begin{align*} 31 = 4\cdot 7+3 \end{align*} and \begin{align*} 10 = 1\cdot 7+3. \end{align*} Both integers leave remainder $3$ after division by $7$, so they determine the same residue class modulo $7$. By contrast, \begin{align*} 31-11 = 20. \end{align*} The multiples of $7$ nearest to $20$ are \begin{align*} 2\cdot 7 = 14 \end{align*} and \begin{align*} 3\cdot 7 = 21. \end{align*} Thus $20$ is not a multiple of $7$, so $7\nmid 20$, and therefore \begin{align*} 31 \not\equiv 11 \pmod{7}. \end{align*} The test is exact: modulo $7$, sameness means that the difference is a multiple of $7$. [/example] The definition gives a test for sameness modulo $n$, but it still needs structural justification. If congruence is going to support arithmetic on classes, then its classes must not overlap ambiguously. The next question is whether congruence behaves like an honest equivalence relation; this requires reflexivity, symmetry, and transitivity. [quotetheorem:9332] This theorem justifies the language of classes. Reflexivity says every integer belongs to its own class, symmetry says the order of comparison does not matter, and transitivity says the classes do not overlap in an inconsistent way. To compute with those classes, we also need a canonical way to name each one; this is supplied by division with remainder. [quotetheorem:9333] The theorem explains why modular arithmetic is finite: although each residue class contains infinitely many integers, exactly one representative lies in the standard range from $0$ to $n-1$. This finite list of representatives is the computational face of congruence. ## Residue Classes and Representatives The equivalence-relation theorem says that congruence partitions the integers. To use that partition, we need a name for one piece of it: all integers that are indistinguishable from a chosen integer modulo $n$. [definition: Residue Class Modulo $n$] Let $n \in \mathbb{N}$ and let $a \in \mathbb{Z}$. The residue class of $a$ modulo $n$ is \begin{align*} \bar{a} &= \{b \in \mathbb{Z}: b \equiv a \pmod{n}\}. \end{align*} [/definition] A residue class is an infinite subset of $\mathbb{Z}$, but modulo $n$ there are only $n$ distinct classes. For example, modulo $5$ every integer belongs to exactly one of $\bar{0},\bar{1},\bar{2},\bar{3},\bar{4}$. The class is the object; the representative is only a convenient name for it. To do arithmetic with residue classes, we need the collection of all classes. This construction is the finite arithmetic universe obtained by declaring multiples of $n$ to be invisible. [definition: Integers Modulo $n$] Let $n \in \mathbb{N}$. The set of integers modulo $n$ is \begin{align*} \mathbb{Z}/n\mathbb{Z} &= \{\bar{a}: a \in \mathbb{Z}\}. \end{align*} [/definition] When the modulus is fixed, we often write elements as $\bar{0},\bar{1},\ldots,\overline{n-1}$. The bar is not decoration: it reminds us that $\bar{a}$ is a class, not the integer $a$ itself. ## Arithmetic of Residue Classes The first test for any proposed arithmetic on residue classes is independence of representatives. If $\bar{a}=\bar{a'}$ and $\bar{b}=\bar{b'}$, then adding or multiplying representatives should lead to the same final class. Otherwise the notation $\bar{a}+\bar{b}$ would depend on arbitrary choices. ### Well-Defined Operations Addition modulo $n$ models cyclic motion: after moving forward, reduce again to the standard residue class. The operation should be defined at the level of classes because congruence is meant to forget the chosen representative. [definition: Addition Modulo $n$] Let $n \in \mathbb{N}$. Addition modulo $n$ is the function from $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z})$ to $\mathbb{Z}/n\mathbb{Z}$ defined by \begin{align*} \bar{a}+\bar{b} &= \overline{a+b}. \end{align*} [/definition] Addition explains cyclic displacement, but many modular questions involve repeated addition packaged as multiplication: powers, divisibility tests, inverses, and equations such as $ax\equiv b\pmod n$. If multiplication stayed attached to chosen integer representatives, residue classes would not form a genuine arithmetic system. We therefore need multiplication to be defined directly on classes, with reduction after multiplying representatives. [definition: Multiplication Modulo $n$] Let $n \in \mathbb{N}$. Multiplication modulo $n$ is the function from $(\mathbb{Z}/n\mathbb{Z}) \times (\mathbb{Z}/n\mathbb{Z})$ to $\mathbb{Z}/n\mathbb{Z}$ defined by \begin{align*} \bar{a}\bar{b} &= \overline{ab}. \end{align*} [/definition] Both definitions use representatives $a$ and $b$, so they require a consistency theorem. The theorem says that replacing an integer by a congruent integer cannot change the result of addition or multiplication modulo $n$. [quotetheorem:9334] Because of this compatibility, addition and multiplication in $\mathbb{Z}/n\mathbb{Z}$ are operations on classes rather than on chosen representatives. The next structural question is whether the familiar laws of arithmetic survive after reduction modulo $n$. [quotetheorem:9335] The ring viewpoint is more than terminology. It lets us ask which elements have inverses, which equations can be solved, and when cancellation is valid. These questions behave differently depending on the modulus. [example: Arithmetic Modulo $8$] In $\mathbb{Z}/8\mathbb{Z}$, addition and multiplication are performed by using integer representatives and then reducing modulo $8$. For addition, \begin{align*} 6+7 = 13. \end{align*} To reduce $13$ modulo $8$, divide by $8$: \begin{align*} 13 = 1\cdot 8+5. \end{align*} Thus $13-5=8$, so $8\mid (13-5)$, and hence \begin{align*} \overline{13}=\bar{5}. \end{align*} Therefore \begin{align*} \bar{6}+\bar{7}=\overline{6+7}=\overline{13}=\bar{5}. \end{align*} For multiplication, \begin{align*} 6\cdot 7 = 42. \end{align*} Reducing $42$ modulo $8$ gives \begin{align*} 42 = 5\cdot 8+2. \end{align*} Thus $42-2=40=5\cdot 8$, so $8\mid (42-2)$, and hence \begin{align*} \overline{42}=\bar{2}. \end{align*} Therefore \begin{align*} \bar{6}\bar{7}=\overline{6\cdot 7}=\overline{42}=\bar{2}. \end{align*} The expression $\overline{42}$ is a valid residue class, but its standard representative modulo $8$ is $2$, so the reduction step is part of the arithmetic rather than an optional cleanup. [/example] ### Cancellation Ordinary cancellation can fail in modular arithmetic. This failure is not a nuisance; it reveals common factors between an element and the modulus. [example: Failure of Cancellation Modulo $6$] Modulo $6$, the two products are \begin{align*} 2\cdot 1 = 2 \end{align*} and \begin{align*} 2\cdot 4 = 8. \end{align*} Their difference is \begin{align*} 8-2 = 6 = 1\cdot 6. \end{align*} Thus $6\mid (8-2)$, so \begin{align*} 2\cdot 1 \equiv 2\cdot 4 \pmod{6}. \end{align*} However, canceling the common factor $2$ would assert $1\equiv 4\pmod{6}$. The difference is \begin{align*} 4-1 = 3. \end{align*} Since $3$ is not a multiple of $6$, we have $6\nmid 3$, and therefore \begin{align*} 1 \not\equiv 4 \pmod{6}. \end{align*} So the congruence $2\cdot 1\equiv 2\cdot 4\pmod{6}$ is true, but the congruence obtained by canceling $2$ is false; the obstruction is that $2$ and $6$ have the common divisor $2$. [/example] The previous example identifies a problem that needs a criterion, not just a warning. We need to know exactly which factors can be canceled without changing solution sets; coprimality with the modulus is the condition that prevents distinct residue classes from being merged. [quotetheorem:9336] The cancellation criterion is often the first place where modular arithmetic becomes sharper than remainder bookkeeping. It says that the obstruction to cancellation is exactly visible through the greatest common divisor. ## Linear Congruences and Inverses The simplest equation in modular arithmetic is linear: solve $ax \equiv b \pmod{n}$. In ordinary arithmetic, nonzero $a$ can be divided away over a field. Modulo $n$, division must be replaced by the existence of a multiplicative inverse, and that existence depends on coprimality. ### Units A coefficient can be divided away modulo $n$ precisely when it has a multiplicative inverse modulo $n$. This motivates separating the invertible classes from all residue classes. [definition: Unit Modulo $n$] Let $n \in \mathbb{N}$. An element $\bar{a} \in \mathbb{Z}/n\mathbb{Z}$ is a unit modulo $n$ if there exists $\bar{b} \in \mathbb{Z}/n\mathbb{Z}$ such that \begin{align*} \bar{a}\bar{b} &= \bar{1}. \end{align*} [/definition] A unit is exactly an element by which division is possible inside modular arithmetic. But a single inverse is not enough for exponent theorems and repeated products. We need the collection of all invertible residue classes as one object. [definition: Multiplicative Group of Units Modulo $n$] Let $n \in \mathbb{N}$. The multiplicative group of units modulo $n$ is \begin{align*} (\mathbb{Z}/n\mathbb{Z})^\times &= \{\bar{a} \in \mathbb{Z}/n\mathbb{Z}: \bar{a} \text{ is a unit modulo } n\}. \end{align*} [/definition] This group isolates the part of modular arithmetic where multiplication behaves like multiplication in a field. To use it, however, we need to know which residue classes actually lie in it. The obstruction is that multiplication by $a$ modulo $n$ may collapse distinct classes whenever $a$ shares a common factor with $n$; in that case division by $a$ cannot be well-defined. The criterion below identifies exactly when this obstruction disappears, so invertibility can be checked without guessing an inverse. [quotetheorem:7884] This theorem turns the problem of division modulo $n$ into an integer divisibility calculation. It also explains why prime moduli are special: every nonzero residue class modulo a prime is invertible. [example: Finding an Inverse Modulo $11$] To invert $7$ modulo $11$, we look for integers $u,v$ such that \begin{align*} u\cdot 11+v\cdot 7=1. \end{align*} The Euclidean algorithm gives \begin{align*} 11 = 1\cdot 7+4. \end{align*} Hence \begin{align*} 4 = 11-1\cdot 7. \end{align*} Next, \begin{align*} 7 = 1\cdot 4+3, \end{align*} so \begin{align*} 3 = 7-1\cdot 4. \end{align*} Finally, \begin{align*} 4 = 1\cdot 3+1, \end{align*} so \begin{align*} 1 = 4-1\cdot 3. \end{align*} Substitute $3=7-1\cdot 4$ into this last equation: \begin{align*} 1 = 4-(7-1\cdot 4). \end{align*} Expanding the right-hand side gives \begin{align*} 1 = 2\cdot 4-7. \end{align*} Now substitute $4=11-1\cdot 7$: \begin{align*} 1 = 2(11-1\cdot 7)-7. \end{align*} Expanding again, \begin{align*} 1 = 2\cdot 11-2\cdot 7-7. \end{align*} Combining the two multiples of $7$ gives \begin{align*} 1 = 2\cdot 11-3\cdot 7. \end{align*} Therefore \begin{align*} -3\cdot 7 = 1-2\cdot 11. \end{align*} The difference between $-3\cdot 7$ and $1$ is \begin{align*} (-3\cdot 7)-1 = -2\cdot 11, \end{align*} which is a multiple of $11$. Hence \begin{align*} -3\cdot 7 \equiv 1 \pmod{11}. \end{align*} Since \begin{align*} -3 \equiv 8 \pmod{11}, \end{align*} multiplying by $7$ gives \begin{align*} 7\cdot 8 \equiv 7\cdot (-3) \equiv 1 \pmod{11}. \end{align*} Thus the inverse of $\bar{7}$ in $\mathbb{Z}/11\mathbb{Z}$ is $\bar{8}$; equivalently, $7^{-1}\equiv 8\pmod{11}$. [/example] ### Linear Congruences Once inverses are understood, linear congruences can be solved systematically. The remaining obstruction is whether the common divisor of $a$ and $n$ also divides $b$, because any common divisor of $a$ and $n$ must also divide $ax-b$ when $ax\equiv b\pmod n$. [quotetheorem:9337] This theorem is the modular analogue of solving a linear equation, but with an arithmetic obstruction. It is also a useful diagnostic: before searching for a solution, compute one greatest common divisor. [example: A Solvable and an Insoluble Linear Congruence] Consider the congruence \begin{align*} 6x \equiv 10 \pmod{14}. \end{align*} By definition, this means that $14\mid (6x-10)$, so there is an integer $k$ such that \begin{align*} 6x-10 = 14k. \end{align*} Factoring out $2$ on both sides gives \begin{align*} 2(3x-5)=2\cdot 7k. \end{align*} Canceling the integer factor $2$ in this equality gives \begin{align*} 3x-5=7k. \end{align*} Thus $7\mid (3x-5)$, which is exactly \begin{align*} 3x \equiv 5 \pmod{7}. \end{align*} Now $3\cdot 5=15$, and \begin{align*} 15=2\cdot 7+1. \end{align*} Hence \begin{align*} 3\cdot 5 \equiv 1 \pmod{7}. \end{align*} Multiplying $3x\equiv 5\pmod{7}$ by $5$ gives \begin{align*} 5\cdot 3x \equiv 5\cdot 5 \pmod{7}. \end{align*} The left side is $15x$, and since \begin{align*} 15x-x=14x=2x\cdot 7, \end{align*} we have $15x\equiv x\pmod{7}$. The right side is $25$, and \begin{align*} 25=3\cdot 7+4, \end{align*} so $25\equiv 4\pmod{7}$. Therefore \begin{align*} x\equiv 4 \pmod{7}. \end{align*} Thus every solution has the form $x=4+7t$ for some $t\in\mathbb{Z}$. If $t=2q$, then \begin{align*} x=4+7(2q)=4+14q, \end{align*} so $x\equiv 4\pmod{14}$. If $t=2q+1$, then \begin{align*} x=4+7(2q+1)=11+14q, \end{align*} so $x\equiv 11\pmod{14}$. Therefore the two solution classes modulo $14$ are \begin{align*} x\equiv 4 \pmod{14} \end{align*} and \begin{align*} x\equiv 11 \pmod{14}. \end{align*} Both classes really solve the original congruence, since \begin{align*} 6\cdot 4-10=24-10=14 \end{align*} and \begin{align*} 6\cdot 11-10=66-10=56=4\cdot 14. \end{align*} By contrast, the congruence \begin{align*} 6x \equiv 9 \pmod{14} \end{align*} has no solution. If it had a solution, then for some $k\in\mathbb{Z}$ we would have \begin{align*} 6x-9=14k. \end{align*} Rearranging gives \begin{align*} 6x-14k=9. \end{align*} The left side is divisible by $2$, because \begin{align*} 6x-14k=2(3x-7k), \end{align*} but $9$ is not divisible by $2$. This contradiction shows that no integer $x$ satisfies $6x\equiv 9\pmod{14}$. [/example] ## Prime Moduli and Multiplicative Structure Composite moduli contain zero divisors and failed cancellation. Prime moduli remove these obstructions. This is why congruence modulo a prime is the basic finite setting in which arithmetic resembles the arithmetic of rational or [real numbers](/page/Real%20Numbers). The failure of cancellation can be localized to special nonzero residue classes whose product is zero. Naming these classes gives a precise way to measure how far $\mathbb{Z}/n\mathbb{Z}$ is from being a field. [definition: Zero Divisor Modulo $n$] Let $n \in \mathbb{N}$. A nonzero element $\bar{a} \in \mathbb{Z}/n\mathbb{Z}$ is a zero divisor modulo $n$ if there exists a nonzero element $\bar{b} \in \mathbb{Z}/n\mathbb{Z}$ such that \begin{align*} \bar{a}\bar{b} &= \bar{0}. \end{align*} [/definition] Zero divisors are the algebraic trace of factorisation of the modulus. They are precisely what make cancellation fail. [example: Zero Divisors Modulo $12$] In $\mathbb{Z}/12\mathbb{Z}$, multiplication is defined by multiplying integer representatives and then taking the residue class of the product. Using the representatives $3$ and $4$ gives \begin{align*} \bar{3}\bar{4}=\overline{3\cdot 4}. \end{align*} Since \begin{align*} 3\cdot 4=12, \end{align*} we get \begin{align*} \bar{3}\bar{4}=\overline{12}. \end{align*} The class $\overline{12}$ is the same as $\bar{0}$ modulo $12$ because \begin{align*} 12-0=12=1\cdot 12. \end{align*} Thus \begin{align*} \bar{3}\bar{4}=\bar{0}. \end{align*} Neither factor is the zero class modulo $12$. Indeed, \begin{align*} 3-0=3 \end{align*} is not a multiple of $12$, so $\bar{3}\neq \bar{0}$, and \begin{align*} 4-0=4 \end{align*} is not a multiple of $12$, so $\bar{4}\neq \bar{0}$. Therefore $\bar{3}$ and $\bar{4}$ are nonzero classes whose product is zero, and the equality reflects the integer factorization $12=3\cdot 4$ inside $\mathbb{Z}/12\mathbb{Z}$. [/example] The example shows how composite moduli create zero divisors. It raises the structural question: for which moduli do zero divisors disappear completely? Prime moduli answer this because every nonzero residue class is coprime to the modulus. Here $\mathbb{Z}/n\mathbb{Z}$ denotes the [quotient ring](/page/Quotient%20Ring) of integer residue classes modulo $n$, with addition and multiplication performed on representatives and then reduced modulo $n$. An [integral domain](/page/Integral%20Domain) is a commutative ring with $1\neq 0$ in which a product can be zero only if one of its factors is zero. Thus asking whether $\mathbb{Z}/n\mathbb{Z}$ is an integral domain is exactly asking whether nonzero residue classes modulo $n$ can multiply to zero. The obstruction is now concrete: a factorization of $n$ produces nonzero residue classes whose product is $0$ modulo $n$. The next structural criterion identifies exactly when that obstruction is absent, converting the arithmetic condition on $n$ into the ring-theoretic condition that $\mathbb{Z}/n\mathbb{Z}$ has no zero divisors. [quotetheorem:8278] The theorem gives a powerful simplification: modulo a prime, every nonzero coefficient in a linear congruence can be divided away. It also prepares the ground for exponent theorems, because the nonzero residue classes modulo $p$ form a finite multiplicative group. [quotetheorem:731] Fermat's theorem turns multiplicative structure into a computational tool. It reduces large powers modulo a prime and provides a first test for primality, although passing the test does not guarantee primality. [example: Reducing a Large Power] To compute $3^{100}$ modulo $7$, note that $7$ is prime and $7\nmid 3$. By *Fermat's Little Theorem*, \begin{align*} 3^6 \equiv 1 \pmod{7}. \end{align*} The exponent decomposes as \begin{align*} 100=16\cdot 6+4. \end{align*} Therefore \begin{align*} 3^{100}=3^{16\cdot 6+4}. \end{align*} Using the exponent law $a^{r+s}=a^r a^s$ gives \begin{align*} 3^{16\cdot 6+4}=3^{16\cdot 6}3^4. \end{align*} Using the exponent law $a^{rs}=(a^r)^s$ gives \begin{align*} 3^{16\cdot 6}3^4=(3^6)^{16}3^4. \end{align*} Since $3^6\equiv 1\pmod{7}$, repeated multiplication preserves congruence, so \begin{align*} (3^6)^{16}\equiv 1^{16}\pmod{7}. \end{align*} Multiplying both sides by $3^4$ gives \begin{align*} (3^6)^{16}3^4\equiv 1^{16}3^4\pmod{7}. \end{align*} Now \begin{align*} 1^{16}=1 \end{align*} and \begin{align*} 3^4=81. \end{align*} To reduce $81$ modulo $7$, compute \begin{align*} 81=11\cdot 7+4. \end{align*} Thus \begin{align*} 81-4=77=11\cdot 7, \end{align*} so $81\equiv 4\pmod{7}$. Combining the equalities and congruences above, \begin{align*} 3^{100}\equiv 4\pmod{7}. \end{align*} The large power is reduced by replacing blocks of $3^6$ with $1$ modulo $7$, leaving only the residual factor $3^4$. [/example] Composite moduli require a more flexible version of Fermat's theorem. The correct exponent is governed by the number of units modulo $n$, since only units participate in the multiplicative group where finite-group exponent arguments apply. [definition: Euler Totient Function] Euler's totient function is the function $\varphi: \mathbb{N}\to\mathbb{N}$ that sends each positive integer $n$ to the number of units modulo $n$: \begin{align*} \varphi(n) &= |(\mathbb{Z}/n\mathbb{Z})^\times|. \end{align*} [/definition] Equivalently, $\varphi(n)$ counts integers $k \in \{1,\ldots,n\}$ with $\gcd(k,n)=1$. The group interpretation explains why $\varphi(n)$ appears as an exponent in modular multiplication. For composite $n$, not every nonzero residue can be multiplied and divided as if it belonged to a field, so a prime-modulus exponent rule cannot apply to all residues. The natural question is whether the prime-modulus power reduction survives after restricting to residues that are units modulo $n$. Euler's theorem gives exactly this replacement: it uses the size of the unit group as the exponent. [quotetheorem:732] Euler's theorem emphasizes the recurring principle: in congruence arithmetic, coprimality is the condition that permits division-like behavior. It is also one of the main tools for reducing high powers modulo composite integers. ## Systems of Congruences A single congruence records one modular shadow of an integer. Several congruences record several shadows at once. The central question is whether these shadows can come from the same integer, and whether that integer is determined modulo a larger modulus. ### Patching Residues To discuss several modular conditions at once, we need a compact way to name the data. A system of congruences is the basic object whose solvability asks whether separate remainders are compatible. [definition: System of Congruences] A system of congruences is a finite collection of congruences \begin{align*} x &\equiv a_i \pmod{n_i}, \quad i=1,\ldots,k, \end{align*} where $a_i \in \mathbb{Z}$ and $n_i \in \mathbb{N}$. [/definition] The simplest and most important case is when the moduli have no common factors with each other. To state this independence cleanly, we isolate the condition that every pair of moduli shares no divisor larger than $1$. [definition: Pairwise Coprime Integers] Integers $n_1,\ldots,n_k \in \mathbb{N}$ are pairwise coprime if \begin{align*} \gcd(n_i,n_j) &= 1 \end{align*} for all $i,j \in \{1,\ldots,k\}$ with $i\neq j$. [/definition] Pairwise coprimality says that no prime obstruction is shared between two moduli. Under this condition, a list of local congruence conditions should patch into a unique global congruence class modulo the product. The [Chinese remainder theorem](/theorems/734) makes that expectation precise. [quotetheorem:734] The Chinese [remainder theorem](/theorems/1707) is a reconstruction theorem. It says that, for coprime moduli, knowing an integer modulo each $n_i$ is the same as knowing it modulo their product. [example: Reconstructing from Two Remainders] Solve the system \begin{align*} x \equiv 2 \pmod{3} \end{align*} and \begin{align*} x \equiv 3 \pmod{5}. \end{align*} The first congruence means that $3\mid (x-2)$, so there is an integer $t$ such that \begin{align*} x=2+3t. \end{align*} Substituting this into the second congruence gives \begin{align*} 2+3t \equiv 3 \pmod{5}. \end{align*} Subtracting $2$ from both sides gives \begin{align*} 3t \equiv 1 \pmod{5}. \end{align*} To solve this congruence, compute \begin{align*} 3\cdot 2=6=1\cdot 5+1. \end{align*} Thus \begin{align*} 3\cdot 2 \equiv 1 \pmod{5}. \end{align*} Multiplying $3t\equiv 1\pmod{5}$ by $2$ gives \begin{align*} 2\cdot 3t \equiv 2\cdot 1 \pmod{5}. \end{align*} The left side is $6t$, and \begin{align*} 6t-t=5t, \end{align*} so $6t\equiv t\pmod{5}$. Therefore \begin{align*} t\equiv 2 \pmod{5}. \end{align*} Hence $t=2+5q$ for some $q\in\mathbb{Z}$. Substituting back into $x=2+3t$ gives \begin{align*} x=2+3(2+5q). \end{align*} Expanding, \begin{align*} x=2+6+15q. \end{align*} Thus \begin{align*} x=8+15q. \end{align*} So every solution satisfies \begin{align*} x\equiv 8 \pmod{15}. \end{align*} Conversely, if $x=8+15q$, then \begin{align*} x-2=6+15q=3(2+5q), \end{align*} so $x\equiv 2\pmod{3}$. Also, \begin{align*} x-3=5+15q=5(1+3q), \end{align*} so $x\equiv 3\pmod{5}$. Therefore the solution set is exactly the single congruence class \begin{align*} x\equiv 8 \pmod{15}. \end{align*} The two separate remainder conditions reconstruct one residue class modulo $3\cdot 5=15$. [/example] ### Shared Factors When the moduli are not coprime, compatibility conditions appear. The same integer cannot have remainders that disagree modulo a common divisor. For example, congruences modulo $4$ and modulo $6$ both impose a parity condition, because the moduli share the factor $2$. If the two prescribed remainders have different parity, no integer can satisfy both congruences. The general condition is that the two remainders must agree modulo every common divisor, equivalently modulo the greatest common divisor of the moduli. [quotetheorem:9338] This result explains the exact failure mode for non-coprime moduli. Shared factors force shared residue information. [example: Incompatible Remainders] The system \begin{align*} x &\equiv 1 \pmod{4} \end{align*} and \begin{align*} x &\equiv 2 \pmod{6} \end{align*} has no solution. Suppose, for contradiction, that some integer $x$ satisfies both congruences. The first congruence means $4\mid (x-1)$, so there is an integer $r$ such that \begin{align*} x-1 &= 4r \end{align*} and therefore \begin{align*} x &= 1+4r. \end{align*} The second congruence means $6\mid (x-2)$, so there is an integer $s$ such that \begin{align*} x-2 &= 6s \end{align*} and therefore \begin{align*} x &= 2+6s. \end{align*} Equating the two expressions for $x$ gives \begin{align*} 1+4r &= 2+6s. \end{align*} Subtracting $1$ and $6s$ from both sides gives \begin{align*} 4r-6s &= 1. \end{align*} Factoring the left-hand side, \begin{align*} 4r-6s &= 2(2r-3s). \end{align*} Hence \begin{align*} 2(2r-3s) &= 1. \end{align*} The left-hand side is divisible by $2$, while $1$ is not divisible by $2$, a contradiction. Thus no integer $x$ satisfies both congruences; the shared factor $\gcd(4,6)=2$ already forces incompatible parity conditions. [/example] ## Congruences as Tests for Diophantine Equations Congruences are often used negatively: reduce an equation modulo $n$ and show that no residue class solution exists. This method cannot prove existence over the integers, but it can disprove existence with striking efficiency. A Diophantine equation over $\mathbb{Z}$ has infinitely many possible inputs, but a congruence modulo $n$ has only finitely many residue choices. If the finite modular problem has no solution, then the original integer problem cannot have a solution whose residues reduce to it. Before trying to solve an equation in integers, we can ask a simpler question: what would any solution look like after reducing all variables modulo $n$? This gives a way to disprove solvability by checking finitely many residue classes. Here $\mathbb{Z}[x_1,\ldots,x_k]$ means the set of polynomials in the variables $x_1,\ldots,x_k$ with integer coefficients. [definition: Congruence Obstruction] Let $F(x_1,\ldots,x_k) \in \mathbb{Z}[x_1,\ldots,x_k]$ and let $n \in \mathbb{N}$. A congruence obstruction modulo $n$ to the equation \begin{align*} F(x_1,\ldots,x_k) &= 0 \end{align*} is the nonexistence of residue classes $\bar{x}_1,\ldots,\bar{x}_k \in \mathbb{Z}/n\mathbb{Z}$ satisfying \begin{align*} F(\bar{x}_1,\ldots,\bar{x}_k) &= \bar{0} \end{align*} in $\mathbb{Z}/n\mathbb{Z}$. [/definition] A congruence obstruction is a certificate of impossibility. If an integer solution existed, reducing its coordinates modulo $n$ would give a modular solution. Therefore, if no modular solution exists modulo some $n$, then no integer solution exists. This is the obstruction principle used in elementary congruence arguments. The principle is powerful because a finite search modulo $n$ can rule out an infinite search over $\mathbb{Z}^k$. The art lies in choosing a modulus that exposes the obstruction. [example: No Square is $3$ Modulo $4$] Let $m\in\mathbb{Z}$. Dividing $m$ by $4$, its remainder is one of $0,1,2,3$, so $m$ is congruent modulo $4$ to exactly one of those four integers. It is therefore enough to square these four representatives and reduce the result modulo $4$. \begin{align*} 0^2=0 \end{align*} Since $0-0=0=0\cdot 4$, we have $0^2\equiv 0\pmod{4}$. \begin{align*} 1^2=1 \end{align*} Since $1-1=0=0\cdot 4$, we have $1^2\equiv 1\pmod{4}$. \begin{align*} 2^2=4 \end{align*} Since $4-0=4=1\cdot 4$, we have $2^2\equiv 0\pmod{4}$. \begin{align*} 3^2=9 \end{align*} Since $9-1=8=2\cdot 4$, we have $3^2\equiv 1\pmod{4}$. Thus the only possible square residues modulo $4$ are $0$ and $1$. Because $3-0=3$ is not a multiple of $4$, and $3-1=2$ is not a multiple of $4$, the residue $3$ is neither $0$ nor $1$ modulo $4$. Hence no square is congruent to $3$ modulo $4$, so any equation forcing $x^2\equiv 3\pmod{4}$ has no integer solution. [/example] Congruence obstructions also explain why some equations have no solutions even though size estimates do not rule them out. The next example uses the small list of square residues modulo $4$ to rule out a two-variable equation. [example: A Diophantine Obstruction] The equation \begin{align*} x^2+y^2 = 3 \end{align*} has no integer solution. To see this, first list the possible residues of a square modulo $4$. Every integer is congruent modulo $4$ to exactly one of $0,1,2,3$, so it is enough to square these four representatives: \begin{align*} 0^2 = 0. \end{align*} Thus $0^2\equiv 0\pmod{4}$. Also, \begin{align*} 1^2 = 1, \end{align*} so $1^2\equiv 1\pmod{4}$. Next, \begin{align*} 2^2 = 4 = 1\cdot 4+0, \end{align*} so $2^2\equiv 0\pmod{4}$. Finally, \begin{align*} 3^2 = 9 = 2\cdot 4+1, \end{align*} so $3^2\equiv 1\pmod{4}$. Therefore any square is congruent to either $0$ or $1$ modulo $4$. Hence the sum $x^2+y^2$ can have only the following residues modulo $4$: \begin{align*} 0+0=0, \end{align*} \begin{align*} 0+1=1, \end{align*} \begin{align*} 1+0=1, \end{align*} \begin{align*} 1+1=2. \end{align*} So $x^2+y^2$ is congruent modulo $4$ only to $0$, $1$, or $2$. If integers $x,y$ satisfied $x^2+y^2=3$, then reducing both sides modulo $4$ would give \begin{align*} x^2+y^2 \equiv 3 \pmod{4}. \end{align*} But $3$ is not congruent to $0$, $1$, or $2$ modulo $4$, since \begin{align*} 3-0=3, \end{align*} \begin{align*} 3-1=2, \end{align*} and \begin{align*} 3-2=1 \end{align*} are not multiples of $4$. This contradiction rules out all integer solutions; the equation fails because its two sides have incompatible residues modulo $4$. [/example] The limitation is just as important as the method. Absence of a congruence obstruction for a few moduli does not produce an integer solution. It only says those particular finite tests have not ruled one out. [remark: Local Tests Are Not Existence Proofs] Solvability modulo $n$ for many values of $n$ is evidence, not a full integer solution. In deeper number theory, the gap between local congruence information and global integer or rational solutions becomes a central theme. [/remark] ## Beyond and Connected Topics Congruence is the entry point to Modular Arithmetic, where residue classes are treated as algebraic objects in their own right. The ring $\mathbb{Z}/n\mathbb{Z}$ supports addition and multiplication, and the structure of its units controls division, cancellation, and exponentiation. Prime moduli lead naturally to finite fields. The field $\mathbb{Z}/p\mathbb{Z}$ is the simplest example of a finite field, and it is the setting for Fermat's little theorem, polynomial congruences, and many constructions in algebra and number theory. Systems of congruences lead to the Chinese remainder theorem, which reappears throughout algebra. In ring theory it becomes a statement about quotient rings by coprime ideals; in number theory it decomposes arithmetic modulo a composite integer into arithmetic modulo prime powers. Congruence methods are also the first local tools for Diophantine Equation. Reducing equations modulo primes and prime powers leads toward quadratic residues, $p$-adic numbers, local-global questions, and the arithmetic of number fields, as developed further in [Cambridge II Number Theory](/page/Cambridge%20II%20Number%20Theory). For the group-theoretic side, the unit group $(\mathbb{Z}/n\mathbb{Z})^\times$ connects congruence to [Group](/page/Group), orders of elements, cyclic groups, and group actions. This is one reason congruence sits naturally between elementary number theory and algebra. Several standard refinements come next. Modular arithmetic supplies the general language for congruence classes, reduced residue systems give concrete representatives for $(\mathbb{Z}/n\mathbb{Z})^\times$, orders modulo $n$ measure when powers return to $1$, primitive roots ask when the whole unit group is generated by one residue class, and [Diophantine equations](/page/Diophantine%20Equations) provide the broader setting in which congruence obstructions rule out integer solutions. ## References Androma, [Cambridge IA Numbers and Sets](/page/Cambridge%20IA%20Numbers%20and%20Sets). Androma, [Cambridge II Number Theory](/page/Cambridge%20II%20Number%20Theory). Androma, [Cambridge II Number Fields](/page/Cambridge%20II%20Number%20Fields). Androma, [Cambridge IA Groups](/page/Cambridge%20IA%20Groups). Androma, [Group](/page/Group). Hardy and Wright, *An Introduction to the Theory of Numbers* (1979). Ireland and Rosen, *A Classical Introduction to Modern Number Theory* (1990). Niven, Zuckerman, and Montgomery, *An Introduction to the Theory of Numbers* (1991).