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) by
"instrumenting" the classic Python implementation of Euclid's Algorithm:
def show_gcd(a,b):
"""
find GCD of two integers, showing intermediate steps
in both remainder and linear-combination forms
"""
while b:
if a%b > 0:
rem_form = "%d == %d*(%d), rem %d" % (a, b, a/b, a%b)
equ_form = "%d == %d*(1) + %d*(-%d)" % (a%b, a, b, a/b)
print "%3d %3d %-30s %s" % (a,b, rem_form, equ_form)
a,b = b, a%b
print "\nGCD is", a
>>> show_gcd(124, 39)
124 39 124 == 39*(3), rem 7 7 == 124*(1) + 39*(-3)
39 7 39 == 7*(5), rem 4 4 == 39*(1) + 7*(-5)
7 4 7 == 4*(1), rem 3 3 == 7*(1) + 4*(-1)
4 3 4 == 3*(1), rem 1 1 == 4*(1) + 3*(-1)
Performing successive substitutions, bottom to top, using the equations
in the right-hand column:
1 == 4*(1) + 3*(-1)
== 4*(1) + (7*(1) + 4*(-1))*(-1)
== 4*(2) + 7*(-1)
== (39*(1) + 7*(-5))*(2) + 7*(-1)
== 39*(2) + 7*(-11)
== 39*(2) + (124*(1) + 39*(-3))*(-11)
== 39*(35) + 124*(-11)
What could be simpler! :-)
-John
[1] http://math453fall2008.wikidot.com/lecture-3 ("GCD as a linear
combonation" [sic])
--
http://mail.python.org/mailman/listinfo/python-list
