Chinese Remainder Theorem: GCD  Greatest Common Divisor  or HCF  Highest Common Factor  If GCDa,b  1, then for any remainder ra modulo a and any remainder rb modulo b there exists integer n, such that n  ra mod a and n  ramod b.  If n1 and n2 are two such integers, then n1n2mod ab Algorithm : 1. Use extended euclid algorithm to find x,y such that ax  by  1 2. Take n  raby  rbax Extended Euclid  extendedeuclid10, 6 1, 2  extendedeuclid7, 5 2, 3 Uses ExtendedEuclid to find inverses  chineseremaindertheorem5,1,7,3 31 Explanation : 31 is the smallest number such that i  When we divide it by 5, we get remainder 1 ii When we divide it by 7, we get remainder 3  chineseremaindertheorem6,1,4,3 14 SAME SOLUTION USING InvertModulo instead ExtendedEuclid This function find the inverses of a i.e., a1  invertmodulo2, 5 3  invertmodulo8,7 1 Same a above using InvertingModulo  chineseremaindertheorem25,1,7,3 31  chineseremaindertheorem26,1,4,3 14
from __future__ import annotations


# Extended Euclid
def extended_euclid(a: int, b: int) -> tuple[int, int]:
    """
    >>> extended_euclid(10, 6)
    (-1, 2)

    >>> extended_euclid(7, 5)
    (-2, 3)

    """
    if b == 0:
        return (1, 0)
    (x, y) = extended_euclid(b, a % b)
    k = a // b
    return (y, x - k * y)


# Uses ExtendedEuclid to find inverses
def chinese_remainder_theorem(n1: int, r1: int, n2: int, r2: int) -> int:
    """
    >>> chinese_remainder_theorem(5,1,7,3)
    31

    Explanation : 31 is the smallest number such that
                (i)  When we divide it by 5, we get remainder 1
                (ii) When we divide it by 7, we get remainder 3

    >>> chinese_remainder_theorem(6,1,4,3)
    14

    """
    (x, y) = extended_euclid(n1, n2)
    m = n1 * n2
    n = r2 * x * n1 + r1 * y * n2
    return (n % m + m) % m


# ----------SAME SOLUTION USING InvertModulo instead ExtendedEuclid----------------


# This function find the inverses of a i.e., a^(-1)
def invert_modulo(a: int, n: int) -> int:
    """
    >>> invert_modulo(2, 5)
    3

    >>> invert_modulo(8,7)
    1

    """
    (b, x) = extended_euclid(a, n)
    if b < 0:
        b = (b % n + n) % n
    return b


# Same a above using InvertingModulo
def chinese_remainder_theorem2(n1: int, r1: int, n2: int, r2: int) -> int:
    """
    >>> chinese_remainder_theorem2(5,1,7,3)
    31

    >>> chinese_remainder_theorem2(6,1,4,3)
    14

    """
    x, y = invert_modulo(n1, n2), invert_modulo(n2, n1)
    m = n1 * n2
    n = r2 * x * n1 + r1 * y * n2
    return (n % m + m) % m


if __name__ == "__main__":
    from doctest import testmod

    testmod(name="chinese_remainder_theorem", verbose=True)
    testmod(name="chinese_remainder_theorem2", verbose=True)
    testmod(name="invert_modulo", verbose=True)
    testmod(name="extended_euclid", verbose=True)
