Chinese Remainder Theorem Calculator

Solve systems of simultaneous linear congruences with step-by-step CRT solutions.

Enter System of Congruences

Enter congruences of the form: x ≡ a (mod m)

x ≡ (mod )
x ≡ (mod )
x ≡ (mod )

Result

Solution
23
x ≡ 23 (mod 105)
Product of moduli (M)105
General solutionx = 23 + 105k
Smallest positive x23

Step-by-Step Solution

x ≡ 23 (mod 105)

Understanding the Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is one of the oldest known results in number theory, dating back to the 3rd century CE. It was first described by the Chinese mathematician Sunzi (Sun Tzu) in his work Sunzi Suanjing (The Mathematical Classic of Sun Zi). The theorem provides a method to solve systems of simultaneous linear congruences when the moduli are pairwise coprime.

Given a system of congruences x ≡ a1 (mod m1), x ≡ a2 (mod m2), ..., x ≡ an (mod mn), where the moduli mi are pairwise coprime (gcd(mi, mj) = 1 for i ≠ j), the CRT guarantees a unique solution modulo M = m1 × m2 × ... × mn.

How the CRT Algorithm Works

Step 1: Compute M

Calculate the product of all moduli: M = m1 × m2 × ... × mn.

M = m1 * m2 * ... * mn

Step 2: Compute Mi

For each congruence, compute Mi = M / mi.

Mi = M / mi

Step 3: Find Inverses

Find yi such that Mi × yi ≡ 1 (mod mi) using the extended Euclidean algorithm.

Mi * yi ≡ 1 (mod mi)

Step 4: Compute Solution

The solution is x = (a1M1y1 + a2M2y2 + ... + anMnyn) mod M.

x = sum(ai*Mi*yi) mod M

The Extended Euclidean Algorithm

A key component of the CRT solution is finding modular multiplicative inverses. The extended Euclidean algorithm is used for this purpose. Given integers a and b, the algorithm finds integers x and y such that ax + by = gcd(a, b). When gcd(a, b) = 1, this gives us a × x ≡ 1 (mod b), meaning x is the modular inverse of a modulo b.

The algorithm works by repeatedly applying the division algorithm while tracking the coefficients that express the gcd as a linear combination of the original numbers. This recursive process terminates when the remainder is zero, and the coefficients are traced back to give the desired solution.

Historical Context

The original problem posed by Sunzi was: "There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, we have three left over; and by sevens, two are left over. How many things are there?" The answer is 23, which is the smallest positive integer satisfying x ≡ 2 (mod 3), x ≡ 3 (mod 5), and x ≡ 2 (mod 7).

Conditions for CRT

  • Pairwise coprime moduli: All pairs of moduli must share no common factor other than 1. That is, gcd(mi, mj) = 1 for all i ≠ j.
  • Positive moduli: All moduli must be positive integers greater than 1.
  • Unique solution: The solution is unique modulo M = m1 × m2 × ... × mn.
  • Any remainders: The remainders ai can be any integers (including negative values or values larger than the modulus).

Applications of the Chinese Remainder Theorem

The CRT has far-reaching applications in both pure mathematics and computer science. In cryptography, it is used in the RSA algorithm to speed up decryption. In coding theory, it helps construct error-correcting codes. In computer science, it enables efficient computation with large numbers by breaking them into smaller components.

  • RSA Cryptography: CRT is used to speed up RSA decryption by performing calculations modulo the prime factors p and q separately, then combining the results.
  • Parallel Computing: Large integer arithmetic can be parallelized by decomposing numbers using CRT and performing operations on smaller residues simultaneously.
  • Polynomial Interpolation: CRT extends to polynomials, enabling efficient polynomial reconstruction from evaluations at distinct points.
  • Calendar Computations: CRT can be used to solve scheduling and calendar-related problems involving multiple periodic cycles.
  • Secret Sharing: Asmuth-Bloom secret sharing scheme uses CRT to split and reconstruct secrets.

Tips for Using This Calculator

  • Make sure all moduli are pairwise coprime (share no common factors).
  • You can add as many congruences as needed using the "Add" button.
  • Negative remainders are accepted and handled correctly.
  • If moduli are not coprime, the calculator will notify you that the standard CRT does not apply.