from euclides import *

def inverso(a,n):
    """Calcula a forma reduzida
    dor inverso de a modulo n,
    se existir, ou retorna False
    caso contrario"""
    mdc, alfa, beta= euclides_estendido(a,n)
    if mdc != 1:
        return False
    if alfa < 0:
        return alfa + n
    return alfa

def teorema_chinês(lista_de_pares):
    """ ... """
    #calculando P
    P = 1

    for a,n in lista_de_pares:
        P *= n
    lista_dos_M = []
    lista_dos_b = []

    for a,n in lista_de_pares:
        M_atual = P//n
        list.append(lista_dos_M, M_atual)
        list.append(lista_dos_b, inverso(M_atual,n))

    soma = 0
    for índice in range(len(lista_de_pares)):
        a_atual = lista_de_pares[índice][0]
        M_atual = lista_dos_M[índice]
        b_atual = lista_dos_b[índice]
        soma += a_atual * M_atual * b_atual
        soma %= P
    return soma