Thread: 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

Originally Posted by Plaso

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'.

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.

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.

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?

Originally Posted by Plaso

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.