While I agree that the constructive proofs are far more satisfying, the general proof (over rings with relatively prime ideals; Hungerford has a nice one) covers so much more and is constructive in an ideal sort of way. All the applications I've seen use Euclidian domains -- where you can compute inverses easily. The constructive proof covers all Euclidian domains. Those applications include polynomial interpolation (Lagrange uses the formula you showed below, just replace the p_i with monic degree one polynomials (x-a_i), the remainders y_i=f(a) mod (x-a_i), m/p_i with product (x-a_j) for all j not equal to i, and (m/p_i^{-1} mod p_i) with (product (x-a_j)^{-1}=product (a_i-a_j)^{-1} mod (x-a_i) and you'll get the formula for Lagrange interpolation), techniques for faster discrete logarithms if the order of the base used is factorable Montgomery multiplication, and even a derivation of truncated Taylor series. The nice thing about the general proof is that it also holds for non-Euclidian domains. I've never seen applications over non-Euclidian domain but it does work. Here's an example: work in the integers adjoined d = the square root of -5: Z[d] (not a Euclidian domain as it is not a unique factorization domain). The ideals (1+d)Z[d], (2+d)Z[d] and (3+2d)Z[d] are all pair-wise relatively prime ideals because each has a linear combination equivalent to one (ex: (2+d)(5+2d) + (3+2d)(-3-d)=1), which besides proving the primality also give you inverses. Using this you can find an integer in Z[d] which is equivalent to y_1 mod(1+d), y_2 mod (2+d) and y_3 mod(3+2d). For a concrete example: 3-22d = 6 mod(1+d), 4 mod(2+d) and 7 mod (3+2d). Does anyone know of any non-Euclidian, better yet, non-commutative, applications? Anna On 7 May 2011, at 20:35, Fred lunnon wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun