Homework 2, due Wednesday, January 19, 2011

Given two whole numbers b and c (like 3 and 5), today (i.e Friday, Jan 14) we thought about what the least positive whole number (i.e, the least positive integer) is that we can get as an integer linear combination of b and c.

The examples we looked at were:
b       c         least positive integer we could find 
                  which is an integer linear combination of b and c
3       5         1 = 2*5 - 3*3 (also 1 = 2*3 - 1*5; there are many more ways to do it)
2       4         2 = 1*4 - 1*2 (also 2 = 1*2 - 0*4, etc)
3       6         3 = 1*6 - 1*3 (also 3 = 1*3 - 0*6, etc)
4       6         2 = 1*6 - 1*4 (also 2 = 2*4 - 1*6, etc)
We talked about whether there is a pattern. What we noticed is that the least positive integer linear combination of b and c always divides both b and c evenly (i.e., it's a common factor). So for example, 2 divides both 4 and 6. In fact we made a guess (or as mathematicians say, a conjecture) as to what exactly this least positive integer linear combination is:

Conjecture: Our guess is that the least positive integer which is an integer linear combination of b and c is the greatest common divisor of b and c.

Let's write gcd(b,c) for the greatest common divisor. So gcd(4,6) = 2.

The assignment for Wednesday is to pick three examples of a b and a c, find gcd(b,c), and see if you can write gcd(b,c) as an integer linear combination of b and c.

We will pool the results of the whole class on Wednesday to see what evidence we get as to whether or not the Conjecture is true: was everyone always able to write gcd(b,c) as an integer linear combination of their choices of b and c, or were there some examples that didn't seem to work?