public static int gcd(int a, int b) {
        if (a < 0)
            return gcd(-a, b);
        if (b < 0)
            return gcd(a, -b);
        if (a < b)
            return gcd(b, a);
        
        while (b > 0) {
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }