Finding positive Bézout coefficients

Question

If I have Bézout coefficients (obtained using extended Euclidean algorithm) and one of them is negative, what is the easiest way to obtain positive Bézout coefficients?

Answer 1

Given some natural $a$,$b$,$n$ we have the diophantine equation $$ax+by=n$$ which which we can find a solution for using Euclid's algorithm.

Let $(x,y)$ and $(x',y')$ be two distinct solutions then subtracting $ax+by=n$ and $ax'+by'=n$ we find $a(x-x')=b(y'-y)$. The question is what does this tell us about $x-x'$ and $y'-y$? It is difficult to deduce something from it since $a$ and $b$ are not coprime, so let $a' = \frac{a}{(a,b)}$, $b' = \frac{a}{(a,b)}$ and we have $a'(a,b)(x-x')=b'(a,b)(y'-y)$, now $a'|y'-y$ and $b'|x-x'$ so we must in fact have $y' = y + a'k$ and $x' = x-b'k$ for some integer $k$.

Reversing this, we can say that given any one solution $(x,y)$ we can parametrize all solutions by an integer $k$: $(x-b'k,y + a'k)$. If any positive solution to the diophantine equation exists, you can easily find it with this formula. If it doesn't you can use this formula to show that too.

Answer 2

Let $a,b,c$ be natural numbers. Can we solve $ax+by=c$ in naturals in a better way than using the euclidean algorithm? Obviously if $c < a+b$ we can't and if gcd(a,b) doesn't divide c we can't so lets suppose a,b,c coprime then we only really need to check if $y = (c-ax)/b$ is a positive integer for $1 \le x \le (c-b)/a$ as soon as its negative we can stop short knowing there are no solutions.