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...

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?

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.

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.

:)

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.

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.

:)

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 :/

Re: Euclidean algorithm, integer solutions

Post deleted due to error.