Solving an equation such that the solution is inetger

Question

I have an equation y*8.57E-7 = x with the constraints:

1. x>0
2. x should be an integer
3. y should be an integer

It might be solved with dynamic programming, but I am weak in analyzing it this way. For me the simple solution was to use brute force. But as expected it takes too much time, and it should be as we don't know in what domain the solution would lie. I also tried to use excel 'solve' but it is too abstract for this problem (I couldn't add 3rd constraint in it).

SO, what you guys do to solve these problems fast and in a better way. I usually counter these problems quite frequently, so there should be something to solve it fast or you can write anything on best practices and something or on some general appraoch. Maybe something using heuristics.

Here is my brute force code:

for x in range(1, 1000000000):
    y = int(1 / (x * 8.57E-7))
    if x * y * 8.57E-7 == 1:
        print(f"{x=}, {y=}")

(No solution whatsoever)

Answer 1

y × 8.57E-7 = x
y × 8.57 × 10^-7 = x
y × 857 × 10^-9 = x
y × 857 = x × 10^9

Now we know that:

• 857 divides x × 10^9;
• 857 and 10^9 are coprime.

Hence by Gauss' lemma, 857 divides x.

Hence there exists an integer w such that x = 857 × w.

Similarly, we know that 10^9 divides y × 857, and 10^9 and 857 are coprime, hence by Gauss' lemma, 10^9 divides y.

So there exists integers w and z such that:

y = z × 10^9
x = w × 857

But then we must have:

y × 857 = x × 10^9
z × 10^9 × 857 = w × 857 × 10^9
z = w

So we have proven that if x,y is a solution to your original equation, then there exists an integer z such that y = z × 10^9 and x = z × 857.

Conversely, if there exists an integer z such that y = z × 10^9 and x = z × 857, then you can easily check that y × 8.57E-7 = x.

As a conclusion, you can choose any integer z that you want, and then pick y = z × 10^9 and x = z × 857, and that'll give you a solution to the equation; and all solutions to the equation can be picked this way.

If you only need one solution, then you can for instance pick z = 1, which gives y = 1000000000 and x = 857.