числа 1, 2, 3, 4, 6, 12 и

{1) + {2) + ¥(3) + ф) + ¥(6) + ¥(12) =

= 1 + 1 + 2 + 2 + 2 + 4 = 12. Общее доказательство можно дать, используя (8) или исходя непосредственно из определения функции (р(т).

В (I, 5) мы уже ссылались на таблицу значений (р(т) для всех т 10 000. В том же томе имеется таблица, в которой приводятся все значения т с данной величиной (р{т) для всех (f{m) 2500. Из этой таблицы видно, что при (f{m) 2500 каждое значение функции (f{m) принимается этой функцией не менее, чем дважды. Естественно предположить, что это верно и в общем случае, т. е. что для любого натурального т найдется отличное от т число т, для которого (f{m) = (f{m). Но это утверждение не доказано, и всякая попытка дать общее доказательство встречает непреодолимые трудности. Для чисел некоторых частных видов результат прост; например, если т нечетно, то (р{т) = (р{2т), если т не делится на 2 и на 3, то (р{3т) = ({Ат) = (р{6т),

5. Теорема Вильсона. Эта теорема впервые была опубликована Варингом в его «Алгебраических размышлениях» (Meditationes Algebraicae) в 1770 году; он приписал ее сэру Джону Вильсону (1741-1793), юристу, изучавшему математику в Кэмбридже. Теорема утверждает, что для любого простого р имеет место сравнение

{р- 1)! = -1 (mod р). (9)

Следующее простое доказательство принадлежит Гауссу. Это доказательство основано на сопоставлении каждого из чисел 1,2,..., р - 1 с числом, обратным ему по modp в смысле п. 2. Обратное к а - это такое число а, для которого аа = 1 (mod р). Каждое число из ряда 1, 2, ..., р - 1 имеет в этом ряду точно одно обратное. Число, обратное к а, может быть равно а; тогда

= 1 (mod р), т. е. а = ±1 (mod р), откуда следует, что а = = 1 или р-1. Все остальные числа 2, 3, ..., р - 2 (кроме 1 и р - 1) могут быть разбиты на пары, так что произведение чисел в каждой паре сравнимо с 1 по mod р. Следовательно,

2.3-4...(р-2) = 1 (modp).

АЛГЕБРАИЧЕСКИЕ СРАВНЕНИЯ 51

Умножив это сравнение на ) - 1, получим (так как р - 1 = = -1 {mod р)) сравнение (9). Если р равно 2 или 3, то приведенное доказательство не проходит; в этих случаях, однако, результат устанавливается непосредственно.

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

Sk = l + 2 + ,,, + {p-l) где р - простое, большее 2. Можно доказать, что если к не кратно р - 1 то Sk = О (mod р). Если к делится на ) - 1, то каждое слагаемое суммы Sk по теореме Ферма сравнимо с 1; а так как в этой сумме р-1 слагаемых, то она сравнима с р - 1 = -1 (mod р),

6. Алгебраические сравнения. По аналогии с теорией уравнений напрашивается рассмотрение алгебраических сравнений, т. е. сравнений вида

апх"" + an-ix~ + ... + ai; + ао = О (mod m), (10)

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

Если степень сравнения п равна 1, то (10) принимает вид aix + ао = О (mod m);

это - линейное сравнение рассмотренного в п. 2 вида.

Если число х удовлетворяет какому-нибудь алгебраическому сравнению по модулю т, то любое число я;, сравнимое с Х{) по mod m, также удовлетворяет этому сравнению. Поэтому два сравнимых между собой решения можно рассматривать как одинаковые и числом решений сравнения по mod т называть число решений этого сравнения в какой-нибудь полной системе вычетов по mod m, скажем в ряду О, 1, ..., т - 1. Например, сравнение я; = 8 (mod 13) удовлетворяется при х = 2, 5,

6 (mod 13) и только в этих случаях, поэтому оно имеет три решения.

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

Чтобы убедиться в этом, допустим, что модуль т раскладывается в произведение mim2, в котором mi и т2 взаимно просты. Алгебраическое сравнение

f{x) = О (mod т) (11)

удовлетворяется тогда и только тогда, когда удовлетворяется каждое из сравнений

f{x) =0 (modmi) и f{x) = 0{modm2). (12)

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

я; = 6, я; = 5, ... (mod mi), а решения второго через

X = rii, X = ri2, ... (mod 777.2). Каждое решение (И) порождает какое-нибудь и какое-нибудь 7]. Обратно, если выбрать одно из скажем и одно из ту, скажем r/j, то, как мы видели в предыдугцем пункте, пара сравнений X = (mod mi) и х = r/j (mod m2) эквивалентна ровно одному сравнению по модулю т. Следовательно, если N{m) - число решений сравнения (И), а N{mi) и N{m2) обозначают количества решений двух сравнений (12), то

N{m) = N{mi)N{m2). Другими словами, N{m) является мультипликативной функцией от т. Если m разложено, как обычно, в произведение степеней простых, то

N{m) = N{p)N{q)... (13)

Таким образом, если известно число решений алгебраического сравнения по модулям, равным степеням простых, то благодаря мультипликативности легко найти и число решений этого сравнения по произвольному модулю. В частности, если хотя бы одно из чисел N{p) равно нулю и р - входягцая в m степень