Chinese Remainder Theorem

Given a system of modular congruences:

x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₙ (mod mₙ)

Find the smallest non-negative integer x that satisfies all congruences. The generalized version handles cases where the moduli may not be pairwise coprime.

Examples

Input: congruences = [[2, 6], [3, 9]]
Output: 3
Explanation: x ≡ 2 (mod 6) and x ≡ 3 (mod 9)
The smallest solution is x = 3

Input: congruences = [[1, 3], [2, 5], [3, 7]]
Output: 52
Explanation: x ≡ 1 (mod 3), x ≡ 2 (mod 5), x ≡ 3 (mod 7)
The smallest solution is x = 52

Input: congruences = [[2, 4], [3, 6]]
Output: null
Explanation: No solution exists (inconsistent system)

Input: congruences = [[1, 2], [0, 4]]
Output: 4
Explanation: x ≡ 1 (mod 2) and x ≡ 0 (mod 4)
The smallest solution is x = 4

Mathematical Background

The Chinese Remainder Theorem states that if m₁, m₂, ..., mₙ are pairwise coprime, then there exists a unique solution modulo M = m₁ × m₂ × ... × mₙ.

For the generalized case with non-coprime moduli, we use the Extended Euclidean Algorithm to find solutions.

Constraints

• 1 ≤ n ≤ 10
• 0 ≤ aᵢ < mᵢ ≤ 10^9
• The system may or may not have a solution
• Return null if no solution exists