простого, то сравнение неразрешимо (это, конечно, очевидно и само по себе).

Аналогичный результат имеет место для алгебраических сравнений от большего числа неизвестных. Число решений сравнения

f{x,y) = о (mod т) от двух неизвестных (и аналогично от любого числа неизвестных) - мультипликативная функция модуля.

7. Сравнения но простому модулю. Имеются два обстоятельства, в силу которых теория сравнений наибольшее внимание уделяет сравнениям по простому модулю.

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

Вторая причина в том, что арифметика по простому модулю, как это уже отмечалось в п. 2, особенно проста. В этой арифметике имеется р элементов, представляемых числами О, 1, 2, ..., р - 1; здесь определены все четыре арифметических действия - сложение, умножение, вычитание и деление, кроме деления на 0. Первые три действия производятся как обычно, причем получаюгцееся в результате число переводится в исходную совокупность прибавлением к нему или вычитанием из него соответствуюгцего кратного р; последняя операция (деление) выполняется путем решения линейного сравнения.

Множество элементов произвольной природы, в котором определены операции, аналогичные четырем арифметическим действиям, удовлетворяюгцие тем же законам и выполнимые (кроме операции деления на нулевой элемент) внутри множества, называется полем. Самый известный пример поля - система рациональных чисел. Числа О, 1, ..., ]9 - 1, комбинируемые, как объяснено выше, также образуют поле; этот пример менее известен, но получаюгцееся поле прогце, ибо оно содержит конечное число элементов. Простейшим является случай р - 2.

в этом случае получается арифметика с двумя элементами. Если мы назовем их О и / (что соответствует О и 1), то получим такие правила действий:

0 + 0 = 0; 0 + 1 = 1; 1 + 0 = 1; 1 + 1 = 1; 00 = 0; 0-1 = 0; 1-0 = 0; 1-1 = 1. Можно сказать, что эта арифметика представляет собой вырожденную форму обычной арифметики, в которой каждое четное число заменено на О, а каждое нечетное число - на /.

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

йпХ + an-ix~ + ... + aix + ао = О (mod р), (14)

имеет не более п решений. Мы считаем, что старший коэффициент не сравним с О (mod р), ибо в противном случае соответ-ствуюгцее слагаемое можно было бы опустить.

Эту теорему впервые сформулировал и доказал Лагранж в 1768 году. Доказательство такое же, как и доказательство аналогичного факта для уравнений. Оно основано на том, что если Xl является решением сравнения, то полином в левой части сравнения разлагается на множители и одним из них служит линейный полином x - Xi. Действительно, если Xi удовлетворяет сравнению, то

апх\ + an-ix~ + ... + aiXi + ао = О (mod р).

Если вычесть это сравнение из (14), то разность членов степени к будет иметь вид ak{x - х\) при любом к из ряда О, 1, ..., п - 1. Каждая такая разность содержит линейный множитель X - Xl. Таким образом, сравнение (14) может быть записано в виде

{х - xi){bn-ix- + bn-2x- + ... + 6о) = О (mod р),

где 6п-ь • • Ьо - некоторые целые числа, зависягцие от а, .. ао и от Xl. Любое другое решение, скажем х2, сравнения (14) должно (так как р простое) удовлетворять сравнению

bn-ix""- + bn-2x~ + 6о = о (mod р) и, значит, порождает множитель х - х2в стоягцем здесь полино-

ме; так что в этом случае мы выделяем два линейных множителя исходного полинома. Это продолжается до тех пор, пока левая часть (14) полностью не разложится на множители или пока мы не придем к неразрешимому сравнению. В первом случае сравнение (14) имеет точно п решений *\ во втором случае - меньше, чем п решений.

Простота модуля в теореме Лагранжа сугцественна. Например, сравнение х - 1 = О (mod 8) степени 2 имеет 4 решения я; = 1, 3, 5, 7 (mod 8). (Это сравнение выполняется для любого нечетного числа.)

Мы видели, что каждое решение алгебраического сравнения отвечает некоторому линейному множителю соответствуюгцего полинома. Можно рассматривать и более обгций вопрос о разложении полинома с приведенными по модулю р коэффициентами на другие полиномы. Легко видеть, что любой полином f(x) можно разложить на неприводимые полиномы, т. е. на полиномы, которые далее не разлагаются. Другими словами, для всякого полинома f{x) сугцествуют неприводимые полиномы fi{x) /2(0;), ..., fr{x) такие, что

f{x) = fi{x)f2{x)... fr{x) (mod p) тождественно по x. Здесь, конечно, идет речь о неприводимости по отношению к данному простому р. Все линейные полиномы, встречаюгциеся в разложении, отвечают решениям сравнения f{x) =0 (mod р); если линейных множителей нет, то сравнение неразрешимо. Вот два примера разложения на неприводимые полиномы:

х+ 3x + 3= {х - 1){х + 1){х - 3) (mod 7), х"+ 2х - х + 2 = {х + х + 1){х + Х + 2) (mod 5), Возникает вопрос, единственно ли это разложение. Очевидно, что полиномы fi{x) fr{oo) можно умножить на числа, произведение которых сравнимо с 1 по mod р не изменив значения произведения /1(0;) • ... • /г(). С другой стороны, можно доказать, что с точностью до этой возможности разложение единственно. Рассматриваемая теория очень похожа на теорию разложения натуральных чисел на простые. Здесь снова важную роль играет алгоритм Евклида, основанный на процессе

*) Здесь каждое решение xi засчитывается т раз, если множитель x - xi входит в разложение левой части (14) т раз. {Прим. перев.)