Тема: Линейное модулярное уравнение
Здравствуйте!
Почитал http://e-maxx.ru/algo/diofant_1_equation
Мне кажется необходимо добавить весьма важную вещь - решение может быть не единственно в кольце вычетов по модулю N. А именно количество решений будет либо 0 либо gcd(A,N). Ну и как их все найти:
d=gcd(A,N);
Если B%d!=0 То решений нет
Иначе
Xi = ((A/d)^-1)*(B/d) + i * (N/d)) mod N , где i принадлежит [0;d-1]
Xi - решение i-ое
(A/d)^-1 - обратный элемент в кольце