Но (

+ ... +

р-1\ Р J

= О, так как вычетов

столько же, сколько и невычетов. Поэтому интересующая нас

или -1. Таким образом,

сумма равна -

{ВВ) + (ЯЯ) - (БЯ) - (ЯБ) = -1.

(17)

Это соотношение, скомбинированное с помоп1;ью почленного сложения и вычитания с полученными ранее соотношениями, дает нам значения {ВВ) и др. Если сложить (17) с (13) и (14), получится {ВВ) + {НН) = (р - 3). С другой стороны, вычитание (14) из (15) дает {ВВ) - (НН) = -(1 + б). Отсюда (ВВ) и др. лежат между \{р - 5) и {р + 1). Поэтому утверждение о том, что они все примерно равны р для больших р, выполняется довольно хорошо.

Важным шагом в доказательстве была оценка суммы симво-/п(п+1)\ /0\

лов Лежандра

\ Р J

. Если мы условимся считать

= 0,

то можно вместо 1, 2, ..., р - 2 допустить для п все значения О, 1, 2, 1, не изменив суммы. Поэтому результат можно

выразить в форме

п{п + 1) Р

= -1,

(18)

где символ Е обозначает суммирование по полной системе вычетов по mod р. Можно показать, что этот результат имеет место

/п + Ьп + с\

и в более обп1;ем случае для любой суммы

квадратным полиномом, старший коэффициент которого равен 1, хотя и не только что использованным методом. Очевидное исключение представляет, конечно, случай, в котором полином является точным квадратом. Для полиномов более высоких степеней подобные вопросы глубоко исследовались в течение примерно последних двадцати лет. В 1934 году Хассе (Н. Basse) показал с помогцью очень трудных и глубоких методов, что зна-

чение любой кубической суммы

+ Ьп + сп + d\

лежит

между -2у/р и 2у/р*. В дальнейшем А. Вейль (А. Weil) обоб-П1;ил этот результат. Теорема А. Вейля имеет важные далеко идуп1;ие следствия.

Замечания к главе III. п. 1. Имеется другое доказательство суш,ествования первообразного корня, принадлежаш,ее Гауссу. Но я предпочел доказательство Лежандра как более конструктивное.

В согласии с теоремами Ферма и Эйлера (П, 3) число называют первообразным корнем по модулю ш, если порядок его равен (р{т). Гаусс доказал, что первообразные корни суш,ествуют для модулей 2, 4, р, 2р, где р - простое, большее 2, п - любое целое, и только для этих модулей.

п. 2. Таблица индексов для простых, меньших 97, имеется в книге Успенского и Хислета ().

п. 3. Можно вывести мультипликативное свойство и критерий Эйлера непосредственно из определения квадратичного вычета, не используя индексов, но такие доказательства менее наглядны.

п. 5. Применяя это рассмотрение к закону взаимности, я следую Шольцу (см. (19)).

п. 6. Факт равной распределенности вычетов и невычетов следует из одного важного неравенства, открытого Полна в 1917 году и независимо от него Виноградовым в 1918 году. Это неравенство устанавливает, что сумма символов Лежандра {п\р) (где п пробегает любую совокупность последовательных чисел п) по абсолютной величине меньше Ср logp, где С - некоторая постоянная. Так как \ogp мало по сравнению с р при больших то отсюда следует, что в любом интервале от ар до /Зр, где р - большое, а а и (3 - фиксированные числа, вычетов почти столько же, сколько и невычетов. О более глубоких результатах, связанных с распределением квадратичных вычетов и невычетов, см. работу Верд-жэсса (D. Burgess, Mathematika, 4 (1957), 106-112)**).

*) Элементарное доказательство теоремы Хассе дал Ю. И. Манин, см. (, гл. 10). {Прим. перев.)

**) Имеется перевод в журнале «Математика» (сб. переводов), 2:6, 1958, стр. 3-9. {Прим. перев.)

ГЛАВА IV

НЕПРЕРЫВНЫЕ ДРОБИ

1. Введение. В (I, 6) мы описали алгоритм Евклида для нахождения наибольшего o6ni;ero делителя двух данных чисел. Имеется eni;e один способ описания этого алгоритма, в результате которого отношение двух чисел представляется в виде непрерывной дроби. Этот способ станет ясным из следуюп1;его численного примера.

Применим алгоритм Евклида к числам 67 и 24. Последовательные шаги алгоритма таковы:

67 = 2-24+ 19, 24 = Ы9+ 5, 19 = 3- 5+ 4, 5 = 1- 4+ 1.

Последний остаток, равный 1, как известно, указывает на то, что числа 67 и 24 взаимно просты. Представим теперь каждое из этих уравнений в виде дроби:

67 19 24 5 19 4 5 , 1 24=2+24 19 = + l9 У = +5 4= + 4

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

Такое выражение называется непрерывной дробью. Для удобства печати принимается следуюп1;ая форма записи: