Chinese Remainder Theorem Solver

Given arrays of residues and moduli, compute the unique solution x modulo M when the moduli are pairwise coprime:

x = r[i] (mod m[i]) for all i

Function signature

func CRT(residues, moduli []int64) (x int64, mod int64, ok bool)

Requirements

• Return ok=false if lengths differ, any modulus <= 1, or moduli are not pairwise coprime.
• If ok=true, return x in [0, mod-1] and mod = product of moduli.

Constraints

• 1 <= len(residues) == len(moduli) <= 8
• 2 <= moduli[i] <= 1e9
• Product of moduli fits in signed 64-bit.