Implement modInverse using Extended Euclid Algorithm in Java

Question

modInverse method of class BigInteger should not be used. I tried and used this method but it does not produce the correct result. Any help would be appreciated.

public static int[] extendedgcd(int a, int b) {
        if (b==0) {
            return new int[]{1, 0, a};
        } else {
            int output[] = extendedgcd(b, a%b);
            return new int[]{output[0], output[0]-((a/b)*output[1]), output[2]};
        }
    }

Answer 1

In the else-branch, the first return value should be output[1] instead of output[0]:

public static int[] extendedgcd(int a, int b) {
    if (b == 0) {
        return new int[]{1, 0, a};
    } else {
        int output[] = extendedgcd(b, a % b);
        return new int[]{
            output[1],
            output[0] - ((a / b) * output[1]),
            output[2]
        };
    }
}

You can test the implementation here: https://onlinegdb.com/volwDTwnl