Results 1 to 5 of 5

Thread: 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
    4
    Dear mlsbbe,

    The diaphantine equation, $\displaystyle ax+by=c$ have solutions iff $\displaystyle (a,b)\mid{c}$. So in your case (a,b)=1 and since $\displaystyle 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
    4
    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.

    $\displaystyle 158x-57y = 7$

    Using Euclid's algorithm,

    Since 158>57

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

    57>44

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

    44>13

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

    13>5

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

    5>3

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

    3>2

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

    Therefore, (158,57)=1

    Now using reverse substitution,

    $\displaystyle 1=3-2$

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

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

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

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

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

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

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

    The general solution,

    $\displaystyle 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
    19,718
    Thanks
    3003
    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: Nov 30th 2011, 01:41 AM
  2. Replies: 7
    Last Post: Aug 30th 2009, 10:03 AM
  3. Replies: 3
    Last Post: Feb 27th 2009, 07:05 PM
  4. Replies: 1
    Last Post: May 15th 2008, 08:23 PM
  5. Replies: 1
    Last Post: Jul 29th 2007, 02:37 PM

Search tags for this page

Search Tags


/mathhelpforum @mathhelpforum