Eulcid Problem

[Pier]

Hi!

Some time ago I've solved problem 10104 (Euclid Problem) by using Euclid's Extended Algorithm. The thing is that I didn't even considered the additional restrictions (|x|+|y| = minimum, x<= y if there's a tie). Recently I re-read the problem and come to wonder if the algorithm always gives a pair with those restrictions or if I just was lucky and the tests are incomplete. I've been trying to prove it (or finding a conter-example) and it seems that the algorithm aways meets the restrictions but haven't found a proof yet.

What I have tried is:
d = ax + by

So the general solutions are of the form:
d = a(x + (b/d)t) + b(y -(a/d)t)

Plotting the equation |x + (b/d)t| + |y -(a/d)t|, we have three line regions which make a V form (well, not exactly but kind of). So if the point we have is the smallest, then as we decrease (or increase) the value of t the sums will also increase. As the smallest is supposed to be t= 0, we just have to check for the values of t= 1 and t= -1. So we have to prove that:

|x| + |y| = |x + (b/d)| + |y - (a/d)|
|x| + |y| = |x - (b/d)| + |y + (a/d)|

and here's where I'm stuck (well, I've some more stuff but not much).

Also, I think that the minimum value (not necessarily integer) that the function can get is:
t = 2d(y-x)/(a+b)

I don't remember how I got this formula this value, but I didn't proved it (I'm not very good proving things, I usually get things by observation and "instinct"). I think this formula might also lead to something interesting.

Another method that I haven't tried much that might be a good idea is checking the minimum values of x and y as we calculate Euclid's Extended. The base values for x and y are 0 and 1, so this ones are obviously minimum, so we might check if the minimum property conserves as we calculate the new values of x and y. Have been able to prove this though.

I wanted to hear some comments as there might be better ways of proving this. Anyway, any help/comments/ideas appreciated!


Best regards,

Pier