Доброго времени суток.
Задача: реализовать функцию находящую число 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).
Вопрос: подскажите пожалуйста, где в реализации ошибка.