Chinese Remainder Theorem Calculator

Welcome to the Chinese Remainder Theorem Calculator, a powerful number theory tool that solves systems of simultaneous congruences using the Chinese Remainder Theorem (CRT). Whether you are studying modular arithmetic, preparing for math competitions, working on cryptography problems, or exploring number theory, this calculator provides a complete step-by-step solution with interactive visualization showing how congruence classes align at the unique solution.

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) is a fundamental result in number theory that guarantees the existence and uniqueness of a solution to a system of simultaneous congruences, provided the moduli are pairwise coprime. The theorem was first described by the Chinese mathematician Sunzi (孫子) in his work Sunzi Suanjing (孫子算經) around the 3rd century CE.

Formally, given the system:

If all moduli \(m_1, m_2, \ldots, m_k\) are pairwise coprime (i.e., \(\gcd(m_i, m_j) = 1\) for all \(i \neq j\)), then there exists a unique solution \(x\) modulo \(M = m_1 \times m_2 \times \cdots \times m_k\).

How the CRT Algorithm Works

The constructive proof provides the algorithm used by this calculator:

Step 1: Compute M

Calculate the product of all moduli:

Step 2: Compute each Mᵢ

For each congruence \(i\), compute \(M_i = M / m_i\). This is the product of all moduli except \(m_i\).

Step 3: Find Modular Inverses

For each \(i\), find \(y_i\) such that \(M_i \cdot y_i \equiv 1 \pmod{m_i}\) using the Extended Euclidean Algorithm. Since \(M_i\) and \(m_i\) are coprime (all moduli are pairwise coprime), this inverse always exists.

Step 4: Construct the Solution

The general solution is \(x + k \cdot M\) for any integer \(k\), meaning the solution repeats every \(M\) integers.

How to Use This Calculator

1. Enter your congruences: For each equation \(x \equiv a \pmod{m}\), enter the remainder \(a\) and modulus \(m\). Start with 2 congruences and click "Add Congruence" for more (up to 10).
2. Check your moduli: All moduli must be positive integers ≥ 2 and pairwise coprime. The calculator verifies this automatically.
3. Click "Solve System": The calculator applies the CRT algorithm and shows the unique solution along with step-by-step work.
4. Review the visualization: The number line shows how the congruence classes from each equation intersect at the solution.
5. Verify: The verification section confirms the solution satisfies every original congruence.

Understanding the Results

• Smallest Non-Negative Solution (x₀): The unique solution in the range [0, M−1]
• General Solution: All integers of the form x₀ + kM where k is any integer
• Verification Table: Confirms x₀ mod mᵢ = aᵢ for each congruence
• Step-by-Step Breakdown: Shows Mᵢ, modular inverse yᵢ, and partial sum aᵢ·Mᵢ·yᵢ for each equation
• Number Line: Visual representation of how residue classes align at the solution

Applications of the Chinese Remainder Theorem

The Classic Sunzi Problem

The original problem from Sunzi Suanjing asks: "There are certain things whose number is unknown. If we count them by threes, we have two left over; by fives, three left over; and by sevens, two left over. How many things are there?"

This translates to: \(x \equiv 2 \pmod{3}\), \(x \equiv 3 \pmod{5}\), \(x \equiv 2 \pmod{7}\). Using CRT, the answer is x = 23 (and more generally, 23 + 105k for any non-negative integer k).

When Does CRT Not Apply?

• Non-coprime moduli: If any pair of moduli shares a common factor greater than 1, the standard CRT does not guarantee a solution. A solution may still exist if the remainders are compatible, but this calculator requires pairwise coprime moduli for the standard algorithm.
• Single congruence: CRT requires at least 2 congruences. A single congruence \(x \equiv a \pmod{m}\) already has the trivial solution x = a.

Extended Euclidean Algorithm

The Extended Euclidean Algorithm is essential for CRT because it finds the modular inverse. Given integers \(a\) and \(b\), it finds integers \(x\) and \(y\) such that:

When \(\gcd(a, b) = 1\), then \(x\) is the modular inverse of \(a\) modulo \(b\), i.e., \(a \cdot x \equiv 1 \pmod{b}\).

Frequently Asked Questions

What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) states that if you have a system of simultaneous congruences x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), ..., x ≡ aₖ (mod mₖ), where all moduli are pairwise coprime, then there exists a unique solution modulo M = m₁ × m₂ × ... × mₖ. This theorem was first described by the Chinese mathematician Sunzi in the 3rd century.

What does pairwise coprime mean?

Pairwise coprime means that every pair of moduli shares no common factor other than 1. For example, {3, 5, 7} are pairwise coprime because gcd(3,5)=1, gcd(3,7)=1, and gcd(5,7)=1. However, {4, 6, 5} are NOT pairwise coprime because gcd(4,6)=2.

How do you solve a system of congruences step by step?

To solve using CRT: (1) Verify all moduli are pairwise coprime. (2) Compute M = product of all moduli. (3) For each congruence, compute Mᵢ = M/mᵢ. (4) Find the modular inverse yᵢ of Mᵢ modulo mᵢ using the Extended Euclidean Algorithm. (5) Compute the solution x = Σ(aᵢ × Mᵢ × yᵢ) mod M. The general solution is x + k×M for any integer k.

What are the applications of the Chinese Remainder Theorem?

CRT has many practical applications: RSA cryptography uses CRT for efficient decryption. Computer science uses it for large number arithmetic by breaking computations into smaller modular pieces. Signal processing applies CRT in error-correcting codes. Scheduling and calendar problems where events repeat at different intervals also use CRT.

What happens if the moduli are not coprime?

If the moduli are not pairwise coprime, the standard CRT does not directly apply. In some cases, a solution may still exist if certain compatibility conditions are met (the remainders must be consistent modulo the GCD of the non-coprime moduli). However, if no solution exists, the system of congruences is inconsistent.

Additional Resources

• Chinese Remainder Theorem - Wikipedia
• Extended Euclidean Algorithm - Wikipedia
• Modular Arithmetic - Wikipedia