[math-fun] Chinese remainder theorem
To save you the trouble of looking it up: Thm: The number of dim sum is always relatively prime to the number of people sharing them. --rwg If the waiter brings you a fork, ask him to show you how to use it. DM>Thanks Mike and Tom :) On 7 May 2011, at 01:06, Mike Stay wrote:
On Fri, May 6, 2011 at 3:37 PM, David Makin <makinmagic@tiscali.co.uk <http://gosper.org/webmail/src/compose.php?send_to=makinmagic%40tiscali.co.uk>> wrote:
(I mean for example - what's CRT here ?)
http://en.wikipedia.org/wiki/Chinese_Remainder_Theorem -- Mike Stay - metaweta@gmail.com <http://gosper.org/webmail/src/compose.php?send_to=metaweta%40gmail.com> http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com
On 5/6/2011 7:57 PM, Bill Gosper wrote:
To save you the trouble of looking it up: Thm: The number of dim sum is always relatively prime to the number of people sharing them. --rwg If the waiter brings you a fork, ask him to show you how to use it.
Corollary: The number of hot dogs in a package and the number of buns in a package are relatively prime. My market sells packs of 23 dogs and packs of 19 buns. * I always buy the LCM so I have enough dogs/buns for several years. * Not really
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
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
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
Re non-commutative: doesn't Euclid work for integer quaternions? (Isn't that Dickson's proof of the 4 squares theorem?) I think that there are also versions of Euclid that work with some classes of matrices. Re CRT in these domains however, I don't know... At 06:26 PM 5/7/2011, Anna Johnston wrote:
Does anyone know of any non-Euclidian, better yet, non-commutative, applications?
On Sunday 08 May 2011 00:37:59 Fred lunnon wrote:
Traditional proofs of the Chinese remainder theorem always strike me as irritatingly indirect and nonconstructive.
[SNIP: a constructive proof: multiplicative inverses and all that.] For what it's worth, I'm pretty sure that that was one of the first proofs of CRT that I ever saw; in any case, it was the proof given in the Number Theory course I took as an undergraduate. I'd certainly consider it a traditional proof. -- g
On 5/8/11, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On Sunday 08 May 2011 00:37:59 Fred lunnon wrote:
Traditional proofs of the Chinese remainder theorem always strike me as irritatingly indirect and nonconstructive.
[SNIP: a constructive proof: multiplicative inverses and all that.]
For what it's worth, I'm pretty sure that that was one of the first proofs of CRT that I ever saw; in any case, it was the proof given in the Number Theory course I took as an undergraduate. I'd certainly consider it a traditional proof.
-- g
Anna's impressive list of examples doesn't really make her case --- the only significance of the Euclidean algorithm here is to efficiently compute multiplicative inverses, which she also utilises in Z[sqrt(-5)]. What I had in mind by "traditional" was actually the pigeonhole principle, which is computationally impractical [even if not strictly logically nonconstructive] --- see http://www.cut-the-knot.org/pigeonhole/CRT.shtml However I had not noticed before that --- to my disgust --- pigeonholing works even when the moduli are not prime: in which case, the inverse that my construction relies on may fail to exist! WFL
On 5/8/11, Fred lunnon <fred.lunnon@gmail.com> wrote:
... However I had not noticed before that --- to my disgust --- pigeonholing works even when the moduli are not prime: in which case, the inverse that my construction relies on may fail to exist!
Relax! The required inverses still exist, provided only that the moduli are coprime in pairs, not necessarily themselves prime. WFL
participants (6)
-
Anna Johnston -
Bill Gosper -
Fred lunnon -
Gareth McCaughan -
Henry Baker -
Stephen B. Gray