Given a system of simultaneous congruences x β‘ aβ (mod mβ), x β‘ aβ (mod mβ), β¦, find the unique solution x modulo lcm(mβ, mβ, β¦) if one exists. Handles both the classic coprime case and the generalized non-coprime case (Gauss's extension), and uses BigInt so it survives RSA-sized numbers.
The full solution set is x, x + M, x + 2M, β¦ β every integer congruent to the shown value mod M.
First stated in the 3rd-century Sunzi Suanjing ("There are certain things whose number is unknown. If we count them by threes, we have two left overβ¦"), the Chinese Remainder Theorem tells you that if the moduli are pairwise coprime, exactly one residue class modulo their product satisfies all the congruences. Modern uses: RSA-CRT decryption is up to 4Γ faster than plain modular exponentiation by working modulo the two primes separately; error-correcting codes use CRT to reconstruct residues from redundant checks; interpolation algorithms (Karatsuba, FFT-based multiplication) piggyback on the same reconstruction trick.