Usando Nᵢ = N/nᵢ e inversos.
El Chinese Remainder Theorem (CRT) te asegura que un sistema de congruencias lineales $x \equiv a_i \pmod{n_i}$ tiene una solución única módulo $N = n_1n_2\dots n_k$, siempre que los módulos $n_i$ sean primos relativos entre sí. Aunque saber que la solución existe sirve mucho para la teoría, los problemas de olimpiada a menudo te piden encontrar el valor específico de $x$. El método constructivo te da una fórmula explícita para esta solución, y así te ahorras el proceso tedioso de andar sustituyendo una y otra vez.
La intuición principal detrás de la construcción es crear una "base" para la solución. La idea es construir términos $T_1, T_2, \dots, T_k$ de tal forma que el $i$-ésimo término aporte exactamente $a_i$ a la suma módulo $n_i$, pero aporte $0$ a la suma módulo cualquier otro $n_j$ (donde $j \neq i$). Al sumar estos términos, creas un número $x = \sum T_i$ que cumple todas las congruencias del sistema al mismo tiempo.
Para lograr esta "ortogonalidad", define $N_i = N/n_i$. Como $N_i$ contiene todos los factores $n_j$ excepto $n_i$, resulta que es divisible entre todos los $n_j$ cuando $j \neq i$. Sin