Chinese Remainder Formula Calculator

Chinese Remainder Theorem:

\[ x = \sum a_i M_i y_i \mod M, \quad M=\prod m_i, \quad y_i = M_i^{-1} \mod m_i \]

Solution (x):

Unit Converter ▲

Unit Converter ▼

From:	To:

1. What is the Chinese Remainder Theorem?

The Chinese Remainder Theorem (CRT) is a theorem that gives a unique solution to simultaneous congruences with pairwise coprime moduli. It has applications in computing, cryptography, and number theory.

2. How Does the Calculator Work?

The calculator uses the CRT formula:

\[ x = \sum a_i M_i y_i \mod M, \quad M=\prod m_i, \quad y_i = M_i^{-1} \mod m_i \]

Where:

\( a_i \) — Remainders
\( m_i \) — Pairwise coprime moduli
\( M \) — Product of all moduli
\( M_i \) — \( M/m_i \)
\( y_i \) — Modular inverse of \( M_i \) modulo \( m_i \)

Explanation: The theorem finds a number that leaves specified remainders when divided by each modulus.

3. Importance of CRT

Details: CRT is fundamental in computer algebra systems, cryptographic algorithms (like RSA), and solving systems of congruences efficiently.

4. Using the Calculator

Tips: Enter pairs of remainders and moduli (one pair per line, comma separated). All moduli must be pairwise coprime (gcd = 1 for each pair).

5. Frequently Asked Questions (FAQ)

Q1: What if moduli aren't coprime?
A: The system may have no solution or multiple solutions. The calculator checks for pairwise coprimality.

Q2: How large can the numbers be?
A: The calculator handles reasonably large integers, but extremely large numbers may cause performance issues.

Q3: What's the time complexity?
A: For n congruences, it's O(n²) due to pairwise coprimality checks and inverse calculations.

Q4: Are there alternatives to CRT?
A: For non-coprime moduli, you can use successive substitution or solve via prime factorization.

Q5: What are practical applications?
A: Used in RSA decryption, fast multi-precision arithmetic, calendar calculations, and solving linear congruences.