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!

Answer

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.