Results 1 to 5 of 5

Math Help - Linear diaphantine equations

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    2

    Linear diaphantine equations

    Do diophantine equations ax+by =C with gcd (a,b) = 1 have a solution?
    Consider the following diophantine equations
    30x + 17y = 30
    158x-57y=7

    gcd of both these equations are 1. So does that mean these equations have no solution?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3
    Dear mlsbbe,

    The diaphantine equation, ax+by=c have solutions iff (a,b)\mid{c}. So in your case (a,b)=1 and since 1\mid{c},~ ax+by=c have solutions.

    Therefore 30x + 17y = 30 and 158x-57y=7 have solutions.

    Hope this helps.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2010
    Posts
    2
    I've been trying to solve the linear diophantine equation, but to no avail:

    158x-57y = 7.

    I've used Euclid's algorithm to get

    gcd = -1

    -1 = 22*158 + 27*57

    Hence
    -1*7= -154*158 - 184*57

    This is apparently wrong. Can somebody help me?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2009
    From
    1111
    Posts
    872
    Thanks
    3
    Quote Originally Posted by mlsbbe View Post
    I've been trying to solve the linear diophantine equation, but to no avail:

    158x-57y = 7.

    I've used Euclid's algorithm to get

    gcd = -1

    -1 = 22*158 + 27*57

    Hence
    -1*7= -154*158 - 184*57

    This is apparently wrong. Can somebody help me?
    Dear mlsbbe,

    First of all (a,b)=d (the greatest common divisor of a and b is d) means the greatest positive integer that divides both a and b is d. Therefore by definition the greatest common divisor is always positive.

    When finding the greatest common divisor and the general solution to a Diophantine equation use the method I have given below.

    158x-57y = 7

    Using Euclid's algorithm,

    Since 158>57

    158=(57\times{2})+44

    57>44

    57=(44\times{1})+13

    44>13

    44=(13\times{3})+5

    13>5

    13=(5\times{2})+3

    5>3

    5=(3\times{1})+2

    3>2

    3=(2\times{1})+1

    Therefore, (158,57)=1

    Now using reverse substitution,

    1=3-2

    1=3-(5-3)=-5+(2\times{3})

    1=-5+2{13-(5\times{2})}=(-5\times{5})+(2\times{13})

    1=(2\times{13})-5[44-(13\times{3})]=(17\times{13})-(5\times{44})

    1=(-5\times{44})+17[57-44]=(-22\times{44})+(17\times{57})

    1=(17\times{57})-22[158-(57\times{2})]=(61\times{57})-(22\times{158})

    7=(158\times{(-22\times7)})-(57\times{(-61\times{7})})

    Therefore, x=-154~and~y=-427~is~a~particular solution.

    The general solution,

    x=-154-57t~and~y=-427-158t~;~t\in{Z}

    Hope this will help you to understand Diophantine equations.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,004
    Thanks
    1657
    Quote Originally Posted by mlsbbe View Post
    I've been trying to solve the linear diophantine equation, but to no avail:

    158x-57y = 7.

    I've used Euclid's algorithm to get

    gcd = -1

    -1 = 22*158 + 27*57
    What? The sum of two positive numbers cannot be -1!
    At first I thought perhaps you just had a sign wrong but
    22*158= 3476 and 27*57= 1539. They are not even close!

    Try again.

    Hence
    -1*7= -154*158 - 184*57

    This is apparently wrong. Can somebody help me?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 6
    Last Post: November 30th 2011, 01:41 AM
  2. Replies: 7
    Last Post: August 30th 2009, 10:03 AM
  3. Replies: 3
    Last Post: February 27th 2009, 07:05 PM
  4. Replies: 1
    Last Post: May 15th 2008, 08:23 PM
  5. Replies: 1
    Last Post: July 29th 2007, 02:37 PM

Search Tags


/mathhelpforum @mathhelpforum