A congruence preserves partial information: means lies in the ideal . When several congruences are imposed, can one element satisfy all of them, and is it unique? The answer depends on how the ideals fit together. This section develops the Chinese remainder theorem from the ideal and Bézout tools in the MATH2076 notes, then uses it for integers and polynomials. We use commutative rings with identity; quotient rings may be the zero ring.
A reconstruction theorem for two ideals
Let be ideals of . Their sum is an ideal.
Definition 5.1.1
(Comaximal ideals)
Ideals of are comaximal if , equivalently if there are and with .
The equivalence follows by applying the definition of the sum to the element : if such a sum contains , it contains every . Write for the ideal of finite sums of products with , ; always .
Theorem 5.1.2
(Chinese remainder theorem for two ideals)
Let be comaximal ideals of a commutative ring with identity. Then for all there is with and , and any two such differ by an element of . Equivalently, the map
is a ring isomorphism. Moreover .
Proof
(Selecting a preimage with a Bézout identity)
Consider the map
It preserves addition, multiplication and identity, because both coordinates do. Its kernel is : the image is precisely when belongs to both ideals. If , the map is also onto. Indeed, choose , with . Then and , while has the opposite behavior. For any desired pair , set
Modulo it becomes , and modulo it becomes . This formula is an algorithm once we have a Bézout identity for .
The kernel describes uniqueness: two solutions differ by an element of . Consequently the induced map on is well defined because elements of vanish in both coordinates, injective by the kernel calculation, and surjective by the construction above.
For the last claim, let as above and . Then . Since and , the first term lies in ; since and , so does the second. Hence , and with the inclusion we get under comaximality.
Proof X-ray
Where comaximality is used, and nowhere else
Comaximality enters in exactly two places. The map , its kernel and therefore the uniqueness statement hold for arbitrary ideals; no identity is needed. The identity is needed to build the selectors: is modulo and modulo , and the other way round, so that reads in the first coordinate and in the second without the two terms interfering.
The non-obvious move in the last paragraph is . It sends each term into the ideal that must contain the product: has and , has and . The proof closes because both summands then lie in . The product formula is a consequence of the hypothesis, not an identity for arbitrary ideals. The counterexample below shows what breaks without the hypothesis: the uniqueness modulus is then the intersection, not the product, and existence needs a compatibility condition.
Counterexample mode
Comaximality cannot be dropped
Claim: for any ideals of a commutative ring, , and every pair of residues is attained by some . Take and . Then , but contains only multiples of , so and . For the second part take , , so that . Here , so the image of has elements, while the target has . The pair is not attained: forces even and forces odd. The repair is the hypothesis ; without it the conclusion holds only for compatible pairs, as the section on non-comaximal ideals shows.
Worked example: integers
Worked example 5.1.3
(Two congruences with coprime moduli)
Find every integer such that
The ideals and are comaximal because . We can choose and . Thus
is a solution. A direct check gives . Every other solution differs from 17 by an integer divisible by both 5 and 7, hence by 35; the complete answer is , . A negative representative, such as , describes the same residue class.
Common mistake
(Swapping the two selectors)
The coefficients and are selectors, and it is easy to reverse them by accident: must be 1 modulo 5 because it multiplies the desired residue 2, and must be 1 modulo 7 because it multiplies 3. With the roles swapped one computes , which is modulo and modulo , the residues exchanged.
Worked example: polynomials
Worked example 5.1.4
(Coprime polynomial moduli over the rationals)
Over , find the polynomial of degree below 3 satisfying
The moduli are coprime: . Taking and gives . Therefore
The product modulus is . Reducing gives the degree-below-3 representative . Check both requirements: its constant term is 1, and modulo it becomes . Every solution is with . Polynomial division gives exactly one representative of degree less than 3.
The same reasoning works for coprime polynomials over a field: Bézout gives , and the product modulus is . The field condition ensures polynomial division and Bézout; it should not be omitted when invoking that proof.
What changes when the ideals are not comaximal?
Proposition 5.1.5
(Solvability of two congruences)
Let be ideals of and . The congruences and have a solution exactly when . If a solution exists, all solutions differ by elements of .
Proof
(Splitting the difference)
Necessity follows by adding and to get . For sufficiency, write with , , and choose . Then and . Two solutions satisfy and , so .
Thus comaximality guarantees compatibility for every pair of residues, but individual compatible pairs can exist even when the ideals are not comaximal.
Worked example 5.1.6
(Compatible and incompatible pairs for moduli 4 and 6)
The conditions and are compatible: . The integer 9 satisfies both, and the complete set is , since . In contrast, and are impossible: their difference is not even, so it is not in .
Practice and full solutions
Exercise 5.1.7
(Solve , , and give the complete set of integer solutions.)
Foundation
Solution(4)
- 1
Write a Bézout identity for the moduli
Since , a convenient identity is . Take and , so .
- 2
Assemble the solution from the selectors
Key step
.
Because: is modulo and modulo , and is the other way round.
- 3
Reduce and check
, and , , so and . An alternative route: gives , the inverse of modulo is , and so , giving again.
- 4
State all solutions
Solutions differ by elements of , so the solutions are for .
Exercise 5.1.8
(Over , find all satisfying and .)
Core
Solution(4)
- 1
Test compatibility
The residues differ by , which belongs to , since . The congruences are compatible.
Because: The moduli share the factor , so they are not comaximal and the Solvability proposition applies.
- 2
Find one solution
Take . It is congruent to modulo , and , so it satisfies the second congruence.
- 3
Compute the uniqueness ideal
Key step
A common multiple of and must be divisible by and by , which are coprime. Hence .
Because: Two solutions differ by an element of the intersection, not the product.
- 4
State all solutions
Exercise 5.1.9
(Decide whether and have a common solution, and if so find all of them.)
Core
Solution(4)
- 1
Compute the sum ideal
.
Because: Solvability depends on , and is generated by .
- 2
Test compatibility
The residues differ by , so a solution exists.
- 3
Find one solution
Write . Then gives , so and . Taking gives , and .
- 4
State all solutions
Since , the solutions are for .