Motivation
A congruence records one residue class, but combining several congruences is not always possible. With shared factors, two prescribed remainders may disagree on information that both moduli retain. Even when a solution exists, multiplying the moduli can overstate the true period.
The right invariant is a complete solution class: after processing some constraints, every solution and only a solution is congruent to one representative modulo one positive period. Extended Euclid supplies a compatibility test and a correction that merges the next condition. A separate prime-power argument explains why checking all pairs is also sufficient for a finite system.
The mathematics here is over exact integers; neither the proofs nor the algorithm rely on guessing within a small range of candidate solutions.
Definitions
Definition 4.2.1
(Congruence and a complete solution class)
For a positive integer , write when divides . This relation is compatible with addition and multiplication. Modulus one imposes no restriction, since every integer difference is divisible by one.
A complete solution class means precisely the integers for , with . Its canonical representative satisfies . A linear congruence is , where may be signed or zero.
The gcd of is the positive gcd of their absolute values. The least common multiple of positive is their smallest positive common multiple and equals . We use Bézout's identity and the cofactor inverse already proved in the integer-algorithm notes. The least common multiple of an empty family is taken to be one, matching an empty system's lack of restrictions. An inverse modulo one need not be invoked: a residue requirement modulo one has a single, unrestricted class.
Definition 4.2.2
(Pairwise compatibility of a finite remainder system)
A finite family , with each , is pairwise compatible when
for every pair of indices. Pairwise coprimeness makes these conditions automatic, but compatibility does not require the moduli to be coprime.
Theorem/Proposition
Theorem 4.2.3
(All solutions of one linear congruence)
Let . The congruence is solvable exactly when divides . If it is solvable, its integer solutions form one class modulo , and therefore exactly distinct classes modulo .
When , a representative is obtained by multiplying by the inverse of modulo . When , every integer is a solution and representative zero suffices.
Theorem 4.2.4
(Constructive merge for two arbitrary positive moduli)
The system , is solvable exactly when divides . If solvable, it has a unique solution class modulo .
Write . If , choose satisfying by its cofactor inverse. If , take . Then , reduced modulo , is a canonical solution representative. This procedure needs gcd and Bézout coefficients, not factorization of the moduli.
Theorem 4.2.5
(Pairwise compatibility is sufficient for every finite system)
For positive moduli, a finite remainder system is solvable if and only if it is pairwise compatible. When solvable its complete solution set is one class modulo the least common multiple of all its moduli. Sequential application of the two-modulus merge constructs that class, or correctly rejects an inconsistent system.
Uniqueness here is uniqueness of the residue class modulo the least common multiple. It does not mean one integer solution, and it does not imply uniqueness modulo the product when shared factors are present.
Proof sketch or proof idea
Proof
(Solving one linear congruence)
If is divisible by , then every common divisor of divides , proving necessity for the linear congruence. When , division gives the equivalent congruence . The reduced coefficient and modulus are coprime, so for modulus greater than one the inverse exists by Bézout. Multiplying gives a unique class modulo ; conversely that class satisfies the original equation after multiplication by .
If the reduced modulus is one, the divided congruence imposes no condition, giving all integers. In either case write the solution class . Within a full interval of consecutive residues it has exactly the distinct values obtained by adding zero through copies of . Differences between these are not multiples of unless the copies agree. This proves the count, including .
Proof
(Merging two congruences, and the sequential solver)
For the two-modulus merge, every solution of the first condition has form . The second condition becomes . The linear-congruence theorem makes this solvable exactly under the stated gcd condition. Dividing by gives the cofactor equation for , with coprime . Its unique class modulo turns into one class for modulo . This also proves all-solution uniqueness, not merely correctness of the constructed representative.
For a sequential algorithm, begin with representative zero modulo one. Maintain that the processed constraints have exactly the current solution class. Merging it with the next congruence produces precisely their intersection by the theorem; failure means that intersection is empty. Thus induction proves correctness of both acceptance and rejection. If the old representative is normalized and the correction satisfies , then already; an explicit final reduction also handles unnormalized input remainders.
Proof X-ray
The merge invariant includes every possible solution
Checking the new representative's residues establishes feasibility only. The substitution and the unique cofactor class also prove that no other solution classes have been lost. Keeping that reverse direction is what makes a later failed merge certify global inconsistency rather than just failure of one selected candidate.
Proof
(Pairwise compatibility through prime powers)
For the pairwise criterion, necessity follows because a common solution makes every difference divisible by both moduli's gcd. We prove sufficiency using prime-power factors. A prime is an integer at least two with no positive divisors other than one and itself. All prime factors here are positive. The needed factorization fact is elementary: existence follows by induction, splitting any composite integer into smaller factors; uniqueness follows from the prime-divisor lemma. That lemma follows from Bézout: if a prime divides a product but not its first factor, its gcd with that factor is one, so multiplying a Bézout identity by the second factor shows it divides the second. Repeating this argument identifies a prime on the other side of any competing factorizations, then cancellation proves uniqueness. The integer one has an empty factorization.
Let be the least common multiple. For every prime power occurring with maximal exponent among the moduli, choose an index attaining that exponent and prescribe the corresponding remainder modulo . These prime powers are pairwise coprime, so repeated use of the already proved merge gives one class modulo their product .
For any original modulus and each of its prime powers , compatibility with the chosen maximal-exponent index makes its remainder agree with the chosen remainder modulo . The constructed integer therefore satisfies every prime-power factor of that original modulus, and hence their coprime product. It satisfies all original congruences. If , all moduli are one and every integer works, matching the same conclusion.
Finally, two common solutions differ by a multiple of every modulus, hence of every maximal prime power and their product . Conversely adding any multiple of preserves all congruences. This proves the complete class and the finite-system theorem. Prime factorization explains the criterion but is not required by the sequential implementation.
Worked examples
Worked example 4.2.6
(A noninvertible coefficient can still admit solutions)
Solve . The gcd is two and divides eight. Divide to get . Since three is an inverse of seven modulo ten, . Thus the two classes modulo twenty are two and twelve. Substitution gives residues eight in both cases. Trying to invert fourteen modulo twenty would fail, but would not prove the original congruence inconsistent.
Worked example 4.2.7
(A shared factor reduces the period)
Solve and . Their gcd is three and the difference of remainders is three, so they are compatible. Substituting gives , hence . The complete solution is . In contrast replacing five by four gives a remainder difference two, which is not divisible by three, and no solution exists.
Worked example 4.2.8
(A third condition changes the period without changing the smallest representative)
Add to the compatible pair. Merge with it. The gcd is two and the difference is minus ten; the reduced correction equation is , whose class is zero. Hence the representative remains fourteen and the period becomes ninety.
The product of the three original moduli is , not the true period. There are six solutions modulo that product, namely for . A correct representative alone would not justify declaring uniqueness modulo .
Algorithm size and the role of factorization
Normalize each input remainder modulo its positive modulus. At every merge the period is a least common multiple and at most the product of the processed moduli. Its binary length is therefore at most the sum of their binary lengths, up to a constant. Correction residues can also be chosen within their reduced modulus, keeping the constructed representative within the new period.
Extended Euclid and exact arithmetic thus operate on numbers of polynomially controlled bit length. A sequential compatibility solver does not need to enumerate integers up to the period, and a large period's numerical magnitude is not its written input length. The factorization proof of pairwise sufficiency should not be mistaken for a requirement to factor every input before applying the gcd-based algorithm.
Concept lensAlgebraic
Compatibility compares information retained by both moduli
A shared prime power constrains the same part of the unknown residue twice. Its two prescriptions must agree at their common resolution. The least common multiple retains each required prime exponent once, explaining the final period. The gcd detects the overlap without requiring its prime factors to be computed.
Common mistakes
Common mistake
(Dividing the coefficients but not the modulus)
From one may not pass to . That congruence has the single class , because inverts modulo ; it loses the solution , for which but . Under the proved condition , divide the coefficient, the right side and the modulus by together. This gives and both classes and modulo .
Common mistake
(The product of the moduli is not the period)
For and the solutions are , so and are both solutions although they are distinct modulo . The coprime period is correct only when ; in general the period is .
Common mistake
(Compatible is not the same as coprime)
The moduli and share the factor , yet the same system is solvable because . Coprime moduli make every pair compatible, but the converse fails, so rejecting a system because discards solvable systems. In the modulus-one branch the constraint is already vacuous, and no modular inverse is to be chosen there.
Counterexample mode
Lack of an inverse is not lack of a solution
The congruence has no coefficient inverse modulo four, yet its solutions are all odd integers. Dividing by the gcd gives . The failed inverse test says multiplication is not a bijection of all four residue classes; it does not say its image omits the requested right side.
Summary
A gcd characterizes solvability of one linear congruence and counts all residue solutions. The same theorem gives an exact noncoprime remainder merge, preserving the full processed solution class. Prime-power compatibility proves that all pairwise consistency checks suffice, while the practical sequential algorithm uses only gcd and inverses and returns the least-common-multiple period.
Exercises
Quick check
(Classify the solutions of for a positive . Include , and count the classes modulo when the congruence is solvable.)
Apply the gcd condition without inventing an inverse of zero.
Solution · Answer
Here . Solvability means . If so, every integer is a solution, a single class modulo one and exactly classes modulo . If not, there is no solution. When , every is divisible by it and every integer works. The theorem's reduced modulus is one, so its explicit vacuous branch applies without any inverse calculation.
Quick check
(Solve and . How many solution classes are there modulo the product ?)
Give the complete smallest-period class first.
Solution · Answer
Write . The second condition gives , hence . Thus and . The two product-modulus classes are nine and twenty-one. Each satisfies both original constraints, and their common twelve-step period is the least common multiple of four and six.
Quick check
(Solve , and . Check pairwise compatibility and verify a canonical representative.)
Merge twice and give the final least common multiple.
Solution
The pairwise gcds are four, two and six, and the corresponding remainder differences are four, ten and six, all divisible as required. First merge three modulo eight with seven modulo twelve: substituting gives , so .
Now put . The final congruence gives , hence and . Therefore . Its residues modulo eight, twelve and eighteen are three, seven and thirteen respectively. The period seventy-two is their least common multiple, and sixty-seven lies in its canonical interval.