Finding positive Bézout coefficients 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?

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.
