(?) Р числа ]9 и 5 дают при делении на 4а один и тот же остаток. Этим доказательство закона взаимности заканчивается.

Квадратичный закон взаимности - одна из наиболее известных теорем теории чисел. Он обнаруживает простое и в то же время замечательное взаимоотношение между разрешимостью сравнений = q (mod р) vl х = р (mod q), взаимоотношение, отнюдь не очевидное заранее. Стремление установить, что кроется за этим законом, было важным фактором в работе многих математиков и привело к далеко идуп1;им открытиям. Первое точное доказательство, данное Гауссом в его «Исследованиях», проводилось индукцией по двум простым р и q; такое доказательство сложно и мало удовлетворительно. Гаусс дал семь доказательств, основанных на совершенно различных методах и устанавливаюп1;их связь между законом взаимности и различными другими арифметическими теориями.

Закон взаимности дает возможность в каждом конкретном случае вычислять значения {а\р), не прибегая к рассмотрению вопроса о разрешимости сравнений. Вычислим, например, (3497). Первый шаг состоит в разложении 34 на 2 • 17. Так как 97 - простое вида 8А: + 1, то мы имеем (297) = 1, поэтому (3497) = (1797). Так как 17 и 97 - простые, не являюп1;иеся одновременно числами вида Ак + 3, то, по закону взаимности, (1797) = (9717) или (1217), так как 97 = 12 (mod 17). Далее (1217) = (317) = (173), опять-таки благодаря закону взаимности. Так как 17 = -1 (mod 3), то значение символа равно (-13) или -1.

Для кубических или высших степенных вычетов такого простого закона, как квадратичный закон взаимности, нет. Но можно кратко упомянуть об одном результате Гаусса, связанном с вычетами четвертой степени. Сначала мы должны напомнить, что, согласно результатам п. 1, теория вычетов четвертой степени интересна лишь для простых вида 4п+1, так как если р имеет вид 4п+3, то наибольший обилий делитель 4 и р-1 равен 2, т. е. в обозначениях п. 1 А: = 2, а потому в этом случае вычеты четвертой степени совпадают с квадратичными вычетами. Если же р имеет вид 4п + 1, то половина квадратичных вычетов суть вы-

Б - вычет, Н - невычет. [Прим. перев.)

четы четвертой степени (таковы те из них, индекс которых делится на 4), а другая половина и все квадратичные невычеты суть невычеты четвертой степени. Результат Гаусса состоит в том, что 2 есть вычет четвертой степени по mod р тогда и только тогда, когда простое р представимо в виде + 64. Надо отметить, что простое р вида 4п + 1 всегда представимо, как о? + 6 (это мы докажем в главе V); очевидно, одно из чисел а и b должно быть нечетным, а другое - четным. Таким образом, условие Гаусса состоит в том, что четное из чисел а и Ь должно делиться на 8. Например, 2 является вычетом четвертой степени по mod 73, так как 73 = 3 + 64.

6. Распределение квадратичных вычетов. Вернемся к вопросам, связанным с распределением квадратичных вычетов и невычетов по единственному простому модулю р. Мы знаем, что половина из чисел 1, 2, ...,р-1 - квадратичные вычеты, другая же половина - квадратичные невычеты. Уже первые наблюдения показывают, что если р - большое простое число, то вычеты и невычеты распределяются довольно случайно. Это распределение подчинено, конечно, известным законам, например мультипликативному закону, и тому факту, что всякий точный квадрат всегда является квадратичным вычетом.

Можно ставить разные вопросы, проверяюп1;ие случайный характер этого распределения. Можно спросить, например, как распределены вычеты и невычеты в подынтервале интервала от О до р. Пусть а vl (5 - две фиксированные правильные дроби; верно ли, что при большом р примерно половина чисел между ар и (5р - квадратичные вычеты? Если это так, то можно сказать, что квадратичные вычеты равномерно распределены. Это предложение действительно верно, но, кажется, не известно никакого элементарного доказательства этого факта.

Более простой вопрос, ответ на который дал Гаусс, связан с характерами последовательных чисел. Пусть п и п+1 - два последовательных числа в ряду 1, 2, ...,р-1; спрашивается, как часто они имеют предписанные значения характеров? Возможные значения характеров для пары чисел таковы: ВВ, ВН, НВ, НН\ Если квадратичные вычеты и невычеты распределены

случайно, то следует ожидать, что каждый из четырех указанных типов встречается примерно одинаково часто. Обозначим через (ВВ) и так далее число пар п, п + 1 с предписанными значениями характеров. Ясно, что (ВВ) + (ВН) равно числу пар, в которых п - квадратичный вычет. Здесь п принимает значения 1, 2, - 2. Полное число квадратичных вычетов

среди 1, 2, ..., - 1 равно {р - 1), а характер р-1, или -1, равен ( -1)"-)/. Поэтому

(ББ) + (БЯ) = Ь-2-е), (13)

где б = ( -1)"-)/. Аналогично

{HB) + {HH) = lip-2 + e), (14)

{BB) + {HB) = lip-l)-l, (15)

{BH) + {HH) = lip-l). (16)

Для четырех неизвестных имеются четыре соотношения, но они не независимы, ибо при сложении первых двух мы получаем тот же результат, что и при сложении двух последних. Поэтому, чтобы определить эти четыре неизвестных, нам нужно eni;e одно соотношение.

Рассмотрим произведение символов Лежандра и •

Оно равно +1 в случаях В В и НН и -1 в случаях ВН и НВ.

Значит, {ВВ) + {НН) - {ВН) - {НВ) равно сумме всех символов

fn{n + l)\

Лежандра - , где п принимает значения 1,2, ..р - 2.

Любое целое п из этого ряда имеет обратное по mod р, которое мы обозначим через ш. Но п{п+ 1) = п{1 + т) (mod р), откуда

п{п + 1)\ fl + m\

- . В то время как п принимает значения

\ Р /

1,2,..., р-2, т. е. все значения от 1 до р-1, кроме р-1, его обратное т также принимает все значения от 1 до ) - 1, кроме р - 1. Поэтому 1 + т принимает все значения от 2 до ) - 1. Сумма символов Лежандра этих чисел есть

/2\ /3\

+ ...+

(р-Л \ р )