solution

CRT tổng quát với $k$ đồng dư

Cho hệ $k$ đồng dư:

$x \equiv r_i \pmod{m_i}, \quad i=1,\dots,k$

Các $m_i$ không nhất thiết đôi một nguyên tố cùng nhau. Hãy gộp dần từng cặp bằng CRT để tìm nghiệm chung.

In nghiệm nhỏ nhất không âm $x$ và modulo gộp $L=\mathrm{lcm}(m_1,\dots,m_k)$. Nếu hệ vô nghiệm, in $-1$.

Ví dụ

$x\equiv2\pmod3$, $x\equiv3\pmod5$, $x\equiv2\pmod7$ cho $x=23$ modulo $105$.