One integer, two pieces of information
Knowing a number's remainder modulo four does not usually determine its remainder modulo five. But two compatible remainder requirements can describe one residue class modulo a larger number. We will construct that class, identify exactly when it exists, and explain what the construction means for quotient rings.
Definition 7.1.1
(Congruence and residue class)
Throughout, are positive integers and are integers. The notation means . It describes a whole residue class, not just a number between zero and . The least common multiple is positive.
The coprime construction
Theorem 7.1.2
(Two coprime moduli)
If , then for any the system
has a solution. Any two solutions are congruent modulo .
Proof
(Two selectors from Bézout's identity)
Choose integers with . Put
Modulo , and . Modulo , and . Thus meets both requirements: each selector keeps one residue and removes the other.
If are two solutions, both and divide . Coprimality implies : for instance, writing , the divisibility and give . Conversely, adding a multiple of preserves both congruences. Hence all solutions form precisely one residue class modulo .
Proof X-ray
Where coprimality is spent
Coprimality is used twice, for two different jobs. Existence needs the identity : it turns the number into a sum of a multiple of and a multiple of , and that splitting is what lets each selector be on one side and on the other. Uniqueness needs the cancellation , which is the only place where is used on divisibility rather than on a linear combination. The idea that does the work is that is built from the two requirements separately, with no search. Without coprimality there are no , and the next section shows what remains.
The coefficients need not be unique. Different choices may yield different integers , but the uniqueness argument proves they represent the same class modulo .
Worked example 7.1.3
(Construct the solution modulo twenty)
Solve , . Since , choose . The selectors are and , so
Check: has remainder 2 modulo 4 and remainder 3 modulo 5. Every solution is for an integer ; it is not a single integer.
When the moduli share a factor
Theorem 7.1.4
(Compatibility for arbitrary positive moduli)
Let . The system has a solution if and only if . When it is solvable, its solutions form one residue class modulo .
Proof
(Reduce to a coprime linear congruence)
If solves both conditions, divides both and , hence it divides their difference . This proves necessity.
Conversely suppose . Write and , where . Set . The second condition becomes
By Bézout, choose with . Then satisfies , and solves both original conditions. This argument also covers : congruence modulo one is automatic.
If are solutions, their difference is divisible by both and . Write it as . Then , so . Coprimality gives , hence divides the difference. Conversely every multiple of this least common multiple is divisible by both moduli. Therefore it is exactly the modulus of the solution class.
Worked example 7.1.5
(A shared factor can permit or forbid a solution)
For and , the gcd is 2 and divides . The integer 14 satisfies both conditions, so the complete answer is .
By contrast, and have no common solution: the first makes odd, the second makes it even. Equivalently, their residue difference 1 is not divisible by .
Worked example 7.1.6
(One modulus divides the other (an edge case))
Take and . Here divides , so a solution exists. With , we have , and the reduced congruence modulo is automatic. The solutions form one class modulo , namely : the second requirement adds no information, because already.
Counterexample mode
The product is not always the correct period
Claim: the solutions of a compatible system form a single class modulo . For , the true period is , not . Both 14 and 38 solve it, but they differ by 24 and are not congruent modulo 48. Saying only would omit valid solutions. The modulus is correct exactly when .
A product-ring interpretation
Theorem 7.1.7
(Chinese remainder isomorphism)
For coprime , the map
is a ring isomorphism.
Proof
(Representatives, operations and bijectivity)
If , then modulo both and , so the map does not depend on the representative. It preserves addition, multiplication and the identity because reduction modulo an integer respects those operations componentwise.
Its kernel consists of classes whose representatives are divisible by both and . By coprimality those representatives are divisible by , so the kernel contains only the zero class and the map is injective. The selector construction gives an integer for every pair of target residues, so the map is surjective. It is therefore a ring isomorphism.
The ring operations on the product are componentwise. In the modulo-20 example, maps to and maps to . Their sum is modulo 20, their product is , and each is unchanged by squaring. They are selectors in the quotient ring; neither need equal the integer 0 or 1.
Common mistake
(The isomorphism needs coprime moduli)
For non-coprime moduli the same formula still defines a ring homomorphism, but it is neither injective nor onto. For , , the map sends to , so its kernel is nonzero (multiples of give a kernel of size 2), and the image has only 24 elements. The pair is not the image of any integer, since the first entry forces odd and the second forces it even. One cannot claim every pair of residues is attainable in that case.
Exercises with solutions
Quick check
(Solve , .)
The moduli are coprime, so one class modulo is expected.
Solution · Answer
satisfies both; since 3 and 5 are coprime, the full class is , equivalently .
Quick check
(Solve , .)
Compare the difference of the residues with the gcd first.
Solution · Answer
The difference 4 is divisible by the gcd 2. The integer 14 works, and all solutions are , .
Quick check
(Can and both hold?)
Look at parity.
Solution · Answer
No. The residues differ by 1, which the gcd 2 does not divide; they also demand opposite parity.
Quick check
(Verify that the selectors and modulo behave as selectors, and use them to rebuild the class for the residues and .)
Reduce each selector modulo and modulo .
Solution · Answer
Their residue pairs are and modulo . Also , , and . Thus gives the class for residues 2 and 3.
The arithmetic and the algebra express the same structure: selectors construct the combined class, and coprimality makes every pair of component residues correspond to exactly one class modulo the product.