# Extended Euclidean Algorithm with negative numbers minimum non-negative solution

I came through a problem in programming which needs Extended Euclidean Algorithm, with $$a*s + b*t = \gcd(|a|,|b|)$$ for $$b \leq 0$$ and $$a \geq 0$$

With the help of this post: extended-euclidean-algorithm-with-negative-numbers

I know we can just move the sign towards $$t$$ and just use normal Extended Euclidean Algorithm and use $$(s,-t)$$ as solution

However in my scenario, there is one more condition: I would like to find the minimum non-negative solution, i.e. $$(s,t)$$ for $$s,t\geq 0$$

And my question is how to find such minimum $$(s,t)$$?

Sorry if it sounds too obvious as I am dumb :(

Thanks!

Fact 1: One nice property of the Extended Euclidean Algorithm is that it already gives minimal solution pairs, that is, if $a, b \geq 0$, $|s| \lt \frac{b}{gcd(a,b)}$ and $|t| \lt \frac{a}{gcd(a,b)}$
Fact 2: If $(s,t)$ is a solution then $(s+k*\frac{b}{gcd(a,b)},t-k*\frac{a}{gcd(a,b)}), k \in \mathbb{Z}$ is also a solution.
Combining the two facts above, for your case in which $a \geq 0$ and $b \leq 0$, compute the pair $(s,t)$ using the extended algorithm on $(|a|,|b|)$, then either:
1. $s \geq 0, t \leq 0$, in this case $(s,-t)$ is the solution you want.
2. $s \leq 0, t \geq 0$, in this case $(s+\frac{|b|}{gcd(|a|,|b|)},-t+\frac{|a|}{gcd(|a|,|b|)})$ is your desired solution.