# Chinese Remainder Theorem Calculator

URL: https://speedycalculator.com/calculators/math/chinese-remainder/
Last updated: 2026-10-30

> The Chinese remainder theorem calculator solves a system of congruences x ≡ aᵢ (mod nᵢ) with pairwise coprime moduli and finds the unique solution modulo N = n₁ · n₂ · …

## Inputs

- Number of congruences
- x ≡ a₁
- (mod n₁)
- x ≡ a₂
- (mod n₂)
- x ≡ a₃
- (mod n₃)
- x ≡ a₄
- (mod n₄)
- x ≡ a₅
- (mod n₅)
- x ≡ a₆
- (mod n₆)

## Results

- Solution
- Smallest non-negative x
- N = product of the moduli
- Steps

## Formula

```
x ≡ Σ aᵢ · Mᵢ · (Mᵢ⁻¹ mod nᵢ)  (mod N),  Mᵢ = N / nᵢ
```

## Explanation

The classic puzzle – "a number leaves remainder 2 when divided by 3, 3 when divided by 5 and 2 when divided by 7" – was posed by Sunzi in the 3rd century. Today the theorem speeds up RSA decryption and underlies many algorithms in computer arithmetic.

### How to use the Chinese Remainder Theorem Calculator

- **Number of congruences**
- **x ≡ a₁**
- **(mod n₁)**
- **x ≡ a₂**
- **(mod n₂)**
- **x ≡ a₃**
- **(mod n₃)**
- **x ≡ a₄**
- **(mod n₄)**
- **x ≡ a₅**
- **(mod n₅)**
- **x ≡ a₆**
- **(mod n₆)**

Everything is calculated in your browser, so results appear instantly and nothing you type is sent to a server.

### How it works

For each congruence the calculator computes Mᵢ = N/nᵢ and its inverse modulo nᵢ with the extended Euclidean algorithm, then combines the terms. The moduli must be pairwise coprime.

## Worked example

Inputs — Number of congruences: 3; x ≡ a₁: 2; (mod n₁): 3; x ≡ a₂: 3; (mod n₂): 5; x ≡ a₃: 2; (mod n₃): 7.

Results — **Solution = x ≡ 23 (mod 105)**; Smallest non-negative x = 23; N = product of the moduli = 105; Steps = x ≡ 2 (mod 3): Mᵢ = 35, inverse of Mᵢ mod 3 = 2, term = 140
x ≡ 3 (mod 5): Mᵢ = 21, inverse of Mᵢ mod 5 = 1, term = 63
x ≡ 2 (mod 7): Mᵢ = 15, inverse of Mᵢ mod 7 = 1, term = 30
Sum mod 105 = 23.

## Key terms

- **Congruence**: a ≡ b (mod n) means n divides a − b.
- **Pairwise coprime**: Every pair of numbers has gcd 1.

## FAQ

**What does the theorem say?**
If the moduli are pairwise coprime, the system has exactly one solution modulo their product.

**What if the moduli share a factor?**
A solution may or may not exist; the calculator asks for pairwise coprime moduli.

**What is the classic example?**
x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7) gives x = 23.

**Where is it used?**
In RSA (CRT decryption), calendars, error-correcting codes and fast big-number arithmetic.


## Sources

- [OpenStax – Contemporary Mathematics](https://openstax.org/details/books/contemporary-mathematics)
- [Wolfram MathWorld – Chinese remainder theorem](https://mathworld.wolfram.com/ChineseRemainderTheorem.html)