# Resolving sets of congruent equations using Chinese remainder theorem
# Rafał Lal 03/06/2021
import sys
from math import gcd, lcm, floor
from itertools import product
from functools import reduce
import numpy

nums = []
mods = []


def check_req():
    if numpy.prod(mods) != reduce(lcm, mods):
        return False
    prod = [x for x in product(mods, mods) if x[0] != x[1]]
    for i in range(len(prod)):
        if gcd(prod[i][0], prod[i][1]) != 1:
            return False
    return True


def extended_euclid(x, y):
    x0, x1, y0, y1 = 1, 0, 0, 1
    while y > 0:
        q, x, y = floor(x / y), y, x % y
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return q, x0, y0


def inversed_mod(a, m):
    g, x, y = extended_euclid(a, m)
    return x % m


def chinese_remainder_theorem():
    n = numpy.prod(mods)
    ni, mi, res = [], [], []
    for i in range(len(mods)):
        ni.append(int(n / mods[i]))
        mi.append(int(inversed_mod(ni[i], mods[i])))
        res.append(int(nums[i] * ni[i] * mi[i]))
    try:
        res = sum(res) % n
    except ArithmeticError:
        res = sum(res)
    return n, ni, mi, res


def main():
    print('Insert congruent equation (q to break): ')
    while True:
        char = input('x {} '.format(chr(0x2261)))
        if char == 'q':
            break
        nums.append(int(char))
        char = int(input('mod '))
        mods.append(int(char))

    if not check_req():
        print('Equation does not fulfil requirments')
        sys.exit()

    n, ni, mi, result, = chinese_remainder_theorem()
    print('\nResults:\nn =', n, sep=' ')
    print('Ni =', *ni, sep=' ')
    print('Mi =', *mi, sep=' ')
    print('x {} {} (mod {})'.format(chr(0x2261), result, n))

    return


if __name__ == '__main__':
    main()
