Chinese Remainder Theorem Calculator

Understanding the Chinese Remainder Theorem Calculator

A Chinese remainder calculator finds a number leaving specified remainders when divided by two moduli. The theorem guarantees a unique solution when the moduli share no common factor, and the calculator now says explicitly when they do not.

How it actually works

Enter two remainders and their moduli. The calculator searches for the smallest non-negative value satisfying both congruences and reports the period at which solutions repeat. Remainders 2 and 3 with moduli 3 and 5 give x equal to 8, repeating every 15.

The deeper context most people miss

The coprime condition is what the classical theorem requires, and the non-coprime cases are not merely failures. Where the moduli share a factor and the remainders agree modulo it, a solution still exists but repeats over the least common multiple rather than the product.

Where the theorem came from and what it enables

The problem appears in Sun Tzu's Mathematical Classic, written somewhere around the third to fifth century, posing the question of finding a number leaving remainders 2, 3, and 2 when divided by 3, 5, and 7. The general method was developed fully by Qin Jiushao in 1247, and the result reached Europe much later, with Gauss giving a modern treatment in 1801. Its practical importance is that it lets a computation modulo a large number be split into independent computations modulo its prime power factors and recombined, which is a substantial speed-up when the pieces are small enough to fit in machine words while the whole is not. RSA decryption uses exactly this, splitting the operation modulo the product of two primes into two operations modulo each prime and combining them, typically giving something like a fourfold speed-up, which matters because RSA decryption is otherwise expensive. The same decomposition underlies fast algorithms in computer algebra, where a computation over the integers is performed modulo several primes and reconstructed, avoiding the growth of intermediate values that would otherwise dominate the cost. It also appears in secret sharing schemes, in error-correcting codes, and in the design of hash functions. The theorem's structural statement, that the integers modulo a product decompose as a direct product of the integers modulo each coprime factor, is what makes all of this work.

A worked example: why the brute force here is bounded

Finding 8 as the solution to x congruent to 2 modulo 3 and 3 modulo 5 by searching upward through the integers works fine for small moduli and scales terribly. The search runs until it finds a match, which takes up to the product of the moduli, so moduli around 1,000 each mean up to a million checks, which is why this calculator caps them. The constructive method is far better and scales to any size: for two coprime moduli, find integers satisfying Bézout's identity using the extended Euclidean algorithm, which expresses their greatest common divisor of one as a combination of the two moduli, and combine them to build the solution directly in a number of steps proportional to the logarithm of the moduli rather than to their product. Garner's algorithm generalises this to many moduli and is what implementations use. For the cryptographic application the moduli are enormous, hundreds of digits, so brute force is not merely slow but impossible, and the constructive method is the only route. The point worth taking from the contrast is that a search that works acceptably at small scale can be entirely infeasible at the scale where the result actually matters, which is a recurring pattern in computation.

Deciding when this structure applies

Congruence conditions arise more often than the abstract statement suggests. Scheduling problems where events recur at different fixed intervals are exactly this: two processes repeating every 3 and 5 units coincide every 15, and finding when they next align together at specified offsets is a congruence system. Calendar calculations use it, since day of week, day of month, and year positions cycle at different periods. Gear and pulley systems returning to an initial configuration. Cyclic scheduling in manufacturing and in operating systems. Sensor sampling at incommensurate rates. In each case the practical question is when the cycles realign, and the answer is governed by the least common multiple of the periods, with the theorem determining whether a specified combination of offsets is achievable at all. The non-coprime case matters here: two processes with periods sharing a common factor cannot achieve every combination of offsets, and knowing which combinations are impossible prevents specifying a schedule that cannot exist. For the general problem with many moduli, the same analysis applies pairwise, and a system is solvable exactly when every pair is compatible, which is a usefully checkable condition.

Modular arithmetic as an algebraic structure

The theorem is a statement about structure rather than a computational trick. The integers modulo n form a ring, and when n factors into coprime parts, that ring decomposes as a direct product of the rings modulo each part, meaning arithmetic can be performed independently in each component and recombined. This is an isomorphism, so nothing is lost. When the modulus is prime, every non-zero element has a multiplicative inverse and the structure is a field, which is why prime moduli appear throughout cryptography and coding theory: fields support division, which composite moduli do not in general. Fermat's little theorem, that any number raised to the power p minus one is congruent to one modulo a prime p, follows from the group structure of the non-zero elements, and Euler's generalisation extends it to composite moduli using the totient function counting values coprime to the modulus. Those results are what make RSA work: the encryption and decryption exponents are chosen so their product is one more than a multiple of the totient, so encrypting and decrypting returns the original message. Understanding this as algebra rather than as a set of arithmetic rules makes the cryptographic constructions look inevitable rather than ingenious.

Variations: multiple congruences, general moduli, and algorithms

The theorem extends to any number of pairwise coprime moduli, giving a unique solution modulo their product. For non-coprime moduli, a solution exists exactly when every pair of congruences agrees modulo the greatest common divisor of that pair's moduli, and the solution is then unique modulo the least common multiple of all the moduli. The extended Euclidean algorithm computes the Bézout coefficients needed for the constructive solution. Garner's algorithm builds the answer incrementally and is efficient for many moduli. The mixed radix representation stores a number by its residues and allows fast addition and multiplication componentwise, which is the basis of residue number systems used in some specialised hardware where the absence of carries between components allows parallelism. Comparison and division are awkward in that representation, which limits its use. In cryptography, the theorem accelerates RSA and appears in threshold secret sharing based on congruences. In computer algebra, modular methods compute over several primes and lift the result, avoiding intermediate expression swell that would otherwise make computations infeasible.

Working with congruence systems

Check whether the moduli are coprime, since the classical theorem guarantees a unique solution only in that case and non-coprime moduli require the remainders to agree modulo the shared factor. Expect the solution to repeat over the least common multiple of the moduli rather than their product when they share a factor. Verify each remainder is less than its modulus, since a remainder equal to or greater than its modulus is not a valid congruence statement. Use the constructive method via the extended Euclidean algorithm rather than searching, since search takes up to the product of the moduli while construction takes time proportional to their logarithm. Use Garner's algorithm for systems with many moduli. Recognise the structure in scheduling problems where processes recur at different fixed intervals, since finding when specified offsets coincide is exactly a congruence system. Note that non-coprime periods make some offset combinations impossible, which is worth checking before specifying a schedule. And remember that prime moduli give a field where division works, which is why they dominate cryptographic applications.

What people get wrong

• Assuming a solution always exists, when moduli sharing a common factor require the remainders to agree modulo that factor and otherwise no solution exists at all.
• Entering a remainder at least as large as its modulus, which is not a valid congruence since a remainder must be strictly less than what you divided by.
• Searching for the solution rather than constructing it, which takes up to the product of the moduli and is infeasible at the scale where the theorem actually matters.
• Expecting the solution period to be the product of the moduli, when non-coprime moduli give a period equal to their least common multiple instead.

Where the math comes from

For x ≡ r₁ (mod m₁) and x ≡ r₂ (mod m₂), a solution exists when r₁ ≡ r₂ modulo gcd(m₁, m₂), and is then unique modulo lcm(m₁, m₂). When the moduli are coprime the condition holds automatically and the solution is unique modulo m₁m₂. This calculator searches upward and caps the moduli, since search cost is proportional to their product.

Questions and answers

Related calculators

Dot Product · Volume · Ellipse · Polar to Cartesian · Cartesian to Polar