Extended euclidean algorithm for negative numbers

Question

How to correctly calculate the coefficients of the Bezout ratio for the case of negative numbers in the implementation of the extended euclidean algorithm? Here is my code:

#include <iostream>
#include <cmath>
#include <tuple>
 
using namespace std;
 
tuple<int, int, int> xgcd(int a, int b, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1) {
    if (b == 0) {
        return {abs(a), s1, t1};
    }
    int q = a / b;
    return xgcd(b, a - q * b, s2, s1 - q * s2, t2, t1 - q * t2);
}
 
int main(double argc, char ** argv) {
    tuple<int, int, int> result = xgcd(-10, -15);
    cout << get<0>(result) << " " << get<1>(result) << " " << get<2>(result) << endl;
 
    return 0;
};

In the presented case (-10, -15), the GCD is calculated correctly, but the Bezout coefficients require inverting the sign. What is the right way to deal with them? Thank you in advance!)

Answer 1

I figured out the problem. The solution is: replace a and b with their modules at the very beginning of the algorithm. But then the Bezout's coefficients will be found incorrectly. Let, for example, a < 0, and b > 0. Then after changing the sign of a, the resulting Bezout's identity will look like this:

gcd(a, b) = s(-a) + tb (in terms of -a and b)

or

gcd(a, b) = -sa + tb (in terms of a and b).

In general , for a and b arbitrary signs , this will be written

gcd(a, b) = sgn(a)sa + sgn(b)tb.

Thus, if we change the sign of a, then we must change the sign of s. Similarly, if we change the sign of b, then we must change the sign of t. Thus, the algorithm in recursive form will be written as follows:

    tuple<int, int, int> xgcd(int a, int b, int sign_a = 0, int sign_b = 0, int s1 = 1, int s2 = 0, int t1 = 0, int t2 = 1) {
        if (!sign_a) {
            sign_a = a < 0 ? -1 : 1;
        }
        if (!sign_b) {
            sign_b = b < 0 ? -1 : 1;
        }
        a = abs(a);
        b = abs(b);
        if (b == 0) {
            return {a, sign_a * s1, sign_b * t1};
        }
        int q = a / b;
        return xgcd(b, a - q * b, sign_a, sign_b, s2, s1 - q * s2, t2, t1 - q * t2);
    }