Solve equation on the PC

Question

A friend of mine asked me to help him and make a small application to solve a problem. This problem can be reduced to this equation system:

aX = Yb; Y > c; Y < d; X is a whole number (X has nothing after . ); Y*10000 is a whole number (Y has no more then 4 digits after . );

eg. for a=185.5 b=1000000 c=4.3 d=4.4 a solution is X=23200 Y=4.3036

I have solved this doing this

for(i=c;i<d;i+=0.0001)
{
   if(b/i is a whole number)
   {
      i have a solution
   }
}

Is there a way to solve this more efficient? (from mathematical point of view can this be solved arithmetically?)

Answer 1

You don't have to work with Y not being whole numbers: multiply Y, c and d by 10000 and divide b by 10000. You still have the same problem now except that Y is a whole number. You want X = Yb/a. Next, find the gcd of a and b, call this g. Divide a and b by g, again you have the same problem as you had before except that now a and b are known to be coprime. It is easy to see now that Y = c + (a-c%a) is the smallest value of Y that can work. If this Y is less than d, then use this value to find X = Yb/a, else there is no valid Y that works.