МЕТОД СРАВНЕНИИ

283

должны быть специально выбраны для того, чтобы сравнение удо-

влетворилось). Примерами тождественных сравнений могут служить:

(mod 1 7), (а

а2 (mod Ь).

103

Примером сравнения, содержащего неизвестное, может служить:

х2 +12=0 (mod 10).

Мы будем здесь говорить только о сравнениях с одним неиз-

вестным. Такое сравнение называется алгебраическим степени п,

если оно имеет вид

Р (х) —0 (mod т),

где Р (х) аохПА- а, хп-1 Х —

многочлен сте-

пени П с целыми коэффициентами, причём ао (modm) (т. е. ао

не делится на модуль), подобно тому кик от алгебраического урав-

нения степени п мы требуем, чтобы коэффициент при

равнялся нулю.

В силу теоремы 2 мы непосредственно видим, что если число хо

удовлетворяет некоторому алгебраическому сравнению по модулю т,

то и любое число х, сравнимое с Хо по модулю т, также будет

ему удовлетворять. Для алгебраических сравнений, таким образом,

характерно, что корни их образуют целые классы по данному мо-

дулю; поэтому обычно решением алгебраического сравнения по

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

(по модулю т) чисел, удовлетворяющих данному сравнению. Соот-

ветственно этому под числом решений данного алгебраического

сравнения по модулю т понимают не число чисел, ему удовлетво-

ряющих (таких чисел всегда имеется либо ни одного, либо беско-

ночное множество), а число классов по модулю т, соетоящих из

удовлетворяющих ему чисел.

Мы, прежде всего, подробно рассмотрим наиболее важный слу-

чай линейных сравнений (т. е. сравнений первой степени) с одним

неизвестным, общий вид которых

ах=Ь (mod т).

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

полной системы вычетов по этому модулю соответствующие значе-

ния произведения ах в силу теоремы З будут представлять собой

полную систему вычетов по модулю т, так что одно и только

одно из этих значений будет сравнимо с Ь. Наше сравнение имеет,

таким образом, в этом случае в точности одно решение аналогично

уравнению первой степени с одним неизвестным.

Один из возможных способов фактического нахождения этого

решения даёт нам теорема Эйлера: так как

1 (mod т),

то

фа? (т) —b (1110d т),