Сравнение первой степени

Рассмотрим сравнение:

 

.

(4.2)

 

Под решением любого сравнения понимается класс вычетов по модулю , один элемент которого (а значит и все) удовлетворяют данному сравнению. Решить сравнение – значит найти все , которые удовлетворяют данному сравнению, при этом весь класс вычетов по модулю считается за одно решение.

 

Пример

Сравнение 5-ой степени: .

Класс вычетов для :. Данному сравнению удовлетворяют: , так как и . Таким образом, у данного сравнения есть два решения: и .●

 

Естественно, метод перебора затруднителен.

В случае сравнения первой степени если решение означает отыскание целых таких, что: , то есть . – это обратный к по модулюэлемент.

Умножим (2) на : . С учетом получаем:

 

(4.3)

 

Значит, сравнение первой степени имеет одно решение по модулю .

Если же , то для решения сравнения (2) необходимо, чтобы делил без остатка. При этом сравнение будет иметь решений: .

 

Пример

Решить сравнение .

Решение

. Поэтому по свойствам 11,7,8 функции сравнение: . Далее для решения сравнения можно использовать два подхода:

1. Алгоритм Евклида (применяется при небольших для нахождения : ).

2. Способ Эйлера. ●