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 extended euclid extended_euclid 10 6 1 2 extended_euclid 7 5 2 3 uses extendedeuclid to find inverses 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 same solution using invertmodulo instead extendedeuclid this function find the inverses of a i e a 1 invert_modulo 2 5 3 invert_modulo 8 7 1 same a above using invertingmodulo chinese_remainder_theorem2 5 1 7 3 31 chinese_remainder_theorem2 6 1 4 3 14
from __future__ import annotations



def extended_euclid(a: int, b: int) -> tuple[int, int]:
    
    if b == 0:
        return (1, 0)
    (x, y) = extended_euclid(b, a % b)
    k = a // b
    return (y, x - k * y)



def chinese_remainder_theorem(n1: int, r1: int, n2: int, r2: int) -> int:
    
    (x, y) = extended_euclid(n1, n2)
    m = n1 * n2
    n = r2 * x * n1 + r1 * y * n2
    return (n % m + m) % m






def invert_modulo(a: int, n: int) -> int:
    
    (b, x) = extended_euclid(a, n)
    if b < 0:
        b = (b % n + n) % n
    return b



def chinese_remainder_theorem2(n1: int, r1: int, n2: int, r2: int) -> int:
    
    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)