# Euclidean algorithm, integer solutions

• May 24th 2013, 06:59 PM
Educated
Euclidean algorithm, integer solutions
Quote:

Bart spends $32.70 buying Beer and Coke for a party. Beer costs$3.30 each and Coke costs $1.80 each. How many bottles of each did he buy? So the first thing to do is find the greatest common divisor of the 2 numbers using the Euclidean Algorithm, (I'm going to use the numbers 327, 33 and 18) We have the equation: 33x + 18y = 327 33 = 1 * 18 + 15 18 = 1 * 15 + 3 15 = 5 * 3 + 0 And so the GCD is 3. Using the extended Euclidean algorithm, I get: 3 = 18 * (2) + 33 * (-1) Scaling that up to 327:$\displaystyle 327 = \underbrace{18 \cdot (2 \cdot 109)}_{\text{Beer}} + \underbrace{33 \cdot (-1 \cdot 109)}_{\text{Coke}}$Now how do I transform the equation into one parameter, (we used 't' as the parameter in our class). As it is now, it says I bought 21.8 bottles of beer and -10.9 bottles of coke... • May 24th 2013, 10:47 PM chiro Re: Euclidean algorithm, integer solutions Hey Educated. I did this stuff years ago, and from memory you should have multiple solutions depending on the GCD and the equation. Have you been given the algorithm to generate all possible solutions of a bi-linear Diophantine equation? • May 24th 2013, 11:24 PM Educated Re: Euclidean algorithm, integer solutions Yea, I know there can be many positive solutions in these sort of equations. In this particular example I think there's just one answer, but I want to know how to work it out in the general form. I think we have to generate the algorithm ourselves, to generate all possible solutions, and that's the part I'm stuck on. • May 25th 2013, 12:30 AM agentmulder Re: Euclidean algorithm, integer solutions Quote: Originally Posted by Educated So the first thing to do is find the greatest common divisor of the 2 numbers using the Euclidean Algorithm, (I'm going to use the numbers 327, 33 and 18) We have the equation: 33x + 18y = 327 33 = 1 * 18 + 15 18 = 1 * 15 + 3 15 = 5 * 3 + 0 And so the GCD is 3. Using the extended Euclidean algorithm, I get: 3 = 18 * (2) + 33 * (-1) Scaling that up to 327:$\displaystyle 327 = \underbrace{18 \cdot (2 \cdot 109)}_{\text{Beer}} + \underbrace{33 \cdot (-1 \cdot 109)}_{\text{Coke}}$Now how do I transform the equation into one parameter, (we used 't' as the parameter in our class). As it is now, it says I bought 21.8 bottles of beer and -10.9 bottles of coke... At the bottom of your post you mixed up beer and coke. :) Here is another way, after you get the GCD, instead of multiplying by 109 you can add 324 3 + 324 = 18(2) + 33(-1) + 324 Now go to work on the 324 on the right.$\displaystyle 327 = 18(2) + 33(-1) + \underbrace{33(6) + 18(7)}_ {324} $327 = 18(9) + 33(5) He bought 9 bottles of coke and 5 bottles of beer. :) • May 25th 2013, 01:30 AM Educated Re: Euclidean algorithm, integer solutions Quote: Originally Posted by agentmulder At the bottom of your post you mixed up beer and coke. :) Here is another way, after you get the GCD, instead of multiplying by 109 you can add 324 3 + 324 = 18(2) + 33(-1) + 324 Now go to work on the 324 on the right.$\displaystyle 327 = 18(2) + 33(-1) + \underbrace{33(6) + 18(7)}_ {324} $327 = 18(9) + 33(5) He bought 9 bottles of coke and 5 bottles of beer. :) Haha yes, I did get them the other way around. Firstly, how did you get that you needed 6 lots of 33 and 7 lots of 18 to make 324? I mean, this is a simple example and you can guess those numbers, but I want a general algorithm to get it. • May 25th 2013, 02:24 AM agentmulder Re: Euclidean algorithm, integer solutions kobayashi maru I cheated like James Tiberious Kirk Look carefully at 3 = 18(2) + 33(-1) There is no way to get both numbers in both parenthesis to be positive integers... which is what you want. Multiplying the whole thing by 109 won't eliminate the impossibility of positive integer solutions. So i thought of another way to package my idea into 'lots' and serve it up as a diophantine solution to an impossible problem. Forgive me if i wasted your time but i hope you smile in the end. :) • May 25th 2013, 02:47 AM Educated Re: Euclidean algorithm, integer solutions I've figured out the solution is:$\displaystyle 327 = \underbrace{(218) \cdot 18}_{\text{Coke}} - \underbrace{(109) \cdot 33}_{\text{Beer}}\displaystyle 327 = \underbrace{(218 + 11t)}_{\text{Coke}} \cdot 18 - \underbrace{(109 + 6t)}_{\text{Beer}} \cdot 33$All you have to do is solve for t:$\displaystyle \underbrace{(218 + 11t)}_{\text{Coke}} \ge 0\displaystyle \underbrace{(109 + 6t)}_{\text{Beer}} \ge 0\$

And there's only 1 solution of t that fits those conditions.

I know how to work it out and everything but I don't know why it works :/
• May 25th 2013, 05:43 AM
agentmulder
Re: Euclidean algorithm, integer solutions
Post deleted due to error.