The Chinese remainder theorem

Return the smallest whole number x, 0 or more, with x % mods[i] == rems[i] for every position i. If no such number exists, return None. The moduli may share factors.

crt([2, 3], [3, 5])         # 8
crt([2, 3, 2], [3, 5, 7])   # 23
crt([1, 3], [4, 6])         # 9
crt([1, 2], [4, 6])         # None: odd and even
crt([], [])                 # 0

Limits

• Up to 2,000 conditions. Each modulus is from 1 to about 10¹⁸ (a 1 followed by 18 zeros), and each remainder is from 0 to its modulus minus 1. The answer can have thousands of digits; Python’s whole numbers hold it exactly.
• pow(a, -1, m) and math.gcd are allowed. pow(a, -1, m) raises ValueError when a and m share a factor, so divide by the gcd first.