Читать онлайн «Распределение простых чисел. Элементарные методы.»
Автор И. В. Зенкин
В. И. ЗЕНКИН
РАСПРЕДЕЛЕНИЕ ПРОСТЫХ ЧИСЕЛ
ЭЛЕМЕНТАРНЫЕ МЕТОДЫ
Калининград, 2008 г. © В. Зенкин, Калининград, 2008 г. Набор, иллюстрации и вёрстка автора. Оглавление
Список используемых обозначений 5
Введение. Постановка задачи 7
I. НАЧАЛЬНЫЕ СВЕДЕНИЯ О ПРОСТЫХ ЧИСЛАХ 10
1. Простейшие свойства функции π (χ) 10
2. Решето Эратосфена 12
3. Решето Лежандра 16
4. Критерии простоты 18
5. Бесконечность множества простых 21
6. Неравномерность распределения простых чисел ... 24
Задачи к главе 1 28
II. ВАЖНЕЙШИЕ ОЦЕНКИ 33
1. Функции Чебышёва 33
2. Неравенства Чебышёва 37
3. Постулат Бертрана (теорема Чебышёва) 44
4. Следствия из теорем Чебышёва 47
5. Суммы и произведения простых 50
Задачи к главе II 58
III. ПРОСТЫЕ ЧИСЛА-БЛИЗНЕЦЫ 60
1. Простые числа-близнецы 60
2. Теорема Бруна 63
Задачи к главе III 68
1У. ПРОСТЫЕ В АРИФМЕТИЧЕСКИХ ПРОГРЕССИЯХ 70
1. Решето Сельберга 70
2. Простые числа в арифметических прогрессиях ... . 74
V. ЗАКОН РАСПРЕДЕЛЕНИЯ ПРОСТЫХ ЧИСЕЛ 78
1. Формула Сельберга 78
2. Асимптотический закон распределения простых чисел 81
VI. ДЗЕТА-ФУНКЦИЯ 92
1. Тождество Эйлера 92
2. Дзета-функция Римана 94
Задачи к главе VI 95
VII. РЕШЕНИЯ ВОПРОСОВ 97
1. Задачи главы I 97
4
2. Задачи главы II 103
3. Задачи главы III 109
4. Задачи главы VI 110
5. Листинги программ 113
5. 1. Базовый класс 113
5.
2. Решето Эратосфена 115
5. 3. Каноническое разложение числа 117
5. 4. Решето Бруна 120
5. 5. Простые в арифметических прогрессиях ... . 123
5. 6. Арифметические функции 126
5. 7. Счастливые числа 132
VIII. ПРИЛОЖЕНИЯ 134
A. ТЕОРИЯ ЧИСЕЛ 134
1. Делимость чисел 134
2. Основная теорема арифметики 135
3. Арифметические функции 136
4. Закон обращения числовых функций 140
B. МАТЕМАТИЧЕСКИЙ АНАЛИЗ 142
1. Конечные суммы 142
2. Свойства функции [х] 143
3. Числовые ряды 144
4. Пределы и О-символика 147
5. Формула бинома 148
6. О сложности алгоритмов 149
Таблица простых чисел 151
Список иллюстраций 156
Предметный указатель 156
Литература 158
Список используемых обозначений
d \ a d делит а, равносильно существованию
целого αχ, такого, что а = da\\
а\Ъ а делится на (кратно) Ъ, равносильно
существованию целого аь такого, что а = Ъа\\
[х] целая часть вещественного числа х,
наибольшее целое число, не превосходящее х;
{х} дробная часть х, {х} = χ — [χ];
{п\ Л} множество элементов п, имеющих свойство Л;
(а, Ъ) наибольший общий делитель чисел а и Ъ, если,
в частности, (а,Ь) = 1, то а и Ъ называют
взаимно простыми;
[а, Ъ] наименьшее общее кратное чисел а, Ъ, НОК и
НОД связаны соотношением [а, Ъ] = аЪ/(а, 6);
π(χ) количество простых, не превосходящих х;
π2(:τ) количество близнецов, не превосходящих х;
12к<х> Пк<х сумма, произведение по всем натуральным
числам, не превосходящим х;
ΣΡ<ζχΐ ΥΙρίζχ сумма, произведение по всем простым числам,
не превосходящим х;
Σά\αι Yldia сумма, произведение по всем делителям а;
Σρΐ Yip сумма, произведение по всем простым числам;
А = В А равно В на основании N, где N обозначает
номер формулы или утверждения;
А = В А обозначено через В;
τ{η) количество делителей числа п, см. стр. 138;
σ(η) сумма делителей числа п, см. стр. 138;
μ(η) функция Мёбиуса, см. стр. 138;
φ(η) функция Эйлера, см. стр. 139;
θ(χ),φ(χ) функции Чебышёва, см. стр. 33;
Л(п) функция Мангольдта, см. стр. 78;
C(s) дзета-функция Римана, см. стр. 94;
а = Ъ (mod πι) а сравнимо с Ъ по модулю πι, равносильно
делимости (а — Ъ)\ πι;
\А\ количество элементов множества А. Делители подразумеваются только положительными.
