#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int modular_inverse(int a, int m) {
    int m0 = m, t, q;
    int x0 = 0, x1 = 1;

    if (m == 1)
        return 0;

    while (a > 1) {
        q = a / m;
        t = m;

        m = a % m;
        a = t;
        t = x0;

        x0 = x1 - q * x0;
        x1 = t;
    }

    if (x1 < 0)
        x1 += m0;

    return x1;
}

int chinese_remainder_theorem(int num[], int rem[], int n) {
    int prod = 1;
    for (int i = 0; i < n; i++)
        prod *= num[i];

    int result = 0;

    for (int i = 0; i < n; i++) {
        int pp = prod / num[i];
        result += rem[i] * modular_inverse(pp, num[i]) * pp;
    }

    return result % prod;
}

int main() {
    int n;

    printf("Digite o número de equações (até 4): ");
    scanf("%d", &n);

    if (n < 1 || n > 4) {
        printf("Número inválido de equações. Deve ser entre 1 e 4.\n");
        return 1;
    }

    int num[4], rem[4];

    printf("Digite os valores dos módulos e os restos (formato: módulo resto):\n");
    for (int i = 0; i < n; i++) {
        printf("Equação %d: ", i + 1);
        scanf("%d %d", &num[i], &rem[i]);
    }

    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (gcd(num[i], num[j]) != 1) {
                printf("Os módulos não são coprimos: %d e %d\n", num[i], num[j]);
                return 1;
            }
        }
    }

    int result = chinese_remainder_theorem(num, rem, n);

    printf("A solução do sistema de congruências é: x = %d\n", result);

    return 0;
}