Results 1 to 4 of 4

Math Help - Particular solution for diophantine equation

  1. #1
    Newbie TriForce's Avatar
    Joined
    Nov 2010
    Posts
    20

    Particular solution for diophantine equation

    54x+15y=6

    I think that GCD(54,15)=3

    But then i am lost.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,789
    Thanks
    1147

    Re: Particular solution for diophantine equation

    Quote Originally Posted by TriForce View Post
    54x+15y=6

    I think that GCD(54,15)=3

    But then i am lost.
    well you can say

    18x + 5y = 2

    36x + 10y = 4

    36x-4 = 10y

    30x + 6x - 4 = 10y

    (6x - 4) mod 10 = 0

    x = 4

    then 36*4 - 4 = -10y

    140 = -10y

    y = -14

    checking 54(4) - 15(14) = 6

    there are probably more systematic and formal ways of solving this
    Last edited by romsek; February 12th 2014 at 11:32 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Nov 2013
    From
    California
    Posts
    2,789
    Thanks
    1147

    Re: Particular solution for diophantine equation

    Ok, with a bit less flailing

    54x+15y=6 ; simplify it by dividing any common factors, in this case 3

    18x+5y=2 ; rewrite this to eliminate one variable via modulo arithmetic

    5(3x+y) + (3x-2) = 0 ==> 3x-2 = 0 (mod 5) ; now solve this relatively simple modulo equation

    3*4-2 = 10 = 0 (mod 5) so x=4

    Now to solve for y simply plug in x above

    18(4)+5y=2

    5y=-70

    y=-14
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    708
    Thanks
    291

    Re: Particular solution for diophantine equation

    Hi,
    You should know a systematic way to find a particular solution of ax + by = c. Such a Diophantine equation has a solution if and only if gcd(a,b) divides c. So in this case divide both sides by the gcd. to arrive at an equation of the form ax + by = c with gcd(a,b) = 1. Now use the extended Euclidean algorithm to find m and n with am + bn = 1. Then x=cm and y=cn satisfy the original equation.

    Example:
    54x + 15y = 6 yields 18x + 5y = 2.
    By the Euclidean algorithm, 18(2) + 5(-7) = 1
    So x=4 and y=-14 is a particular solution.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] diophantine equation
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: January 11th 2011, 07:26 PM
  2. Diophantine equation .
    Posted in the Number Theory Forum
    Replies: 16
    Last Post: January 9th 2011, 06:06 AM
  3. Diophantine Equation? Or something?
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 1st 2010, 04:10 PM
  4. Diophantine Equation
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 13th 2009, 02:16 PM
  5. Diophantine equation
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: December 14th 2006, 12:13 PM

Search Tags


/mathhelpforum @mathhelpforum