Расширенный алгоритм Евклида

Доброго времени суток.

Задача: реализовать функцию находящую число X обратное к числу A по модулю N (т.е. (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).

Вопрос: подскажите пожалуйста, где в реализации ошибка.