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
