Teorema do Restante Chinês e Solução de Equações Congruentes

Congruências são pilares na teoria dos números, com aplicações em áreas como criptografia. Este artigo explora o Teorema do Restante Chinês (CRT) e a resolução de equações congruentes, fornecendo implementações em C++ adaptadas para clareza e eficiência.

Fundamentos Teóricos

• Pequeno Teorema de Fermat: Para primo p e inteiro a não divisível por p, ap-1 ≡ 1 (mod p).
• Algoritmo Euclidiano Estendido: Calcula intieros x e y satisfazendo ax + by = gcd(a, b).
• Inverso Multiplicativo: Dados a e m coprimos, existe x com ax ≡ 1 (mod m).
• Teorema de Euler: Se a e n são coprimos, então aφ(n) ≡ 1 (mod n), onde φ é a função totiente.
• Teorema do Restante Chinês: Resolve sistemas de congruências lineares simultâneas com módulos coprimos.

Problema 1: Determinação do Menor K via CRT

Dado um sistema de congruênccias K ≡ ai (mod mi), onde os mi são primos distintos, encontrar o menor inteiro positivo K que satisfza todas as condições.

Exemplo de Entrada:

3
2 1
3 2
5 3

Saída Esperada: 23

Especificação de Entrada:

• Primeira linha: inteiro N (2 ≤ N ≤ 10) indicando o número de congruências.
• Próximas N linhas: cada uma contém primo P e resto M (0 ≤ M < P).

Saída: O menor K < 109.

Implementação em C++

Utiliza o algoritmo euclidiano estendido para calcular inversos modulares no CRT.

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

ll extended_gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll gcd = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

ll solve_crt(int n, const vector<ll>& mods, const vector<ll>& rems) {
    ll prod = 1;
    for (ll m : mods) prod *= m;
    
    ll result = 0;
    for (int i = 0; i < n; ++i) {
        ll mi = mods[i];
        ll ri = rems[i];
        ll Mi = prod / mi;
        ll inv, dummy;
        extended_gcd(mi, Mi, inv, dummy);
        result = (result + ri * Mi * inv) % prod;
    }
    return (result + prod) % prod;
}

int main() {
    int n;
    cin >> n;
    vector<ll> mods(n), rems(n);
    for (int i = 0; i < n; ++i) {
        cin >> mods[i] >> rems[i];
    }
    cout << solve_crt(n, mods, rems) << endl;
    return 0;
}

Problema 2: Resolução da Equação Congruente ax ≡ 1 (mod b)

Encontrar o menor inteiro positivo x tal que ax ≡ 1 (mod b). Assume-se que a e b são coprimos.

Exemplo de Entrada:

3 10

Saída Esperada: 7

Especificação de Entrada:

• Entrada: dois inteiros a e b (2 ≤ a, b ≤ 2×109).
• Saída: o menor x positivo.

Implementação em C++

Aplica o algoritmo euclidiano estendido para calcular o inverso modular.

#include <iostream>
using namespace std;

typedef long long ll;

ll extended_gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll x1, y1;
    ll gcd = extended_gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return gcd;
}

ll modular_inverse(ll a, ll m) {
    ll x, y;
    ll g = extended_gcd(a, m, x, y);
    if (g != 1) {
        return -1; // Inverso não existe; problema garante solução.
    }
    return (x % m + m) % m;
}

int main() {
    ll a, b;
    cin >> a >> b;
    cout << modular_inverse(a, b) << endl;
    return 0;
}