Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: What is a systematic method to solve this Diophantine equation?

  1. Oct 2, 2012 #1
    1. The problem statement, all variables and given/known data

    Suppose you spend $12.30 on chocolate bars and chips. If chocolate bars cost $1.20 and each bag of chips cost $2.50, how many bags of chips did you buy?

    *Both the number of chocolate bars and bags of chips must be positive.

    2. Relevant equations

    12.30 = 1.20x + 2.50y

    3. The attempt at a solution

    What is the method i go about solving this problem besides guess and check. I assume it has something to do with the euclidian algorithm since thats what I have been learning.
  2. jcsd
  3. Oct 3, 2012 #2
    Euclidean algorithm?
  4. Oct 3, 2012 #3


    User Avatar
    Homework Helper
    Gold Member

    Well I think I got it, start with see why the chip bags have got to be an odd number and after that the chocolate bars have got to be...

    Hopefully this leads to something interesting (because I can't say it starts that way :biggrin:)
  5. Oct 3, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper

    Notice that all three numbers are "nearly" multiples of 1.2.

    You can use that fact to solve the problem without guessing, or chugging through Euclid's algorithm.
  6. Oct 3, 2012 #5


    User Avatar
    Science Advisor

    The first thing I would do it is multiply 12.30 = 1.20x + 2.50y by 10 to get 12x+ 25y= 123.

    The only "Euclidean algorithm" needed is to note that 25- 2(12)= 1. Multiplying that equation by 123, 12(-246)+ 25(123)= 123. That is, one solution is x= -246 and y= 123. That is not the solution because -246 is not positive. But x= -246+ 25k and y= 123-12k is also a solution for ay integer, k: 12(-246+ 25k)+ 25(123- 12k)= 12(-246)+ (12)(25k)+ 25(123)- 25(12k)= 123 since the two terms in k cancel.

    So you want to find an integer, k, such that x= -245+ 25k> 0 and y= 123- 12k> 0.
  7. Oct 3, 2012 #6
    Thanks heap guys! :!!)
  8. Oct 3, 2012 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Homework Helper
    Gold Member

    By the Way: Welcome to PF, Doctor111 !
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook