Лабораторная работа № 9 Сравнения - ой степени по составному модулю.
Рассмотрим сравнение вида
(1)
и пусть 
, где
- простое число 
.
Теорема: Сравнение (1)
1. Равносильно системе сравнений
2. 
- число решений сравнения (1), где 
- число решений соответствующих сравнений системы.
Пример 1. Решить сравнение 
.
Решение: Данное сравнение равносильно системе 
и
. Решаем отдельно каждое сравнение (см. пример из лаб. раб. № 7). Сравнение имеет два решения 
. Сравнение имеет три решения 
, поэтому решаемое сравнение имеет 
решений. Чтобы найти эти 6 решений необходимо решить системы вида:
.
В нашем случае имеем 6 пар значений 
.
Но, так как 
, 
, то совокупность решений системы представится в форме 
. Таким образом, получим 
. Ответ: .
Теперь рассмотрим сравнение вида
, (2)
p - простое число.
Сравнение (2) можно свести к сравнению
. (3)
Действительно, всякое x, удовлетворяющее сравнению (2), должно удовлетворять и сравнению (3). Пусть 
- решение сравнения (3). Тогда 
. Подставим это значение x в сравнение 
. Получим 
. Раскладывая левую часть в ряд Тейлора ( за исключением первых двух слагаемых, все остальные содержат 
), получим
, 
или 
. (4)
В наиболее общем случае, когда 
не делится на 
, находим решение 
.
. Подставим это значение x в сравнение 
. Получим 
или 
. Здесь 
не делится на p, поэтому 
. Выражение для x принимает вид: 
. Продолжая данный процесс, при условии, что не делится на , получим в итоге решение сравнения (2): 
. Пример 2. Решить сравнение 
.
Решение: Сравнение 
имеет одно решение 
. 
- не делится на 3. 
. Тогда 
.
.
Если в сравнении (4) 
, а правая часть на p не делится, то сравнение (2) неразрешимо. Если же правая часть делится на p, то сравнение (4) является тождественным, и ему будут удовлетворять все целые числа 
.
Задания для самостоятельной работы:
1. 
2. 
3. 
4. 
5. 