Chinese Remainder Theorem

Find the unique solution to a system of modular congruences using the Chinese Remainder Theorem.

modular arithmetic crt coprime

Implement a function `crt(remainders, moduli)` that, given two lists of equal length — `remainders` (a_i) and `moduli` (m_i) — finds an integer `x` satisfying all congruences:

  x ≡ a_i (mod m_i)   for all i

The moduli are pairwise coprime (gcd(m_i, m_j) = 1 for all i ≠ j). Return the smallest non-negative solution modulo the product of all moduli (i.e., in the range [0, M-1] where M = product of all moduli).

You may assume:
- 1 ≤ len(remainders) == len(moduli) ≤ 10
- 0 ≤ a_i < m_i ≤ 1000
- Moduli are pairwise coprime.

Implement the function with the exact signature:

```python
def crt(remainders, moduli):
    pass
```

Your solution must run within the given time limit for the constraints (O(n^2) or better).

Constraints

1 ≤ n ≤ 10; 0 ≤ a_i < m_i ≤ 1000; moduli pairwise coprime. The product M fits in Python int.

Example

>>> crt([2, 3], [3, 5])
8
>>> crt([1, 2, 3], [2, 3, 5])
23
>>> crt([0], [7])
0

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Compute the total product M = product(moduli). For each modulus m_i, compute M_i = M // m_i and find its modular inverse modulo m_i.

The solution is sum(a_i * M_i * inv_i) mod M, where inv_i is the inverse of M_i modulo m_i.

Use extended Euclidean algorithm to compute modular inverses.

Ensure the final result is non-negative (take mod M).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.