Results 1 to 8 of 8

Math Help - Euclidean algorithm, integer solutions

  1. #1
    Senior Member Educated's Avatar
    Joined
    Aug 2010
    From
    New Zealand
    Posts
    418
    Thanks
    11

    Euclidean algorithm, integer solutions

    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:

    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...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Sep 2012
    From
    Australia
    Posts
    3,607
    Thanks
    591

    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Educated's Avatar
    Joined
    Aug 2010
    From
    New Zealand
    Posts
    418
    Thanks
    11

    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member agentmulder's Avatar
    Joined
    Aug 2011
    From
    42nd parallel, North America
    Posts
    105
    Thanks
    33

    Re: Euclidean algorithm, integer solutions

    Quote Originally Posted by Educated View Post
    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:

    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.

     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.

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member Educated's Avatar
    Joined
    Aug 2010
    From
    New Zealand
    Posts
    418
    Thanks
    11

    Re: Euclidean algorithm, integer solutions

    Quote Originally Posted by agentmulder View Post
    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.

     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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member agentmulder's Avatar
    Joined
    Aug 2011
    From
    42nd parallel, North America
    Posts
    105
    Thanks
    33

    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.

    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member Educated's Avatar
    Joined
    Aug 2010
    From
    New Zealand
    Posts
    418
    Thanks
    11

    Re: Euclidean algorithm, integer solutions

    I've figured out the solution is:

    327 = \underbrace{(218) \cdot 18}_{\text{Coke}}  -  \underbrace{(109) \cdot 33}_{\text{Beer}}


    327 = \underbrace{(218 + 11t)}_{\text{Coke}} \cdot 18 -  \underbrace{(109 + 6t)}_{\text{Beer}} \cdot 33

    All you have to do is solve for t:

    \underbrace{(218 + 11t)}_{\text{Coke}} \ge 0

    \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 :/
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member agentmulder's Avatar
    Joined
    Aug 2011
    From
    42nd parallel, North America
    Posts
    105
    Thanks
    33

    Re: Euclidean algorithm, integer solutions

    Post deleted due to error.
    Last edited by agentmulder; May 25th 2013 at 05:50 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Division Algorithm or Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 10th 2013, 01:10 PM
  2. Euclidean algorithm
    Posted in the Algebra Forum
    Replies: 7
    Last Post: October 7th 2012, 06:40 AM
  3. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 9
    Last Post: September 25th 2012, 08:44 PM
  4. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 13th 2007, 07:20 AM
  5. Euclidean algorithm gcd lcm help..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 10th 2006, 05:46 AM

Search Tags


/mathhelpforum @mathhelpforum