O Teorema Chinês do Resto Estendido (ExCRT) resolve sistemas de congruências da forma \(x \equiv r_i \pmod{m_i}\) para \(i=1,\ldots,k\), mesmo quando os módulos \(m_i\) não são coprimos entre si. A abordagem baseia-se na combinação iterativa de equações usando o algoritmo de Euclides estendido.

Fundamentos do Algoritmo de Euclides Estendido

Para resolver a equação diofantina linear \(a \cdot x + b \cdot y = \gcd(a, b)\), onde \(a\) e \(b\) são inteiros, o algoritmo de Euclides estendido fornece uma solução particular. Implementado recursivamente, ele calcula simultaneamente o máximo divisor comum (MDC) e os coeficientes \(x\) e \(y\).

typedef long long LL;

LL euclides_estendido(LL a, LL b, LL &x, LL &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    LL x_prox, y_prox;
    LL mdc = euclides_estendido(b, a % b, x_prox, y_prox);
    x = y_prox;
    y = x_prox - (a / b) * y_prox;
    return mdc;
}

Esta função retorna o MDC de \(a\) e \(b\), e armazena em \(x\) e \(y\) uma solução particular. Para resolver \(a \cdot x + b \cdot y = c\), onde \(c\) é um inteiro, é necessário que \(c\) seja divisível pelo MDC. Caso contrário, não existe solução.

Demonstração da Combinação de Congruências

Considere o caso com duas congruências: \(x \equiv r_1 \pmod{m_1}\) e \(x \equiv r_2 \pmod{m_2}\). Isso é equivalente a \(x = k_1 m_1 + r_1 = k_2 m_2 + r_2\) para inteiros \(k_1\) e \(k_2\). Reorganizando, obtemos a equação diofantina:

\[k_1 m_1 - k_2 m_2 = r_2 - r_1.\]

Aplicando o algoritmo de Euclides estendido para resolver \(k_1' m_1 - k_2' m_2 = \gcd(m_1, m_2)\), multiplicamos ambos os lados por \((r_2 - r_1)/\gcd(m_1, m_2)\) para obter uma solução particular \(k_1\). Substituindo em \(x = k_1 m_1 + r_1\), encontramos uma solução particular \(x_0\). A solução geral é então \(x = x_0 + t \cdot \text{mmc}(m_1, m_2)\), onde \(t\) é um inteiro arbitrário e \(\text{mmc}\) é o mínimo múltiplo comum. Isso produz uma nova congruência equivaelnte: \(x \equiv x_0 \pmod{\text{mmc}(m_1, m_2)}\). O processo é repetido iterativamente para todas as congruências do sistema, resultando em uma única congruência \(x \equiv R \pmod{M}\), onde \(M\) é o MMC de todos os módulos.

Implementação em C++

A função abaixo implementa o ExCRT. Ela mantém um módulo acumulado \(M\) e um resto acumulado \(R\), combinando cada congruência sequencialmente. Se em algum passo a congruência for inconsistente, a função retorna -1 indicando falta de solução.

#include <vector>
using namespace std;
typedef long long LL;

LL resolver_ex_crt(const vector<LL>& restos, const vector<LL>& modulos) {
    LL mod_corrente = modulos[0];
    LL resto_corrente = restos[0];
    int n = modulos.size();
    
    for (int i = 1; i < n; i++) {
        LL x, y;
        LL mdc = euclides_estendido(mod_corrente, modulos[i], x, y);
        
        LL diff = resto_corrente - restos[i];
        if (diff % mdc != 0) {
            return -1; // Sistema inconsistente
        }
        
        LL fator = diff / mdc;
        x = (x * fator) % modulos[i];
        if (x < 0) x += modulos[i]; // Ajuste para não-negativo
        
        resto_corrente = resto_corrente - mod_corrente * x;
        mod_corrente = mod_corrente / mdc * modulos[i];
        resto_corrente = ((resto_corrente % mod_corrente) + mod_corrente) % mod_corrente;
    }
    
    return resto_corrente;
}

Esta implementação assume que os vetores restos e modulos contêm os \(r_i\) e \(m_i\) respectivamente. A solução retornada é o menor inteiro positivo \(x\) que satisfaz o sistema, ou -1 se não houver solução.