xa-by<c

[a1call]

Hi,
Not sure where would be the appropriate section for this. I figure it could be posted as a puzzle even though I don't know the answer.

For non zero positive integers a, b, c, x, and y,
find a general solution for x and y for the inequality:
0<|xa-by|<c

where:
c=|a-b|

Notes:

* There are values for a and b which there are no solutions for such as:
a = 66
b = 55

yet for:
a = 66
b = 57
66 - 57 = 9
13 x 66 - 57 x 15 = 3 < 9
i.e.:
x = 13 and y = 15

Thank you.

[retina]

Originally Posted by a1call

* There are values for a and b which there are no solutions for such as:
a = 66
b = 55

x=10, y=12

ETA: Nevermind, OP edited the original post stipulating an extra condition 0<|xa-by|<c.

[a1call]

Originally Posted by retina

x=10, y=12

ETA: Nevermind, OP edited the original post stipulating an extra condition 0<|xa-by|<c.

Originally Posted by retina

x=10, y=12

I just added the "0<" to the post.

Thank you for pointing that out.

[science_man_88]

the reason 66 and 55 can't work in the scenario you propose is simply because the difference is the GCD. in fact all such solutions with |a-b| = gcd(a,b) are out. so basically as long as c is in not equal to their gcd you can solve bezout's identity for their gcd and use that solution.

[a1call]

Originally Posted by science_man_88

the reason 66 and 55 can't work in the scenario you propose is simply because the difference is the GCD. in fact all such solutions with |a-b| = gcd(a,b) are out. so are all the ways to solve Bézout's identity, flipping the sign to deal with the subtraction still doesn't work. so basically as long as c is in not equal to their gcd you can solve bezout's identity for their gcd and use that solution.

I think you are correct about the difference being the GCD.
But the puzzle is still unsolved.
We still need a general solution for x and y.

[science_man_88]

Originally Posted by a1call

I think you are correct about the difference being the GCD..

I know I'm right as a=gcd(a,b)*(a/gcd(a,b)); and b=gcd(a,b)*(b/gcd(a,b)) so plugging these in as a and b gets you that for any x and y you always get a multiple of their gcd the lowest such positive multiple is the gcd itself. I still don't have the general solution you want if you actually want numbers.

[a1call]

Originally Posted by science_man_88

I know I'm right as a=gcd(a,b)*(a/gcd(a,b)); and b=gcd(a,b)*(b/gcd(a,b)) so plugging these in as a and b gets you that for any x and y you always get a multiple of their gcd the lowest such positive multiple is the gcd itself. I still don't have the general solution you want if you actually want numbers.

No not numbers, a general solution would be formulaic.
Thank you for introducing me to Bézout's identity.
See if that can produce a solution to the inequality.

[science_man_88]

Originally Posted by a1call

No not numbers, a general solution would be formulaic.
Thank you for introducing me to Bézout's identity.
See if that can produce a solution to the inequality.

if a-b = d*gcd(a,b) then multiplying a solution to bezout's identity by d-1 or less should solve it.

[Batalov]

Originally Posted by a1call

I think you are correct about the difference being the GCD.
But the puzzle is still unsolved.
We still need a general solution for x and y.

Step 1: A = a/gcd(a,b), B = b/gcd(a,b). Solution for (a,b) exists iff solution for (A,B) exists.
Step 2: if d = |A-B| <= 1, then there is no solution, because there is no d :: 0<d<1.
Otherwise, use Extended Euclidean algorithm

[a1call]

Originally Posted by Batalov

Step 1: A = a/gcd(a,b), B = b/gcd(a,b). Solution for (a,b) exists iff solution for (A,B) exists.
Step 2: if d = |A-B| <= 1, then there is no solution, because there is no d :: 0<d<1.
Otherwise, use Extended Euclidean algorithm

Thank you, I was just about to add the c>1 to the OP. Thank you for pointing that out.
Thank you for solving the puzzle. Didn't take that long.
I will now have to read up on the Extended Euclidean algorithm.