Сравнения высших степеней по простому модулю.
Перейдем к рассмотрению вопроса о числе решений сравнения 
степени по простому модулю.
ТЕОРЕМА 4.3. Сравнение
степени 
по простому модулю 
имеет не более 
решений.
Доказательство проводится индукцией по 
. Если 
то сравнение имеет вид 
, где 
в этом случае сравнение имеет нуль решений. Предположим, что сравнение (1) имеет степень 
Если сравнение имеет решения, то для некоторого целого числа 
Вычтем это сравнение из (1). Тогда разность членов степени k имеет вид
при 
каждая разность содержит линейный множитель 
. Поэтому результат вычитания можно записать так:
где 
— некоторые целые числа, 
. Любое другое решение сравнения (1), скажем 
будет решением сравнения
Действительно, так как 
и модуль 
простой, то из сравнения
следует, что
Так как степень сравнения (4) равна 
то, по индуктивному предположению, сравнение (4) имеет не более 
решений. Следовательно, исходное сравнение (1) имеет не более 
решений.
СЛЕДСТВИЕ 4.4. Если сравнение апхп 
имеет более 
решений, то все его коэффициенты делятся на 
.
ПРЕДЛОЖЕНИЕ 4.5. Если 
— простое число, то сравнение 
имеет точно 
решений.
Это предложение непосредственно следует из теоремы Ферма, а сравнению удовлетворяют любые числа, не делящиеся на 
; решениями являются числа 
.
ТЕОРЕМА ВИЛЬСОНА. Если 
— простое число, то
Доказательство. Если 
, то теорема, очевидно, верна. Пусть 
Рассмотрим сравнение
Его степень меньше 
и в то же время это сравнение имеет 
решений: 
Поэтому согласно следствию 4.4 все коэффициенты сравнения (2) делятся на 
. В частности, последний коэффициент, равный 
делится на 
.
ТЕОРЕМА 4.6. Если 
— простое число и d — натуральный делитель числа 
, то сравнение
имеет точно d решений.
Доказательство. Пусть d — любой делитель 
Тогда сравнение
можно записать в виде
Согласно предложению 4.5, сравнение (2) имеет 
решений: 
. Каждое решение сравнения (2) должно удовлетворять одному из сравнений:
По теореме 4.3 сравнение (4) имеет не более 
решений. Поэтому сравнение (1) должно иметь не менее d решений. Следовательно, ввиду предложения 4.5 сравнение (3) имеет точно d решений.
