Page 1 of 2 12 LastLast
Results 1 to 15 of 16

Math Help - elem.num.theo - diophantine equations w/word problems

  1. #1
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101

    elem.num.theo - diophantine equations w/word problems

    OK: long story short, restrictions are positive integers - the book gives us 63x+7=23y
    so I start:
    63 = (-23)(-2) + 17
    -23 = 17(-1) + (-6)
    17 = (-6)(-2) + 5
    -6 = (5)(-1) + (-1)
    5 = (-1)(-5) + 0
    so gcd(63,-23)=-1

    does this work? I mean with the whole negative thing? because I continue on like that and eventually get:
    x = 28 + 23t
    y = 77 + 63t
    where t>0
    then I get, t>(-28/23) and t>(-77/63)
    and I'm stuck. Because it has to be positive - and it has to be an integer

    therefore - i think it has to do with the negatives - how would one go about them?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by cassiopeia1289 View Post
    OK: long story short, restrictions are positive integers - the book gives us 63x+7=23y
    so I start:
    63 = (-23)(-2) + 17
    -23 = 17(-1) + (-6)
    17 = (-6)(-2) + 5
    -6 = (5)(-1) + (-1)
    5 = (-1)(-5) + 0
    so gcd(63,-23)=-1

    does this work? I mean with the whole negative thing? because I continue on like that and eventually get:
    x = 28 + 23t
    y = 77 + 63t
    where t>0
    then I get, t>(-28/23) and t>(-77/63)
    and I'm stuck. Because it has to be positive - and it has to be an integer

    therefore - i think it has to do with the negatives - how would one go about them?
    the gcd cannot be negative.

    anyway, it seems to me that your solutions for x and y (which, since you did so well on the last problem, i assume are right--perhaps with a factor of a minus sign if you indeed took the gcd to be -1) will be positive as long as t \ge -1, where t is an integer
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Apr 2008
    Posts
    1,092
    Quote Originally Posted by cassiopeia1289 View Post
    OK: long story short, restrictions are positive integers - the book gives us 63x+7=23y
    does this work? I mean with the whole negative thing? because I continue on like that and eventually get:
    x = 28 + 23t
    y = 77 + 63t
    where t>0
    then I get, t>(-28/23) and t>(-77/63)
    and I'm stuck. Because it has to be positive - and it has to be an integer

    therefore - i think it has to do with the negatives - how would one go about them?
    Note that

    x = 28 + 23(-1) = 5
    y = 77 + 63(-1) = 14

    is a solution in positive integers.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    ok, but if the gcd can't be negative - how do I even approach this problem to begin with??
    Follow Math Help Forum on Facebook and Google+

  5. #5
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by cassiopeia1289 View Post
    ok, but if the gcd can't be negative - how do I even approach this problem to begin with??
    the same way you did the last one. you want to find the solutions to 7 = (-63)x + 23y

    furthermore, note that \text{gcd}(a,b) = \text{gcd}(|a|,|b|)

    so gcd(63, -23) = gcd(-63, 23) = gcd(-63, -23) = gcd(63,23) = +1
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    ah - haha, ok,

    helpful

    so I just use a as |-63| = 63 and b as 23?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    ok - but if I do that - wouldn't it screw up my end result? or would I then have to convert the x0 to be negative?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by cassiopeia1289 View Post
    ok - but if I do that - wouldn't it screw up my end result? or would I then have to convert the x0 to be negative?
    probably. just start over with the new insight that you have and run the algorithm through from scratch. what do you end up with? if it just changes the x to an initial negative result, so be it, just choose t so that you only produce positive x values
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    ok, so I got x0=4 and y0=11
    the equation yields:
    1 = 23(11) - 63(4)

    should I make y0=(-4), making 63 positive, or keep y0=4, making 63 negative like it was before I did absolute values

    If I undid it to begin with, shouldn't I have to redo it?


    and either way - it doesn't make sense
    I get: x = 4 + 23t > 0
    and y = 11 - 63t > 0

    even if I turn 63 negative or positive - they equal the same thing ... ? therefore no solutions?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by cassiopeia1289 View Post
    ok, so I got x0=4 and y0=11
    the equation yields:
    1 = 23(11) - 63(4)

    should I make y0=(-4), making 63 positive, or keep y0=4, making 63 negative like it was before I did absolute values

    If I undid it to begin with, shouldn't I have to redo it?


    and either way - it doesn't make sense
    I get: x = 4 + 23t > 0
    and y = 11 - 63t > 0

    even if I turn 63 negative or positive - they equal the same thing ... ? therefore no solutions?
    essentially it won't matter, since you could get the same solutions by choosing a different range for t, but, for consistency sake, you want to keep the 63 negative as that is how the problem started out
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    ok, but either way there are no integer solutions ...
    Follow Math Help Forum on Facebook and Google+

  12. #12
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by cassiopeia1289 View Post
    ok, but either way there are no integer solutions ...
    how so? x = 5, y = 14 work, for instance

    your first solution was correct. i got it to be x = 5 + 23t and y = 14 + 63t. they cover the same thing
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    but the only reason I got 5 and 14 was because I was using the gcd to be -1 - which can't work
    when I start over again, with positive numbers, I get the gcd to be 1 and x0=4 and y0=11, hence my problem
    Follow Math Help Forum on Facebook and Google+

  14. #14
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by cassiopeia1289 View Post
    but the only reason I got 5 and 14 was because I was using the gcd to be -1 - which can't work
    when I start over again, with positive numbers, I get the gcd to be 1 and x0=4 and y0=11, hence my problem
    yes, that is because 1 = (-63)*4 + 23*11

    but remember, we don't want the linear combination to be 1, we want it to be 7, so multiplying through by 7, we get 7 = (-63)*28 + 23*77

    so actually, your x0 = 23 and your y0 = 77


    you got this last time, maybe you're just tired why you can't see it now

    look back on your other post before this one, you did exactly what i just did
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Member cassiopeia1289's Avatar
    Joined
    Aug 2007
    From
    chicago
    Posts
    101
    haha - wow - I keep forgetting to do that step, like on all my problems, its really would be humorous if it wasn't so sad

    but still: even when x0=28 and y0=77, you get t > -28/23 and t > -77/63
    which doesn't work because a) they're negative and b) there is no integer in between those intervals

    however, it DOES work if I don't convert the 63 into a negative - then it works out perfectly ...
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. elem#theo - phi and odd #
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: December 2nd 2008, 06:45 PM
  2. elem.num.theo - diophantine equations
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 9th 2008, 02:23 PM
  3. elem.num.theo - GCD
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: October 9th 2008, 01:23 PM
  4. elem.num.theo - help w/proof
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 26th 2008, 06:18 AM
  5. elem. # theo - gcd(a, a+n) divides n ...
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 23rd 2008, 08:25 PM

Search Tags


/mathhelpforum @mathhelpforum