Обратные остатки

Рассмотрим два случая:

1) Тогда решений всего два и

2)

Для начала предположим, что и Тогда или Заметим, что если то верно поэтому и — различные решения.

Теперь будем считать, что то есть обратим.

Тогда умножим все сравнение на Получаем

По формуле разности квадратов:

Таким образом, и взаимно обратны по модулю то есть удовлетворяют системе

для некоторого обратимого Из этой системы следует, что поэтому решения существуют тогда и только тогда, когда обратим. Отметим, что если все-таки обратим, то и вычет тоже восстанавливается однозначно. Таким образом, система имеет единственное решение, если обратим.

Найдем такие для которых существуют обратимые такие, что необратим. Для этого рассмотрим сравнение Оно эквивалентно сравнению является квадратичным вычетом по модулю По критерию Эйлера, — квадратичный вычет тогда и только тогда, когда

Очевидно, это сравнение верно только если имеет вид а во всех остальных случаях является невычетом. Таким образом, задача разбивается на два случая.

1.

В случае имеется ровно два решения сравнения Таким образом, в качестве в систему можно подставить различных (все кроме решений указанного сравнения и ) и получится различных решения. Вспомним, что еще имеется два решения из поэтому общее число решений —

2.

В случае сравнение не имеет решений, поэтому можно просто подставлять любое из возможного. Учтем еще 2 решения из случая тогда получится решение.