Many remainders, one number
Suppose you know a number's remainder under several different coprime moduli. The Chinese remainder theorem says these remainders pin down a single value modulo the product of the moduli, and it gives a way to reconstruct that value. This lets you split a large modular computation into independent pieces.
The guarantee
If the moduli are pairwise coprime, then for any choice of remainders there is exactly one solution in the range from zero up to the product of the moduli. Uniqueness within that range is what makes the reconstruction well defined.
Reconstructing the value
A standard construction builds the answer as a sum of contributions, one per modulus.
- Let the product of all moduli be the big modulus.
- For each modulus, take the product of all the others.
- Multiply that product by its inverse with respect to the current modulus, and by the required remainder.
- Sum these contributions and reduce by the big modulus.
Each contribution is designed to give the right remainder for its own modulus and vanish for the rest.
Key idea
Pairwise coprime moduli make the remainders identify one value modulo their product, reconstructed by summing per modulus contributions that each fix their own remainder and cancel elsewhere.