BigInteger Extended Euclidean Algorithm recursion error

Question

I am trying to make an extended euclidean algorithm with the BigInteger. but I am keeping getting the error that

Exception in thread "main" java.lang.ArithmeticException: BigInteger divide by zero

I searched on google and it says that I might get an error because of the noninteger division

How should I solve this problem?

public static void main(String[] args) throws Exception{

    BigInteger ex1 = new BigInteger("9");
    BigInteger ex2 = new BigInteger("13");
    //if(eA.gcd(eB).equals(BigInteger.ONE))
//  {
        BigInteger[] val = gcd(ex1,ex2);
        
        System.out.println(val[1]);
        System.out.println(val[2]);
//  }
}

   // Returns a triple {d, a, b} such that d = a*p + b*q

   static BigInteger[] gcd(BigInteger p, BigInteger q) {
          if (p.equals(BigInteger.ZERO))
             return new BigInteger[] { p, BigInteger.valueOf(1), BigInteger.valueOf(0) };

          BigInteger[] vals = gcd(q, p.remainder(q));
          BigInteger d = vals[0];
          BigInteger a = vals[2];
          BigInteger b = vals[1].subtract((p.divide(q)).multiply(vals[2]));
          return new BigInteger[] { d, a, b };
       }
}

Answer 1

Here is the working variant, produced by Github Copilot (verified by me):

// Returns a triple {d, a, b} such that d = a*p + b*q
static BigInteger[] extendedEuclidean(BigInteger p, BigInteger q) {
    BigInteger[] val = new BigInteger[3];

    if (q.equals(BigInteger.ZERO)) {
        val[0] = p;
        val[1] = BigInteger.ONE;
        val[2] = BigInteger.ZERO;
    } else {
        BigInteger[] val2 = extendedEuclidean(q, p.mod(q));
        val[0] = val2[0];
        val[1] = val2[2];
        val[2] = val2[1].subtract(p.divide(q).multiply(val2[2]));
    }

    return val;
}

Note: when p=0 it returns q and vice versa.

The difference from your code, is that it checks that q != 0 (which is bound to become 0 at some point), instead of p != 0.

Tests:

input: 9, 13
d = 1, a = 3, b = -2

input: 2, 15
d = 1, a = -7, b = 1

input: 9, 12
d = 3, a = -1, b = 1

input: 0, 10
d = 10, a = 0, b = 1

input: 0, 0
d = 0, a = 1, b = 0

input: 1, 1
d = 1, a = 0, b = 1

input: 3, 0
d = 3, a = 1, b = 0