Implement:
ext_gcd(a, b): returns (g, x, y) with g = gcd(a, b) and a*x + b*y = g (iteratively)mod_inverse(a, m): the x in 0..m-1 with a*x ≡ 1 (mod m), or raise ValueError if none existscrt(remainders, moduli): the smallest non-negative x satisfying every x ≡ r_i (mod m_i) for pairwise coprime moduli (Chinese remainder theorem)Don't use pow(a, -1, m).