扩展欧几里得算法

再会。

任务：实现一个函数，该函数找到与数 A 模 N 成反比的数 X（即 (X*A)%N==1）。数字 A 和 N 是已知的。

我是如何解决这个问题的：据我所知，这个问题通过扩展的欧几里得算法得到了很好的解决。所以我实现了以下功能：

private Triple getExtendGCD(long a, long n) {
    long s1 = 1, s2 = 0;
    long t1 = 0, t2 = 1;
    while(n != 0) {
        long quotient = a / n;
        long r = a % n;
        a = n;
        n = r;
        long tempS = s1 - s2 * quotient;
        s1 = s2;
        s2 = tempS;
        long tempR = t1 - t2 * quotient;
        t1 = t2;
        t2 = tempR;
    }
    return new Triple(a, s1, t1);
}

private final class Triple {

    final long GCD, A, B;

    private Triple(long gcd, long a, long b) {
        GCD = gcd;
        A = a;
        B = b;
    }

}

但是，它在以下测试用例中给出了不正确的答案：A = 2，N = 31（它给出 -15，但预期为 16）；A = 2，N = 101（产生 -50，预期为 51）。

问题：请告诉我执行中的错误在哪里。