§ 2. Распределение степенных вычетов в прогрессии.

В этом параграфе мы изложим содержание замечательного мемуара академика И. Виноградова "Элементарное доказательство одной общей теоремы аналитической теории чисел" . Пусть нечетное простое число и делитель числа . В § 6 гл. I мы указали разделение приведенной системы вычетов на классов по чисел в каждом классе, причем класс состоит из всех вычетов степени по модулю невычеты же степени распределяются между классами Класс можно определить также как совокупность тех чисел приведенной системы вычетов, индексы которых (по фиксированному первообразному корню) сравнимы с по модулю . В вышеупомянутом мемуаре И. Виноградов, основываясь на чрезвычайно остроумных и чисто арифметических рассуждениях, дает приближенную формулу для количества чисел любого класса содержащихся в арифметической прогрессии разность которой а не делится на Докажем предварительно несколько лемм.

Лемма Пусть — вещественные наела, k — целое число, большее нуля, и (см. теорему 8), где если целые числа и то

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

Подставляя вместо А его значение, находим где Так как линейная функция от х, то ее значения при заключаются между крайними значениями разность этих чисел, т. е. по абсолютному значению меньше единицы. Следовательно, целые числа Либо равны, либо отличаются на единицу. Разобьем сумму стоящую в левой части равенства (4), на сумм:

и рассмотрим одну из них Если то, полагая при имеем так как выражение в этой сумме пробегает полную систему вычетов по модулю то, обозначая через наименьший неотрицательный вычет по модулю имеем Если для суммы отличаются на единицу, то, обозначая меньшее из этих чисел через и полагая опять имеем для причем крайние значения удовлетворяют следующим неравенствам: одно другое Аналогично предыдущему находим

При имеет опять и только при если соответствующее значение х удовлетворяет неравенству имеем Поэтому, обозначая через нуль или единицу, получаем

и на основании указанных выше неравенств для крайних значений получаем где Замечая, что таких значений при

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

Лемма II. Пусть простое число, большее, чем 2, а — одно из чисел целое число, могущее меняться с изменением целое число Тогда, полагая

имеем

причем в сумме для каждого х суммирование производится по всем у из ряда взаимно простым с х. Рассматривая одну из сумм найдем по теореме 8 несократимую дробь удовлетворяющую условиям Полагая и разбивая сумму на части замечаем, что к первой части суммы можно приложить лемму I (считая Пользуясь формулой (4) и принимая во внимание, что находим для суммы выражение

Аналогично поступаем и с новой суммой Полагаем по теореме 8

и аналогично предыдущему для получаем выражение

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

причем, как и раньше, Складывая найденные выражения для получаем

откуда

и

В последней сумме предполагается, что числа а также число определены для каждого а, после чего берется сумма по всем указанным значениям а. Чтобы оценить величину этой суммы, соберем в ней все слагаемые вида для которых имеет одно и то же значение. Переписывая равенство в форме видим, что есть целое число, взаимно простое с и удовлетворяющее условиям обратно, задание чисел у (при фиксированных удовлетворяющих последним условиям, определяет число Желая найти верхний предел суммы тех членов в которых равны данному числу примем во внимание соответствующие этим числам значения Так как может принимать лишь значения взаимно простые с х. При выбранном соответствующее значение а определяется из сравнения Далее и потому сумма указанных членов будет не больше

суммы взятой по всем у из ряда взаимно простым с х. Отсюда, наконец, видим, что правая часть (6) не превосходит суммы что и доказывает лемму II.

Лемма III. Числа имеют то же значение, что и в предыдущей лемме; кроме того, пусть целые числа, бдльшие нуля и меньшие Обозначим через количество тех из чисел наименьшие вычеты которых по, модулю будут больше или равны нулю и меньше у, и положим

Тогда

где обозначает то же, что и в предыдущей лемме [см. (5)].

Лемма эта выводится непосредственно из предыдущей. Замечая, что или смотря по тому, будет ли наименьший вычет по модулю , или получаем

Но на основании предыдущей леммы

откуда

что и требовалось доказать.

Теперь мы можем формулировать упомянутую выше теорему И. Виноградова в следующем виде:

Пусть нечетное простое число, - любой делитель числа и числа разделены на классы вычетов и невычетов степени по модулю (см. выше). Если а — число, не делящееся на произвольное целое число и то количество чисел класса (при любом содержащихся в прогрессии представляется в виде причем и величина (та же, что и в леммах II и III) определяется формулою (5).

Пусть одно из чисел составим произведений

где а пробегает все числа класса независимо от Определим для каждого из этих произведений число и сравнением причем и обозначим через количество тех произведений (7), для которых соответствующие значения и меньше На вычислении этого количества двумя разными способами и основано доказательство теоремы. Рассмотрим сначала те произведения (7), которые соответствуют одному и тому же значению а. Полагая можем сравнение для и заменить следующим: где не зависит от х. Таким образом по обозначениям леммы III часть количества соответствующую постоянному а, можно представить в виде ; суммируя эти величины по всем а, находим

Подсчитаем теперь другим способом, оставляя в произведениях (7) постоянным число х. Если для взятого то все соответствующих произведений (7) должны быть присчитаны к

Если же для взятого есть одно из чисел класса содержащихся в данной прогрессии то в сравнении принадлежит к классу и легко видеть, что из всех чисел а существует таких, для которых [считаем при Отсюда

где если в данной прогрессии содержится в противном случае. Сравнивая найденные выражения для получаем при всяком

причем в правой части сумма берется по всем числам а класса Положим в и из полученной формулы вычтем почленно (8); принимая во внимание, что числа лишь порядком отличаются от получим

причем в правой части а и а пробегают все числа классов На основании леммы III правая часть последнего равенства не превышает и потому при любом складывая эти неравенства для всех с очевидным

равенством находим Положим тогда и так как то откуда в случае, если данная прогрессия не содержит нуля, очевидно, Если же эта прогрессия содержит нуль модулю то но из формулы видим, что откуда Итак, теорема доказана.

Из доказанной теоремы легко выводится другая теорема И. Виноградова относительно распределения первообразных корней в прогрессии. Вывод этой теоремы основан на следующем простом замечании: пусть любая совокупность целых чисел (в конечном числе); обозначим через количество тех чисел из которые делятся на число Тогда для любого целого сумма взятая по всем делителям числа , будет изображать количество тех чисел из которые взаимно просты с Это замечание легко доказывается на основании свойств функции Мёбиуса (§ 2 гл. I). Рассмотрим прогрессию отбросив число если оно имеется в этой прогрессии, возьмем индексы всех остальных чисел по некоторому первообразному корню. Примем совокупность этих индексов за в предыдущем замечании и положим Так как всякое число, индекс которого взаимно прост с будет первообразным корнем числа то для количества первообразных корней в данной прогрессии получаем формулу где сумма берется по всем делителям числа изображает количество чисел в данной прогрессии, индексы которых делятся на т. е. количество вычетов степени по модулю При по доказанной выше теореме при равно или и также можно положить Следовательно, где есть функция Эйлера (§ 2 гл. I). Замечая, что при делящемся на квадрат, а в остальных случаях получаем желаемую теорему: Количество первообразных корней в данной прогрессии может быть представлено в форме где

обозначает число различных простых делителей Чналогичную теорему можно вывести и для чисел, принадлежащих к данному показателю по модулю примечание к § 6 гл. I). Относительно величины грубая оценка показывает, что она будет порядка так что порядки добавочных членов в выведенных приближенных формулах для количества степенных вычетов и первообразных корней в прогрессии будут соответственно и