Results 1 to 6 of 6

Math Help - Number of solutions : ax+by=n

  1. #1
    Newbie
    Joined
    Apr 2011
    Posts
    3

    Number of solutions : ax+by=n

    Hi,

    I want to know the number of solutions of the diophantine equation

    ax+by=n

    where a,x,b,y,n are positive and a,b,n are given.

    The first thing I do is checking whether n is a multiple of gcd(a,b). If this is not the case, there are 0 solutions. Otherwise we divide the equation by gcd(a,b) and thus can assume a and b are coprime.

    But what can I do now? The euclidean algorithm does not work since x and y have to be positive.

    Cheers,
    Plaso
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1
    Quote Originally Posted by Plaso View Post
    Hi,

    I want to know the number of solutions of the diophantine equation

    ax+by=n

    where a,x,b,y,n are positive and a,b,n are given.

    The first thing I do is checking whether n is a multiple of gcd(a,b). If this is not the case, there are 0 solutions. Otherwise we divide the equation by gcd(a,b) and thus can assume a and b are coprime.

    But what can I do now? The euclidean algorithm does not work since x and y have to be positive.

    Cheers,
    Plaso
    the euclidean algorithm doesn't restrict x,y to be positive. x and y can very well be negative.

    the number of solutions of ax+by=c are infinite if gcd(a,b) divides c. if (x1, y1) is any particular solution then (x1+[b/d]t, y1-[a/d]t) is also a solution for any integer 't'.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2011
    Posts
    3
    No, this exactly is the problem. The euclidean algorithm gets all solutions including the negative ones.
    I have to search for the number of the positive ones and only for the positive ones. Since that number is finite (that is pretty much obvious) and not infinite it is not that easy.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Behold, the power of SARDINES!
    TheEmptySet's Avatar
    Joined
    Feb 2008
    From
    Yuma, AZ, USA
    Posts
    3,764
    Thanks
    78
    I guess I need to ask a question to clarify for this problem are you given specific numbers for a,b and n or are you trying to devise a general formula for positive integer values.

    If you are looking for a general formula you may want to analyze a few specific cases to get an idea of what can happen. For example consider the equation

    2x+5y=3 this has no positive integer solutions (look at its intercepts) now consider x+y=5 what will the intercepts of the graph look like and what constrains will this generate.

    If it is the first case just find all solutions then use the x and y intercepts to restrict them. After that you should be able to find how many lie in the first quadrant.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2011
    Posts
    3
    I try to devise a general formula.

    Ok, I took a look and noticed there every x has the form x_1+ b*k with k being an integer. Furthermore x is greater than 0 and by looking at the x-intercept I can tell x has to be less than n/a.

    Now I divide n/a and b getting n/ab. So the number can be the greatest number smaller than n/ab as well as the smallest number greater or equal n/ab.

    But how do I decide which one is the right?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1
    Quote Originally Posted by Plaso View Post
    No, this exactly is the problem. The euclidean algorithm gets all solutions including the negative ones.
    I have to search for the number of the positive ones and only for the positive ones. Since that number is finite (that is pretty much obvious) and not infinite it is not that easy.
    if (x1,y1) is a particular solution then general solution is (x1+[b/d]t,y1-[a/d]t)=(x,y). d=gcd(a,b)
    apply x>0 and y>0. CASE:If x1>0 and y1>0
    you get t> (-x1)d/b and t < (y1)d/a.
    so the number of solutions is the number of 't's satisfying (-x1)d/b < t < (y1)d/a. that is G.I.F((y1)d/a) - G.I.F((-x1)d/b) +1. (or may be the '+1' is not there)
    here G.I.F is the greatest integer function. Similarly the other three cases can be treated.

    Now this is not a general formula but an algorithm can be written on the above idea.
    Is there a FORMULA to find GCD of two integers?I don't think there is but IF there is then the above can also be made to have a FORMULA.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of solutions
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: April 11th 2011, 06:07 AM
  2. Number of solutions
    Posted in the Discrete Math Forum
    Replies: 11
    Last Post: November 16th 2010, 08:15 AM
  3. Number of solutions of x^2 + xy + y^2 = 27 in Q
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: September 27th 2010, 01:37 AM
  4. number of solutions
    Posted in the Trigonometry Forum
    Replies: 3
    Last Post: May 3rd 2009, 07:16 AM
  5. Number of solutions
    Posted in the Calculus Forum
    Replies: 3
    Last Post: November 13th 2008, 08:36 AM

Search Tags


/mathhelpforum @mathhelpforum