Atividades de Programação para P2 - MD2

Questão 10 - Teorema Chinês

Gustavo Abrantes de Souza - 212008160

#include <stdio.h>

// Função para calcular o inverso modular de a mod m
int inversoModular(int a, int m) {
    a = a % m;
    for (int x = 1; x < m; x++) {
        if ((a * x) % m == 1)
            return x;
    }
    return -1; // Se não existir inverso
}

// Função para resolver o sistema de congruências usando o Teorema Chinês do Resto
int teoremaChines(int n[], int a[], int k, int *N) {
    *N = 1; // Produto de todos os n_i -> N = n1.n2.n3
    for (int i = 0; i < k; i++) {
        *N *= n[i];
    }

    int X = 0;
    for (int i = 0; i < k; i++) {
        int Ni = *N / n[i]; // Calculo dos N1, N2, N3, na qual é dado por -> N/n_i
        int Xi = inversoModular(Ni, n[i]); // Inverso de Ni módulo n_i, na qual é dado por Ni.Xi ≡ 1 (mod ni)
        if (Xi == -1) {
            printf("Erro: Nao existe inverso modular para %d modulo %d\n", Ni, n[i]);
            return -1;
        }
        // Calculo do X -> X ≡ (a1.X1.N1 + a2.X2.N2 + a3.X3.N3) mod N
        X += a[i] * Ni * Xi;
    }
    return X % (*N);
}

int main() {
    int n[4], a[4];
    int k, N;

    // Leitura do número de equações (máximo 4)
    printf("Digite o numero de equacoes (ate 4): ");
    scanf("%d", &k);

    if (k > 4) {
        printf("Numero maximo de equacoes e 4.\n");
        return 1;
    }

    // Leitura dos módulos (n_i) e dos restos (a_i), seguindo o formato 

    // X ≡ a1 (mod n1)
    // X ≡ a2 (mod n2)
    // X ≡ a3 (mod n3)
    for (int i = 0; i < k; i++) {
        printf("Digite n[%d] (modulo da equacao %d): ", i + 1, i + 1);
        scanf("%d", &n[i]);
        printf("Digite a[%d] (resto da equacao %d): ", i + 1, i + 1);
        scanf("%d", &a[i]);
    }

    // Chamando a função para calcular o resultado
    int result = teoremaChines(n, a, k, &N);
    
    if (result != -1) {
        printf("A solucao do sistema de congruencias e X = %d (mod %d)\n", result, N);
    }
    return 0;
}