### Dr. Wilson

8. a) Use the Euclidean algorithm to find the GCD of 309 and 708.

b) Express the GCD as a difference of multiples of 309 and 708.

c) Given a 309 gallon bucket and a 708 gallon bucket, what is the smallestnumber of gallons you can measure and how would you measure it?

a) The steps in the Euclidean Algorithm are:

• divide one number into the next getting a quotient and a remainder;
• divide the remainder into the divisor; and
• repeat until you get a division problem that comes out even.

The divisor in the problem that comes out even is the GCD. It is also the last nonzero divisor.

and the GCD is 3.

b) To express the GCD as a difference of multiples of the two original numbers, in this case 309 and 708, first express the remainders in all of the division problems in terms of the dividends and divisors.

In each division problem, the remainder is expressed in terms of the dividend and divisor. Since the divisor is the remainder in the previous problem, if you substitute the formula for the remiander from the previous step in for the dividend in the current step, you can express each remainder in terms of the dividend and divisor from the previous problem. If we repeat, we can express the GCD, which is the last non-zero remainder in terms of the original dividend and divisor which are our two original numbers.

For each division problem after the one which gives us the GCD, there are three steps

 Substitute Remove parentheses Combine like terms 3 = 39 - 3x12 = 39 - 3(90 - 2x39) = 39 - 3x90 + 6x39 7x39 - 3x90 = 7(309 - 3x90) - 3x90 = 7x309 - 21x90 - 3x90 = 7x309 - 24x90 = 7x309 - 24(708 - 2x309) = 7x309 -24x708 + 48x309 = 55x309 - 24x708

To check:

55x309 - 24x708

= 16995 - 16992

= 3

c) Given a 309 gallon bucket and a 708 gallon bucket, what is the smallestnumber of gallons you can measure and how would you measure it?

We know that any common divisor, including the Greatest Common Divisor will go into any number of gallons which can be measured with this system. If we can show how to measure out the GCD, that would have to be the smallest number of gallons that can be measured.

Keep filling up the 708 gallon bucket with the 309 gallon bucket. As soon as you empty the 309 gallon bucket fill it up again and keep dumping it into the 708 gallon bucket until the 708 gallon bucket is full. As soon as the 708 gallon bucket is filled up, dump it out and keep filling it with what is left in the 309 gallon bucket. If you keep going, the 55th 309 gallon bucket will fill up the 708 gallon bucket for the 24th time with 3 gallons left.