Motivation
A congruence such as looks like an equation over the integers, but cancellation must be treated with care: six has no inverse modulo fourteen. Working in a residue ring explains both when an equation has a solution and how many solutions it has. It also connects arithmetic with the ring-theoretic ideas of zero divisors, nilpotents and idempotents.
Definitions
Definition 3.3.1
(Special elements of a residue ring)
Fix an integer and write . We denote the class of by when the modulus is clear. A unit has a multiplicative inverse. A nonzero is a zero divisor when for some nonzero . An element is nilpotent if some positive power is zero, and idempotent if its square equals itself. The zero class is nilpotent and idempotent, but by our convention is not a zero divisor.
Write the prime factorization as , with distinct primes and . The Chinese remainder theorem (CRT) gives a ring isomorphism
It translates equations in into equations in every prime-power coordinate. The inverse map combines one solution in each coordinate into exactly one residue modulo .
Theorems
Theorem 3.3.2
(A linear congruence)
Let . The equation has a solution if and only if . If it does, it has exactly distinct solutions modulo .
Proof sketch or proof idea
Proof
(Reduce by the gcd, then lift back)
If is divisible by , then divides both and , so . Conversely, if , write , and . Dividing the integer divisibility statement by gives the equivalent congruence . If , Bézout gives an inverse for modulo because , so there is exactly one solution class modulo . If , there is likewise exactly one class and the congruence holds automatically. The classes
are distinct, and every solution has this form. Indeed two shifts agree modulo exactly when their indices agree modulo .
Counterexample mode
Cancellation needs a unit
It is tempting to cancel a nonzero factor: from , conclude . Take and . Then and , so , although . The class is a zero divisor, since , and the difference is annihilated by . Applying the proof above to gives the repaired statement: holds exactly when . Here , and indeed . Cancellation modulo itself is valid exactly when .
Theorem 3.3.3
(Units, zero divisors, nilpotents and idempotents)
For :
- is a unit exactly when ; it is a nonzero zero divisor exactly when and .
- is nilpotent exactly when every prime dividing divides .
- An idempotent has, independently for each , coordinate or modulo . Thus there are exactly idempotents in .
Proof
(Bézout, prime divisors and consecutive integers)
Bézout gives when the gcd is one, so is an inverse; the converse follows from . If and , then is nonzero and annihilates . A unit cannot annihilate a nonzero element, proving the zero-divisor criterion.
If , every divides , hence . Conversely, if every divides , taking makes divide for each ; their product divides . This proves nilpotence without claiming a least exponent.
For an idempotent coordinate modulo , the divisibility holds. Since consecutive integers cannot both be divisible by , all copies of must divide one factor. Hence or , and both are indeed idempotent. CRT combines these independent choices uniquely.
Proof X-ray
Why idempotents are decided one prime power at a time
The unit criterion uses only Bézout and needs no factorization. The other two parts each use primality at one precise point. For nilpotence, forces because is prime; the converse multiplies the prime-power divisibilities, which is legitimate because distinct prime powers are coprime. For idempotents, the key move is that and are coprime, so a prime power dividing divides one factor entirely. This step fails for a composite modulus: modulo , the class satisfies , yet divides neither nor . That is why the argument runs in each prime-power coordinate first, and only then does CRT assemble the independent choices of or into idempotents.
Worked examples
Worked example 3.3.4
(A solvable congruence)
Solve . The gcd is , which divides . Dividing the congruence by changes the modulus: . Since , . The two solutions modulo fourteen are and ; direct substitution gives .
Worked example 3.3.5
(Nilpotents modulo 72)
Since , the nilpotents are precisely the twelve classes divisible by : . The class has nilpotence index three: is nonzero modulo , while is zero. In contrast, is a nonzero zero divisor, since , but is not nilpotent because never divides a power of .
Worked example 3.3.6
(Constructing the idempotents modulo 12)
Here . The CRT coordinates give . For we need a multiple of three congruent to one modulo four: works. For , works. Therefore the full list is . As a check, , , and , .
The multiplication map: kernel and image
For fixed and , there is a structural reason why all solvable congruences have the same number of solutions. Regard as an additive group and define by . It is well defined because changing by a multiple of changes by a multiple of ; distributivity makes it an additive group homomorphism. We do not need it to be a unital ring homomorphism; multiplication by generally does not preserve products or the identity.
Let and . The kernel consists of the classes , where . Indeed, the congruence reduces to , so ; the distinct lifts give the stated kernel. The image is the subgroup of multiples of . One inclusion follows from . For the other, Bézout gives , and hence . Its elements are , so its order is .
The first isomorphism theorem therefore gives an isomorphism of additive groups
The displayed map is well defined because representatives in the same kernel coset have the same image; it is onto the image, and only the kernel coset maps to zero, so it is injective.
If is one solution of , the entire solution set is the coset : subtracting gives an element of the kernel, and adding any kernel element gives another solution. In particular a nonempty fiber contains elements. If is outside the image, its fiber is empty. This explains why the existence test and the count belong together.
Local equations and the global answer
Under CRT, modulo holds exactly when it holds modulo each . For a fixed prime power , let be the largest integer between and such that divides ; when take . Equivalently, . The linear-congruence theorem says that the local equation is solvable exactly when , and then has solutions modulo .
The local conditions together are equivalent to . If each is satisfied, choose a local solution at every prime-power coordinate; CRT gives one global class, and every global solution arises from exactly one such tuple. Multiplying the local numbers gives solutions. This is the same answer as the kernel argument, obtained by decomposing the ring rather than the additive map.
Worked example 3.3.7
(Solve a congruence by both methods)
Solve . Here , so the equation is solvable and has six solutions. Dividing the entire congruence, including the modulus, by six gives ; since , we get . The six solutions modulo thirty are
The local calculation gives the same result. Since , modulo two and three the equation reads , so all two and all three local classes are allowed. Modulo five it reads , with unique solution . CRT combines the tuples into the six classes listed. In the additive map , the kernel is and the solution set is its coset .
Now change the right side to . Modulo two the equation would say , so there is no global solution. Checking a single incompatible local equation suffices to disprove existence; checking just one compatible coordinate does not prove it.
Finding the first zero power
The nilpotence criterion tells us whether a power becomes zero; the prime exponents tell us when this first happens. Suppose is nilpotent and . For each , let be the exponent of in . Thus . Since the exponent of in is , the condition is equivalent to the simultaneous inequalities for all . Consequently the least positive such is
The maximum matters: a power is zero modulo only after it is zero in every prime-power coordinate. If the chosen representative is , its first positive zero power is simply ; the formula above was stated for nonzero representatives so that the exponents are finite.
Worked example 3.3.8
(The first zero power modulo 360)
Take and . All three required primes divide , so its class is nilpotent. Their exponents in are all one; the formula gives . Indeed, is not divisible by (it has only two factors of ), while . Thus but . The bound happens to be sharp here; it need not be sharp when contains higher prime powers.
Building complementary idempotents
The CRT also gives a practical construction, not just a count. Write with coprime. To find the idempotent with coordinates modulo , start with a multiple and solve . An inverse of modulo exists by Bézout, so this gives a unique class modulo . The class has coordinates . Coordinatewise, both square to themselves and their product is zero. Moreover every decomposes as : the first summand has zero -coordinate and the second has zero -coordinate. This is a decomposition in the ring, not a choice of integer representatives.
These pieces also explain how the ring splits. The sets and are rings under the inherited operations, with identities and respectively. In general neither identity is . The map preserves sums and products; cross-products vanish because . Its inverse sends to : indeed , , and the cross terms are zero. Hence . Under the CRT these factors correspond to and . For example, multiplying by keeps exactly the first coordinate, so it acts as a projection, not as an invertible change of coordinates.
Worked example 3.3.9
(Constructing the two pieces modulo 72)
Here , . Since , choose and . Then . Indeed, has coordinates and has modulo . For instance, , since . The two summands isolate the two coordinates. Together with and , these are all four idempotents modulo .
Quick check
(What is the first zero power of modulo ?)
Compare the exponent of each prime in with its exponent in .
Solution · Answer
Here and , so the answer is : indeed is divisible by , while .
Common mistakes
Common mistake
(Dividing a congruence also divides the modulus)
Dividing by two while leaving the modulus fourteen would replace the original equation by a different condition. Divide the modulus too, and count the lifts back to the original modulus.
Common mistake
( allows every local class)
In a local equation, permits every class in that coordinate, not merely zero. By contrast, with has no local solution and therefore no global solution.
Common mistake
(Zero divisors and nilpotents are different)
A zero divisor does not have to be nilpotent: modulo six is idempotent and nonzero, yet it annihilates . In the other direction, a residue class may be nilpotent without its integer representative being zero. The definition concerns a power becoming divisible by the modulus. Being divisible by just one prime factor is insufficient when the modulus has another prime factor.
Summary
Use the gcd to solve linear equations and identify units. Use the prime divisors of the modulus for nilpotence, and use independent zero-or-one choices in prime-power coordinates for idempotents. The CRT combines local answers; it does not say that every pair of congruences with noncoprime moduli is compatible.
Exercises
Quick check
(Solve and show the list is complete. Find the kernel and image of on the additive group, and express the solution set as a kernel coset.)
Solution · Answer
Here divides . Divide by four to get , whence . The four solutions modulo twenty are . The kernel is , the image is , and the solution set is .
Quick check
(Find every nilpotent modulo and the least positive power that makes zero.)
Solution · Answer
As , the nilpotents are . Since is nonzero and , the least positive exponent for is two.
Quick check
(Find all idempotents modulo .)
Solution · Answer
CRT for gives four choices. The classes with coordinates are respectively .
Quick check
(Prove that has no nonzero nilpotent exactly when is square-free.)
Solution · Answer
If is square-free, every prime divisor dividing implies , so every nilpotent class is zero. If some exponent , let be the product of the distinct prime divisors of . Then is nilpotent by the criterion but nonzero because .