# looping through possible combinations of McNuggets packs of 6, 9 and 20

John Posner jjposner at optimum.net
Wed Aug 18 20:50:32 CEST 2010

```On 8/18/2010 1:38 PM, cbrown at 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])

```