2
$\begingroup$

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!

$\endgroup$
2
+100
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Thanks for the answer, just one more little question: for case 2, (s+|b|/gcd(|a|,|b|),−t+|a|/gcd(|a|,|b|)) must be non-negative? $\endgroup$ – shole Jun 8 '15 at 0:55
  • $\begingroup$ Yes, they are guaranteed to be non-negative because of the bounds I mentioned in Fact 1. $\endgroup$ – mathosopher Jun 9 '15 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.