On Aug 18, 11:50 am, John Posner <jjpos...@optimum.net> wrote: > On 8/18/2010 1:38 PM, cbr...@cbrownsystems.com wrote: > > >>> To go the other way, if d = 1, then there exists integers (not > >>> neccessarily positive) such that > > >>> a*x + b*y + c*z = 1 > > That fact is non-trivial, although the proof isn't *too* hard [1]. I > found it interesting to demonstrate the simpler case (a*x + b*y = 1)...
And to get the more general case, if we write (a,b) for gcd of and b, we can think of the "," as a binary operator that you can show is associative: ((a,b), c) = (a, (b,c)) = (a, b, c) and so a proof that exists x,y with a*x + b*y = (a,b) can then be extended to a proof for an arbitrary number of elements. (Oddly, "," is also distributive over itself: ((a,b), c) = ((a,c), (b,c))...) Cheers - Chas -- http://mail.python.org/mailman/listinfo/python-list
