Motivation
A residue records exactly the part of an integer visible after division by a fixed modulus. Working with residues can shorten a calculation, but it changes cancellation rules. The equation is solvable even though has no inverse modulo . Understanding that example leads to a general solvability theorem and then to the reconstruction of an integer from several remainders.
Definitions
Definition 2.1.1
(Congruence and units)
Fix an integer . The relation means . The residue class is the set of all integers congruent to . Addition and multiplication of classes are induced by integer arithmetic. A unit is a class having a multiplicative inverse; is a unit exactly when .
The operations are well-defined because replacing by changes their sum and product by multiples of . The inverse criterion follows from Bézout: gives ; conversely an inverse equation says for some integers . Congruence is an equivalence relation, so the classes represented by partition the integers.
Theorem/Proposition
Theorem 2.1.2
(Linear congruence theorem)
Let . The congruence is solvable exactly when . If solvable, it has exactly distinct solutions modulo . If is one solution, all solutions are , for .
Theorem 2.1.3
(Chinese remainder theorem and compatibility)
For pairwise coprime integers , any system has exactly one solution class modulo . For two arbitrary moduli , a system with residues is solvable exactly when ; when solvable it is unique modulo .
Proof sketch or proof idea
Proof
(Bézout, then a reduced modulus)
The linear congruence is the integer equation , so Bézout proves the solvability criterion. After division by , the coefficient is invertible modulo . Thus there is a unique solution class modulo , which splits into precisely classes modulo . Two listed representatives differ by ; this is divisible by exactly when , proving distinctness.
Proof
(Selectors for coprime moduli; substitution for two moduli)
For the coprime theorem set and choose with . Then has every prescribed residue: all summands except the th vanish modulo . Two solutions differ by an integer divisible by every , hence by , using pairwise coprimality and prime factorization.
For two general moduli put . The second equation becomes , solvable exactly under the stated gcd condition. The difference of any two solutions is divisible by both , exactly the condition of being divisible by their lcm. This also proves uniqueness with the correct modulus.
Proof X-ray
Where pairwise coprimality is spent
The coprime proof uses the hypothesis twice, for two different purposes. Existence needs each to be a unit modulo ; this holds because shares no prime with any other , so . The selector is then modulo and modulo every other modulus, and the solution is just the combination . Uniqueness needs the passage from “divisible by each ” to “divisible by ”, which is again exactly pairwise coprimality.
For moduli and both steps fail visibly: has , so no selector for the modulus exists, and is divisible by and but not by . The two-modulus argument repairs both at once by reducing to the first theorem. Substituting gives , a linear congruence with . Its solvability criterion becomes the compatibility condition, and its solutions form one class modulo , so is determined modulo .
Worked examples
Worked example 2.1.4
(A nonunit coefficient)
For , divides . Division of the entire divisibility statement by gives , hence . The three solutions modulo are . Dividing while keeping modulus would have changed the problem.
Worked example 2.1.5
(Reconstructing from coprime residues)
Solve , , . With , use and inverses respectively. The construction gives . Indeed has the required three remainders.
Worked example 2.1.6
(Compatibility comes before reconstruction)
The system , is compatible because . Substituting gives , so and . Changing the second residue to makes the system impossible: one equation requires an odd integer, the other an even integer.
Congruence preserves operations, but not every inference
Congruence allows integers to be replaced by simpler representatives because addition and multiplication respect the equivalence relation. Subtraction is included, since negatives are compatible with congruence. Division is different: an operation can be well-defined only if the divisor has an inverse or if the modulus is adjusted to account for the missing information. This distinction explains why modular arithmetic can resemble ordinary arithmetic in a long calculation and then fail at one apparently harmless cancellation.
To derive the adjusted rule directly, suppose a product difference is divisible by the modulus. Divide the coefficient and the modulus by their gcd. The reduced coefficient is now coprime to the reduced modulus, so Bézout permits cancellation there. The conclusion is a congruence with the reduced modulus. Thus cancellation is not mysterious: it is ordinary divisibility plus one carefully stated coprimality fact. The loss of modulus records exactly the ambiguity introduced by a nonunit coefficient.
Counterexample mode
Canceling a nonunit loses information
The false claim is that every nonzero coefficient can be canceled while keeping the modulus. Modulo six, multiplying residues one and four by two gives the same residue, even though the original residues differ. The repaired statement cancels only units, or changes the modulus by dividing it by the gcd with the coefficient. Nonzero is a weaker condition than invertible when the modulus is composite.
The gcd condition for a linear congruence therefore has two distinct roles. It decides whether the target lies in the image of multiplication by the coefficient, and it counts how many source classes share that image. An image class is reached by exactly the number of solutions of the homogeneous equation. Translating one solution by a homogeneous solution preserves the target, and subtracting any two solutions gives a homogeneous solution. This gives a conceptual explanation for why every solvable target has the same number of preimages.
Counting the image as well as the solutions
There are as many attainable target classes as the modulus divided by the gcd. Indeed, an attainable target must be divisible by that gcd, and the solvability theorem says every such target is attained. Each attainable target has as many preimages as the gcd itself. Multiplying the image size by this common fiber size recovers the total number of source classes. This is a useful independent check on the theorem's solution count.
For example, multiplication by six modulo fifteen can reach exactly the five classes represented by zero, three, six, nine and twelve. Each has three preimages. The fifteen source classes have therefore been partitioned into five fibers of equal size. Asking for an inverse to this map would be impossible: three distinct inputs give the same output. After reducing the modulus to five and the coefficient to two, the map becomes bijective, which is precisely what the computation in the first example used.
The reconstruction terms act as selectors
The Chinese remainder construction can be understood before calculating any target residues. For each modulus, build one number that is one modulo that modulus and zero modulo all the others. Such a number selects one coordinate of a residue tuple. Multiplying it by the desired coordinate and adding all these contributions produces the required integer. The construction is linear in the residue data, so the same selector terms may be reused for many different systems with the same moduli.
This viewpoint also explains uniqueness. If all coordinates of an integer vanish, it is divisible by every modulus. Pairwise coprimality then makes it divisible by their product. Thus the only class mapping to the zero tuple is the zero class modulo the product. Existence constructs a class for every tuple; uniqueness says distinct classes cannot represent the same tuple. Together they describe an exact correspondence, rather than merely a recipe that happens to produce a solution.
Concept lensStructural
One residue as a tuple of local residues
For pairwise coprime moduli, reduction sends a residue modulo the product to its tuple of residues modulo the factors. It preserves addition and multiplication coordinate by coordinate. The Chinese remainder theorem proves this map is a bijection. A large modular calculation may therefore be performed separately in smaller moduli and reconstructed afterwards, with no approximation.
A consequence is the factorization of unit counts for coprime moduli. An integer is coprime to a product of coprime factors exactly when it is coprime to each factor. Under the residue-tuple correspondence, units are therefore exactly the tuples of units. Counting these tuples gives the multiplicativity of Euler's function in the coprime case. This connects a reconstruction theorem to an arithmetic function that initially appears to be only a counting definition.
Compatibility is shared information, not a technical nuisance
When two moduli have a common divisor, both congruences already prescribe a remainder modulo that common divisor. Those prescriptions must agree. This proves necessity of the compatibility condition without any algebraic manipulation. The linear-congruence reduction then proves the converse: agreement on the shared information is enough for two moduli. The lcm is the correct uniqueness modulus because it combines all prime powers required by either modulus without counting an overlapping requirement twice.
To see the distinction concretely, take one modulus dividing the other. A residue modulo the larger modulus already determines its residue modulo the smaller one. The smaller congruence either agrees and contributes no new information, or disagrees and makes the system inconsistent. Multiplying the two moduli in this situation would introduce artificial extra classes. The lcm simply retains the larger modulus, exactly as the information interpretation predicts.
For several moduli that are not pairwise coprime, one can merge the congruences two at a time. After a successful merge, record the resulting residue and lcm modulus, then merge the next condition using the two-modulus theorem. At each stage the recorded congruence represents exactly the solutions of all conditions processed so far. If compatibility fails, the original system has no solution. This procedure needs no unsupported product formula and handles redundant conditions naturally.
Yes: a system is solvable exactly when every two of its congruences are compatible.
A natural next question
Is pairwise compatibility enough for many moduli?
Yes: a system is solvable exactly when every two of its congruences are compatible.
Necessity is the two-modulus case. For sufficiency, split each condition into its prime-power parts. For a fixed prime , keep a condition modulo with the largest exponent, coming from . Any other part modulo , from , has , so it already follows. The kept conditions use distinct primes, and the coprime theorem solves them.
Checking a reconstructed answer
A completed solution should contain a representative and its uniqueness modulus. Substitute the representative into every original congruence. This verifies the construction survived arithmetic simplification. Then justify the modulus by considering differences of two solutions. The substitution check alone does not show completeness; many individual integers may satisfy the system. Conversely, a correct uniqueness modulus without a representative does not establish existence. The theorem supplies both, and a written solution should make their roles visible.
A nonlinear calculation can also split into coordinates
The residue correspondence preserves multiplication, so it can also organize polynomial equations. For instance, solving a square equal to one modulo a product of two distinct odd primes amounts to solving the same equation in each prime modulus. In each field there are exactly two choices, one and minus one: factoring the square difference and using the absence of zero divisors proves this. The Chinese remainder theorem combines every pair of choices into exactly one residue modulo the product. Consequently there are four roots modulo that product, even though the polynomial has degree two. The field root bound was applied only in each prime coordinate, where its hypothesis holds. This example shows both the strength of reconstruction and the danger of transferring a field theorem unchanged to a composite modulus. It also distinguishes counting solutions from listing them: the four coordinate choices establish the count, while the reconstruction formula computes their actual representatives.
Common mistakes
Common mistake
(Canceling a coefficient that is not a unit)
From one may cancel and keep only when is a unit. In general, the valid conclusion is . For example , but .
Common mistake
(The product modulus needs pairwise coprimality)
The product modulus in the Chinese remainder theorem also requires pairwise coprimality. For moduli the natural uniqueness modulus is , not : a solution class modulo splits into two classes modulo . State whether an answer is an integer representative or an entire residue class.
Common mistake
(A quadratic congruence can have more than two roots)
The bound “a polynomial of degree two has at most two roots” is a theorem about fields, so it applies modulo a prime but not modulo a composite number. Modulo , the residues all square to : for instance and . Apply the root bound in each prime coordinate and combine with the Chinese remainder theorem.
Summary
The gcd controls division in a congruence. Coprime moduli allow arbitrary local residues; overlapping moduli impose compatibility. The reconstruction formula provides existence, while divisibility of differences gives uniqueness.
Exercises
Quick check
(Find every solution of 14x congruent to 8 modulo 30.)
Reduce the coefficient and modulus together.
Solution · Answer
The gcd is , so divide to get . Since , . Thus ; direct multiplication gives remainder in each case.
Quick check
(Solve congruent to 2 modulo 9 and congruent to 5 modulo 12, or prove that no solution exists.)
Check the gcd before substitution.
Solution · Answer
Since divides , write . Then , or , so . Therefore . Its remainders are and , and uniqueness is modulo the lcm .
Quick check
(Find every residue modulo with .)
Solve modulo and modulo first, then combine.
Solution · Answer
Since and are primes, forces in each coordinate, because modulo a prime forces a factor to vanish. The Chinese remainder theorem combines the four sign choices into four classes modulo : , , and . Check: and . The answer is .