Modular Inverse and BigInteger division

Question

I've been working on the problem of calculating the modular inverse of an large integer i.e. a^-1 mod n. and have been using BigInteger's built in function modInverse to check my work.

I've coded the algorithm as shown in The Handbook of Applied Cryptography by Menezes, et al. Unfortunately for me, I do not get the correct outcome for all integers.

My thinking is that the line q = a.divide(b) is my problem as the divide function is not well documented (IMO)(my code suffers similarly). Does BigInteger.divide(val) round or truncate? My assumption is truncation since the docs say that it mimics int's behavior. Any other insights are appreciated.

This is the code that I have been working with:

private static BigInteger modInverse(BigInteger a, BigInteger b) throws ArithmeticException {
    //trivial case: b = 0 => a^-1 = 1
    if (b.equals(BigInteger.ZERO)) {
        return BigInteger.ONE;
    }
    //all other cases
    BigInteger x2 = BigInteger.ONE;
    BigInteger x1 = BigInteger.ZERO;
    BigInteger y2 = BigInteger.ZERO;
    BigInteger y1 = BigInteger.ONE;
    BigInteger x, y, q, r;
    while (b.compareTo(BigInteger.ZERO) == 1) {
        q = a.divide(b);
        r = a.subtract(q.multiply(b));
        x = x2.subtract(q.multiply(x1));
        y = y2.subtract(q.multiply(y1));
        a = b;
        b = r;
        x2 = x1;
        x1 = x;
        y2 = y1;
        y1 = y;
    }
    if (!a.equals(BigInteger.ONE))
        throw new ArithmeticException("a and n are not coprime");
    return x2;
}

An example of input that is yielding incorrect input is:
a: 123456789
b: 2^809 - 1

An example of input that is yielding expected results is:
a: 123456789
b: 2^807 - 1

Answer 1

Here is how integer division is specified in the Java Language Specification:

JLS 15.17.2 Division Operator

Integer division rounds toward 0. That is, the quotient produced for operands n and d that are integers after binary numeric promotion is an integer value q whose magnitude is as large as possible while satisfying |d·q|<=|n|; moreover, q is positive when |n|>=|d| and n and d have the same sign, but q is negative when |n|>=|d| and n and d have opposite signs.

Answer 2

Change return x2; to return y2; and your routine will give the correct answer.

Edit, this answer is no longer valid, as the top poster changed his code.