Linear combinations and GCD
Move the sliders for a and b to any predefined value. Then move the sliders for X and Y around until you achieve the smallest, nonzero result for the quantity aX + bY. This smallest nonzero result is called the GCD of a and b.
1. Set a = 10 and b = 13. For what values X and Y is aX + bY = 1?
2. Set a = 17 and b = 44. For what values X and Y is aX + bY = 1?
3. Set a = 21 and b = 33. It turns out it is impossible for aX + bY = 1 in this case. For what values X and Y is aX + bY as close to zero as possible (without being zero)? How close is it to zero?
4. Describe how you go about finding the values X and Y above. Try to explain a systematic or organized approach.
5. In problem 3, why couldn't you reach 1?
6. The smallest number you can reach in each case is called the GCD. Go to www.wolframalpha.com, and type in gcd(10, 13). You should get 1 -- this corresponds to the value we determined in problem 1.
7. Using WolframAlpha, find gcd(17, 44), and gcd(21, 33). What do you get?
8. Now type "Integer solutions to 10x + 13y = gcd(10, 13)" into WolframAlpha. This should give you the X and Y values you need to reach 1. Use it to find solutions to 135x + 522y = gcd(135, 522).