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?