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