Traditional proofs of the Chinese remainder theorem always strike me as irritatingly indirect and nonconstructive. First, given a nonzero remainder y over the natural numbers, the unique inverse z = y^(-1) (mod p) modulo a prime p is computed via Euclid's algorithm: then z y = y z = 1 (mod p) . Next, for i = 1,...,k, given distinct prime moduli p_i and setting m = p_1...p_k, compute z_i = (m/p_i) ( (m/p_i)^(-1) (mod p_i) ) . These act as a kind of orthonormal basis, with z_j = 1, 0 (mod p_i) when j = i, j <> i resp. Finally, given remainders y_i with 0 <= y_i < p_i , the unique natural x satisfying 0 <= x < m and x = y_i (mod m_i) is computed via x = y_1 z_1 + ... + y_k z_k (mod m) . QED WFL