Wednesday, June 5, 2019

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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...