And for the inevitable typo see (*) below ... WFL On 5/8/11, Fred lunnon <fred.lunnon@gmail.com> wrote:
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 p_i) (*) is computed via x = y_1 z_1 + ... + y_k z_k (mod m) .
QED WFL