PRIMZAHLEN

von

DR. ERNST TROST

VERLAG BIRKHAUSER • BASEL-STUTTGART

ЭРНСТ ТРОСТ

ПРОСТЫЕ ЧИСЛА

Перевод с немецкого Н. И. ФЕЛЬДМАНАпод редакцией А. О. ГЕЛЬФОНДА

ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВОФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ

МОСКВА 1959

11-4-1

АННОТАЦИЯ

Книга посвящена одной из областей арифметики — теории простых чисел. Автор поставил себе целью изложить некоторые теоремы «элементарной» теории простых чисел и сообщить наряду с этим о различных интересных результатах в этой области. Для чтения книги достаточно знания школьной алгебры и простейших фактов дифференциального и интегрального исчисления. В книге изложены элементарные доказательства асимптотического закона распределения простых чисел, найденное Сельбергом и Эрдошем в 1948 г., и теоремы Дирихле о простых числах в арифметической прогрессии. Специальная глава содержит основы метода решета Бруна.

ОГЛАВЛЕНИЕ

Предисловие 7

Основные положения и предварительный обзор 9

Теоретикочисловые функции23

Общие критерии простых чисел30

Специальные простые числа41

Суммы по простым числам52

Общие теоремы относительно тс (х)ирп60

Элементарное доказательство асимптотического закона распределенияпростых чисел 80

Элементарное доказательство теоремы об арифметической прогрессии88

Метод решета94

Гипотеза Гольдбаха 106

Приложение. А. О. Гельфонд, Аналитический метод оценки числа простых чисел в натуральном ряде и арифметической прогрессии113

Литература 132

Литература к приложению135

ПРЕДИСЛОВИЕ

Простые числа, как основные составные элементы натуральных чисел, более или менее подробно изучаются в каждом учебнике теории чисел, однако при этом обходятся сравнительно немногими теоремами. Самостоятельная теория простых чисел является менее известной специальной областью арифметики. Она отличается просто формулируемыми постановками задач и в то же время сложными, часто аналитическими, доказательствами. Многие проблемы ожидают здесь еще своего решения.

Мы поставили перед собой задачу доказать некоторые теоремы «элементарной» теории простых чисел и наряду с этим сообщить о различных интересных результатах, чтобы помочь ознакомлению читателя с этой богатой замечательными методами областью. Принимая во внимание ограниченный объем книги, многое приходится, конечно, пропустить, в особенности мы экономили в литературном указателе. В работах Ландау [12], Ингама [9] и Диксона [5] читатель найдет в изобилии дальнейшую информацию (см. список литературы на страницах 132—134).

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

Сенсацией первого ранга явилось открытие П. Эрдёшем и А. Сельбергом в 1948 году элементарного, т. е. не зависящего от средств теории функций, доказательства асимптотического закона распределения простых чисел. Общее, косвенное доказательство этих авторов (см. Эрдёш [6]) сделано общедоступным ван дер Корпутом и Нагеллем [17]. Мы приводим здесь слегка измененное конструктивное доказательство Сельберга (Сельберг [22]).

Развитая в 1920 году Вигго Бруном в высшей степени оригинальная идея использования эратосфенова решета привела к созданию одного из сильнейших методов теории простых чисел, не лишившегося своей продуктивности и сегодня. Изложенный нами метод Бруна в равной мере пригоден для вывода оценок сверху и снизу, тогда как новый метод решета Сельберга, на который ввиду недостатка места мы можем лишь сослаться, пригоден только при оценках сверху, но зато привел здесь к наилучшим возможным результатам.

Различные господа поддержали меня сообщениями и присылкой работ. Моя благодарность в первую очередь относится к Н. Г. В. X. Бигеру (Амстердам), В. Бруну (Осло), П. Эрдёшу (Лос-Анжелос), X. Мейеру (Цюрих), Б. ван дер Полю (Гент), А. Реньи (Будапешт), Д. Риччи (Милан), X. Е. Ри- херту (Геттинген), А. Сельбергу (Принстон), В. Серпинскому (Варшава). За побуждение к составлению этой книги и многочисленные ценные дискуссии сердечно благодарю издателя этой книги, моего коллегу Л. Лохер-Эрнста.

Цюрих, апрель 1953 г.

Эрнст Трост

ОСНОВНЫЕ ПОЛОЖЕНИЯ И ПРЕДВАРИТЕЛЬНЫЙ ОБЗОР

Делимость. Элементарная теория чисел занимается в первую очередь натуральными числами 1, 2, 3,... Присоединив нуль и целые отрицательные числа, получим область всех целых чисел, в которой неограниченно выполнимы операции сложения, вычитания и умножения. Для деления это не так, поэтому понятие делимости играет важную роль. Если натуральное число а представимо в виде произведения a = dd\ где d и df — натуральные числа, то d называется делителем а. В таких случаях употребляют обозначение d | a. d' называется дополнительным к d делителем а. Каждое а имеет тривиальные делители 1, а.

Чтобы проверить, имеет ли место d | а, проведем деление a*.d и получим представление a = qd-^r, где ^^0 — частное и O^r^d—1—остаток. Случай г = 0 характерен для d | а. Частное может быть также записано в форме q = ^d^ причем [а] для положительного вещественного а обозначает наибольшее целое число ^а).

Простые числа. Натуральное число р^=\ называется простым), если оно не имеет никаких нетривиальных делителей. Число 1 целесообразно не считать простым, так как каждое целое число делится на 1 в сколь угодно большой степени. Таким образом, последовательность простых чисел начинается числами 2, 3, 5, 7, И, 13, 17, 19, 23, 29,...; 2 — единственное четное простое.

Легко видеть, что каждое а^\ имеет по крайней мере один простой делитель р | а. Действительно, наименьший де

литель р=^ 1 числа а обязательно должен быть простым, так как в противном случае он сам имел бы нетривиальный делитель, меньший чем р, что противоречит минимальности р.

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

Теорема 1. Каждое натуральное число п однозначно, если не учитывать порядок множителей, представимо в виде произведения простых чисел п = рх р2.. .рг (г^1).

Доказательство. Легко доказать существование такого разложения. Отделим в первую очередь наименьший делитель рх ^= 1, который по предыдущему замечанию является простым числом. В дополнительном делителе снова отделим простое число р2 ^ рх и т. д.; так как дополнительные делители при этом все время убывают, то эта операция оборвется на простом числе рг Таким образом получаем так называемое каноническое разложение л>1:

”= Р^'Р?---Рб* (Р, <Р2<-•-<РД ^S3(1)

Однозначность разложения (1) получим следующим образом: или любое п разлагается однозначно, или существует наименьшее число т с двумя различными разложениями m = pvp2... •. .ps = qxqv • ^t MR— простые числа). Каждое р; отлично от всех qk, так как если, например, р1=^1, то т\рх имело бы два различных разложения, хотя число т\рх меньше, чем т.

Предположим, что qx — наименьшее простое, встречающееся в обоих разложениях т. Делением получим:

p^q^i-Vr., рг=qiQ4-\-rt> • • • > Ps=qtQs+rs

и отсюда перемножением

m = p,p2.. -Ps = r,rt.. .г^ + ^Р^,^. • ^v

R = rxr2...rs также делится на qx. Так как qx<^P(, то 0 <^R <Ст, следовательно, R, как и все г., однозначно разложимо в соответствии с предположением. Так как ri<^qx1 то простой множитель qx не может входить в его разложение и R не делится на qv Итак, предположение о существовании числа т с двумя различными разложениями привело к противоречию, что и доказывает однозначность разложения.

Если п составлено из малых простых множителей, то его каноническое разложение легко найти. Нужно лишь перепробовать простые p^V п^ так как каждое составное п содержит простой множитель ^ )/ п. При этом полезны таблицы множителей, такие, как таблицы Лемера т), в которых для любого п < 10 017 000, не делящегося на 2, 3, 5, 7, указан наименьший делитель.

В дальнейшем нам понадобится каноническое разложение числа п\ Очевидно, в п\ входят все р^п, так что нужно определить лишь соответствующие показатели ер. Среди чисел 1, 2, 3,..., п имеется \n]p^ кратных р, [п^р] кратных р2 и т. д. Точно \п[рг^ — Vnlpr+4 чпсел делятся на р\ но не делятся на pr+1. Таким образом,

( Г Л 1Г П 1 | Г 72 1 , Г 72 1 ,

^llyJЫ / " Ы + W + ''' ’ I

= Д/A]

Ряд для ep оборвется, как только будет ^r>/z.

Разложение (1) дает полное представление о делителях /z, число которых равно, очевидно, (^ Ц-1) (^2 4~ 0 • • • (^ 4~ В- Если в (1) все ^.= 1, то среди делителей п нет полных квадратов и п называется свободным от квадратов.

Количество простых чисел» Разложение (1) ничего не говорит о количестве различных pt Можно было бы подумать, что все и составлены из конечного числа р. То, что это не так, заметил уже Эвклид2), который показал, что для каждого простого числа есть большее.

Теорема 2. Число простых чисел бесконечно.

Доказательство. Допустим, что существует наибольшее простое число р и Р = 2 • 3 • 5 • 7 • . . . .р— произведение всех простых чисел. Число Р-\- 1 не делится ни на одно из этих простых чисел, так как в остатке каждый раз получится 1. Поэтому Р-|-1 или само является простым числом > р или произведением простых чисел ^>р. Мы пришли к противоречию. Примеры: 2.34-1=7; 2-3 5-|-1=31; 2-3-5-7-|-1 =211, 2.3.5-7.114- + 1 =2311, 2-3-5.7 - И • 13-|- 1 = 30 031 =59-509.

9 D. Н. Lehmer, Carnegie Inst. Publ. 105 (Вашингтон, 1909). История таблиц множителей очень интересна. См. D. Н. Lehrner [13].

Из доказательства Эвклида можно получить грубую оценку сверху для величины я-го простого числа р п^рх = <21 р^^З^./у Выведем эту оценку по индукции. Предположим, что

^2,р%^\^2< р^\..,.Рп^”1-

Так как рп+х не больше наименьшего простого делителя числа рхрг. . .^4" 1> т0

рп+1<т---рп+1^2,+2+--- + 2’,” + 1 = 22П.

Решето Эратосфена является очень старым и простым методом для составления таблицы простых чисел, не превосходящих числа N. Пишут подряд числа от 2 до N. Число 2, как простое, оставляется, а все остальные четные числа вычеркиваются. Первое незачеркнутое число — это простое число 3. Далее, зачеркиваются все числа, кратные 3. Если таким методом найдены все p^pt и зачеркнуты все числа, кратные pt1 то первое следующее за pt незачеркнутое число — это простое число pt-px, так как оно не делится ни на одно p^pt. Если найдено Pt^V N, то все еще незачеркнутые числа будут простыми, так как кратные kpt ^ N вследствие неравенства к <^V N уже вычеркнуты раньше, как кратные простым числам <Zpt.

Пример. N = 50

23456789ТО

ИТ21314ТбТб17181920

2Т222324252627282930

31323334353637383940

41424344454647484950

В качестве простых чисел <50 получаем: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.

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

I] ОСНОВНЫЕ ПОЛОЖЕНИЯ И ПРЕДВАРИТЕЛЬНЫЙ ОБЗОР 13 сколь угодно большие пропуски. Среди т последовательных чисел (w -|~ U> 2, (tn 4~ 1)! 4" 3,. . ., (in -|- 1)! 4* т 4* 1 простых чисел нет, так как первое делится на 2, второе на 3, последнее на т-\-\. Позднее мы увидим (теорема 40), что имеются сколь угодно длинные цепи сколь угодно больших пропусков. Пропуск длиной 34 лежит между 1327 и 1361, а также между 8467 и 8501. Между 370 261 и 370 373 лежит пропуск длины 112.

С другой стороны, существуют простые числа р, р-\-2 с минимальным расстоянием 2. Примерами таких простых чисел-близнецов являются 41, 43; 2309, 2311; 10 016 957, 10 016 959. До сих пор неизвестно, является ли число таких пар простых близнецов конечным или бесконечным. Однако можно показать, что отношение числа близнецов ^ N к числу всех p^N стремится к нулю с ростом N (ср. §68). Имеется 1224 пары близнецов до числа 100 000 и 8164 пары до 1 000 000. Для количества простых чисел соответственно имеем 9592 и 78 498. Существуют также тройки р, р-\-2, р-^-6) и четверки р, р-]-^, P^V^ р4~^- Примеры: 5, 7, 11; 10 014 491, 10 014 493, 10 014 49 7; 294 311, 294 313, 294 317, 294 319, 299 471, 299 473, 299 477,299 479.

Функция распределения простых чисел. Изучение распределения простых чисел концентрируется в первую очередь на поисках функции п(х), дающей количество простых чисел х. Примеры: п(1) = 0, п(2)=1, п(20) = 8, тг (107) = 66 4 5 79, п (109) = 50 847 478, п (р J = п, если рп — п-е простое число.

Хотя для функции п (х) неизвестна никакая простая формула, можно, однако, сформулировать далеко идущие утверждения о се порядке. Наиболее выразительным является закон распределения простых чисел, предсказанный еще Гауссом и впервые доказанный Адамаром и де ла Валле-Пуссеном, который гласит, что отношение п (х) и функции / (x) = x/logx) стремится к 1 с ростом х. Относительная ошибка |п(х) — — /Wj/^W» возникающая при замене п (х) на /(х), становится таким образом с ростом х сколь угодно малой. Этот центральный результат мы пока отметим как

Теорему о. lim — I или п (х), '

X —> QOХ

Элементарное доказательство этой теоремы будет дано в главе VIII. Возможность доказательства этой теоремы без применения методов теории функций долгое время вызывала сомнения, поэтому открытие такого доказательства в 1948 г. Сельбергом и Эрдёшем явилось большой сенсацией.

Простые числа в арифметических прогрессиях. Нечетные р имеют вид 4/7 4~ I или 4/г —(—3. Методом Эвклида легко показать, что существует бесконечно много простых чисел обоих видов. Покажем это для вида 4/7 4~3. Положим Р = Т -3-5- . . . -р—I, где в первый член входят в качестве множителей все простые числа р, так что Р будет вида 4/г 4-3. Р не может состоять из простых множителей только вида 4/7 Ц-1, так как произведение в этом случае также имело бы вид 4/7^ • Таким образом, Р делится на простое

число вида 4/7 4~3, которое >р.

Аналогично получается, что существует бесконечно много простых чисел вида 6/7 4™ 5. За исключением 2 и 3, все простые числа имеют вид 6/?4~l или 6п 4“ 5. Р= 2 • 3 • . . . -р—1 имеет вид 6/?4~5 и не может состоять только из множителей вида 6/7 4~ 1, так как тогда и произведение имело бы такой вид. Таким образом, существует простое число вида 6/7 4- 5, которое > р.

Эти факты являются частными случаями следующей знаменитой теоремы Дирихле (теорема об арифметической прогрессии):

Теорема 4. Каждая арифметическая последовательность a-^-kd (& = 0, 1, 2, ...), где к и а не имеют общих делителей, содержит бесконечно много простых чисел.

Элементарное доказательство этой теоремы будет дано в главе VIII.

Общий наибольший делитель. Можно записать (1) также в форме бесконечного произведения, распространенного на все простые числа pt (/ = 1, 2, 3, ...). При этом показатель af простого числа pt, не входящего в а, равен нулю.

]) Утверждение / (х) — g^ равносильно утверждению lim /(x) g (х) — 1. В таком случае говорят об асимптотическом ра-

оо

а = II Рм а^ ^ 0 для /^1, а, > 0 лишь для конечного z = l

числа L

Очевидно, утверждение d\a равнозначно неравенству Sz^az для всех I, если dz играет для d ту же роль, что az для а. Если а и b представлены в такой форме, а tz = min (az, pz) обозначает наименьшее из чисел az и pz для az^pz и Tz = az

ОО

для az = pz, то число t — JJ р^ является делителем как для а1 Z=1

так и для Ь, т. е. общим делителем а и Ь. Так как rz для общего делителя увеличить нельзя, то / — общий наибольший делитель (о. н. д.) чисел а и Ь. Пишут / = (а, by Каждый другой общий делитель а и b является делителем t. Если ^сц #) = 1, то а и b называются взаимно простыми. Если под |xz = Max (az, ^z) понимать наибольшее из чисел az и pz, то

ОО

число т — JJ р^ будет кратным как числу а, так и Ь. Так z'=l

как ^ для общего кратного уменьшить нельзя, то т— общее наименьшее кратное (о. н. к.) чисел а и Ь. Пишут щт^^сц Ь]. Из равенства ab = JJ р^+& следует полезная формула ^а, Ь} = = аЬЦау by О. н. д. (а заодно и о. н. к.) может быть найден без использования разложения на простые множители с помощью алгоритма Эвклида (последовательное деление).

Сравнения. Делением на т > 0 можно все п > 0 разбить на т классов, поместив в один класс все числа, имеющие один и тот же остаток. Каждый класс характеризуется одним из остатков 0, 1, 2, . . . , т— 1. Два числа а и b одного и того же класса называются сравнимыми по модулю т. Пишут а ее b (т^т). Такое сравнение равносильно утверждению: а — b делится на т. В частности, равнозначны утверждения лп 16Z и (2 — 0 (mod ту Различают полную систему вычетов по mod т и приведенную систему вычетов по mod т в зависимости от того, рассматриваются ли все вычеты 0, 1, 2, ... , т—1 или те из них, которые взаимно просты с модулем.

Как и в случае равенства, из сравнений а = ах (mod ту b = bx (mod т) следует, что а + b ^ ах + bx (mod т) и ab = = axbx (mod ту Если / (х) многочлен от х с целыми коэффициентами, то из условия а = b (mod т) следует, что / (я) = = / (,b) (mod ту

В то время как сравнение можно умножать на любое целое число, делить можно лишь на числа, взаимно простые с модулем, как видно из примера: 5-9 = 5-3 (mod 10), 9^3 (mod 10). Из па ~ nb (mod т) следует лишь, что а = b [mod т^пг, z?)], так как в равенстве а — b = km^n правая часть — целое число, кратное т^т, nV

В качестве приложения докажем важное сравнение, найденное в частном случае т — р Ферма, а в общем случае Эйлером, ср (т) обозначает количество чисел <^т и взаимно простых с т, в частности ср (р) = р — 1.

Теорема 5. Если {а, т}=\, то а^^ = 1 (mod/и).

Доказательство. Если av a?, ... , а^^— вычеты, взаимно простые с т, то также и числа аах, аа^ . .. , аа^^ взаимно просты с т и различны по mod т, так как из аа( ~ = tt^(modw) следует а( ~ ak (mod mV Произведение чисел а{ сравнимо по mod т с произведением чисел аа( и после деления обеих частей этого сравнения на ахаг. . .а^ ^ получим доказываемое.

Если /(х)—многочлен и существует такое х0, что / (х0) = 0 (mod/тг), то х0— решение сравнения /(х) = 0 (modm). Вместе с х0 решениями сравнения будут, естественно, и числа x0-^-km, принадлежащие тому же классу вычетов. Из теоремы 5 вытекает, что сравнение ах ~ b (mod т^ при ^а, т^ = 1 имеет решение хй — a's^—xb.

Пример, а = 3, пг = 5, b = 2, ср (w) = 4, З2 = 4, З5 = 2, 34^1, х0 = 2-3 = 4 (mod 5), Зх ~ 2 (mod 5) имеет решение х = 4 (mod 5).

(3)(3)Если многочлен f (х) = айхп -(- ... -\-ап имеет степень п и модулем является простое число р, то сравнение / (х) = 0 (mod р) имеет не более п несравнимых корней. Это максимальное число достигается по теореме 5 для сравнения х77-1 = 1 (modp), для которого числа х= 1, 2, . .. , р— 1 являются несравнимыми решениями. В общем случае рассуждаем следующим образом: если сравнение / (х) = 0 (mod р) имеет решение xv то делением получим / (х) = (х — х,) fx (х) 4-гп где ^! ^ 0 (mod р). Если х2 хх еще одно решение, то должно быть /г (х2) = 0, так что Д (х) = (х —х2) /2 (х)-]-^, где г2 = 0. Если имеется точно п несравнимых решений, то получаем тождество

(3)

(3)

Так как а0 ^ О, то из / (х0) ~ 0 следует (ввиду простоты модуля), что для некоторого I ^ п х0—х{ = 0, т. е. х0 = х^ следовательно, новых решений больше нет.

Первообразные корни. Как показывает пример 2s = 1 (mod 7), сравнение теоремы 7 может выполняться и для показателей <ср (т). Если d— наименьший целый положительный показатель, для которого ad = 1 (mod mY то говорят, что а по mod/n принадлежит показателю d. Так, 2 по mod 7 принадлежит показателю 3. Очевидно, для (a, т^ = \ ап = 1 (modzn) тогда и только тогда, когда d | п; в частности, d является делителем ср ^mY

d степеней а, а\ ...,ad различны по mod/и, так как из ar = as и d^r^>s следует ar-s при г — s<^d, что противоречит выбору d. Если а принадлежит по mod/?z показателю <р (т), то а называется первообразным корнем по mod/и. Тогда ср (т) степеней а, а\ *.. , a^W представляют собой в точности ср (///) вычетов, взаимно простых с т. Не для всякого модуля существуют первообразные корни, а лишь для zn = 2, 4, ре, 2ре (р— нечетное простое число).

Для наших дальнейших целей будет достаточно установить существование первообразных корней для т = ре.

Пусть сперва т=р, а ф (rf)—количество вычетов, принадлежащих показателю d, делителю р — 1.

Если ф (d) > 0 и / один из таких ф (б/) вычетов, то /, /2, ... , fd — несравнимые решения сравнения xd = 1 (mod р) и по (3) других решений нет. Следовательно, все вычеты, принадлежащие показателю d, должны находиться среди степеней fh (А=1, 2, ... , dY Но fh может принадлежать показателю d дишь тогда, когда ^d, к)=Х. Действительно, если (d, h) = t > 1, d = dxt, h = h^ to ^dt = U^Y* = 1 (mod p) и /^ принадлежит показателю ^dx<^d. Отсюда следует, что ф \d^ ^ ср ^dY Так как каждый вычет принадлежит некоторому определенному показателю d, то р—1=2Ф(^)^2<рм, где сумма распространена на все d\p—1. Как мы увидим позднее в § 14 (17), ^^^ = р— 1, откуда ф(й?) = ср(й?) для всех d. В частности, ф (р—1) = (р(р — 1)>1, что и доказывает существование первообразных корней по mod р.

Пусть р — первообразный корень по mod р. По теореме 5 имеем рр— р=-ур. Покажем теперь, что r = p +р (^— 1) является первообразным корнем по modpe для любого е^1.

Из rp = рр (modp2) следует, что

г <гр"х — 1) = гр— г ~ рр — р — р (-и — 1) = р (mod р^,

так что гр-1— 1 ^ 0 (mod р2) и по теореме 5 имеем представление

rp"x = 1 + ^Р, где Ь^^ (умАр}.

Так как

(1 -^Ьр^ = 1 -Р^У+1 (mod//+2), у^ 1,

то по индукции из частного случая 5 = 0 получим:

(r^”1)^=14-^+1 (modp^2), 5^1.(4)

Показатель d, которому принадлежит г по mod ре, является делителем числа

W^=Pe"' (р-1);

с другой стороны, d должно быть кратным р — 1, так как г также является первообразным корнем по mod р. Таким образом, d имеет вид (р— ^ ps. Сравнение (4) показывает, что 5 — е — 1—наименьшее значение, для которого правая часть = 1 (modpe). Отсюда следует, что d = <^pe^ и г—первообразный корень по modpe.

Пример. 2—первообразный корень по mod 3, r = 2-|- -L3-l=5 — первообразный корень по mod3е. 5, 52 ~ 7, 53~8, 54 ~ 4, 55 = 2, 5е = 1 (mod 9)—вычеты по mod 9.

3 — первообразный корень по mod 4, но для т = 2е (г )> 2) не существует первообразных корней. Зато для каждого нечетного а^>0 имеет место следующее представление с однозначно определяемым с

а — 1

а ее (— 1)“5е (mod 2е), 0 < с < 2е*8.(5)

Для доказательства используем соотношение, справедливое для т^ 3,

52т 3—1 _j_M.2m-1(я — нечетное),

которое легко доказывается с помощью индукции.

Так как показатель d, которому принадлежит 5 по mod 2е, должен быть делителем числа ср (2е) = 2е”х, то /zz = ^ —[^ 1 и б/ = 2е“2. Все 2е-2 значений 5е в (5) таким образом несравнимы по mod 2е. Все они, кроме того, = 1 (mod 4). В полной системе вычетов по mod 2е имеется 2е-2 вычетов я^1 (mod 4) и

столько же вычетов = — 1 (mod 4); остальные вычеты или = О, или = 2, т. е. четные. Числа (5) поэтому совпадают с нечетными вычетами по mod 2е.

Пример. 5 = 4, 5° = 1, 51 = 5, 52 = 9, 5s = 13 (mod 16). Нечетные вычеты 1,3 =— 13, 5, 7 =—9, 9, 11 =— 5, 13, 15 = —1.

1L Квадратичные вычеты. Числа а, взаимно простые с р>2, распадаются на два класса, в зависимости от того, разрешимо или нет сравнение х2 = а (mod р\ Числа первого класса называются квадратичными вычетами по mod р, второго класса — квадратичными невычетами по mod р. Это свойство выражается символом Лежандра:

/^^f 1, если а — квадратичный вычет по modp,

\Р )1—1, если а — квадратичный невычет по modp.

Если р—первообразный корень по modp, то, очевидно, каждое р2А— квадратичный вычет, а каждое р2/?+1—квадратичный невычет. Действительно, сравнение (pf)2 = р2А+1 невозможно, так как отсюда вытекало бы сравнение pJ = 1 с нечетным 5, тогда как s должно быть кратно четному числу р-— 1. Таким образом, существует (р—1)/2 квадратичных вычетов и столько же невычетов по mod р. Легко устанавливается справедливость важной формулы

Пример. Квадратичные вычеты по mod 7 — это 1, 22 = 4, З2 = 2; невычеты — это 3, 5, 6.

По теореме 5 для (а, р) = 1 р-1р-1

ар”х— 1=(д 2 —1) ^а 2 -pl) = 0 (modp).

Так как—1 ^-(-1 (m°dp)> то Для любого а или только первый, или только второй множитель делится на р. Для а = г#2к это будет первый, а для а = р2^4"1 — второй множитель. Отсюда вытекает критерий Эйлера

Следствие:Следствие:р-1 а 2р-1 а 2(modp).(modp).(7)(7)

Следствие:

Следствие:

р-1 а 2

р-1 а 2

(modp).

(modp).

(7)

(7)

~ 1\ (4~ 1 Для р=1 (mod 4),. Р / 1—1 для р = 3 (mod 4).

Гаусс указал простую лемму, служащую для определения квадратичного характера числа а. Положим р = <2к-\-\. р чисел —£, —(&—1), ... , — 1,0, 1, 2, ... , к— это наименьшие по абсолютной величине вычеты по mod р. Каждому п соответствует один такой минимальный вычет по modp. Он будет отрицательным, если наименьший неотрицательный вычет больше чем ^. Пусть г15 г2, ... , г^, —г', —г^ • • • >—г\ — минимальные вычеты к чисел ча (у=1, 2, ... , к^ причем рс4Л = А, 0<rz<£,0<r^<£. Из ri = r. вытекает avt =—а^2 или у1Ц-у2 — 0 (modp), что невозможно, так так ^х^^, У2< у. Таким образом, все к чисел rt-^-r. различны и их совокупность—это числа 1, 2, . .. , к. Перемножением получим: акк\ = (—1)х&! (modp), так что вследствие (7) (j)=(-1)x-(9)

Пример. р= 19, я = 5, к = 9. Минимальные по абсолютной величине вычеты для чисел 5, 10, 15, ... , 45 — это 5, —9, —4, 1, 6, —8, —3, 2, 7, так что к = 4, (й)=(-1)4=1,102 =5 (mod19)-

Лемма Гаусса дает возможность определить квадратичный характер для а = 2. В этом случае |Л — число положительных четных чисел <р/2, т. е. ц = [р/4]. Для X получаются следующие выражения: если р = 1 (mod 4), то

. _Р- 1р- 1 _р- 1 _ Гр + П

24 - 4 — L 4 J >

а если р ее 3 (mod 4), то

р-i р-з_р + 1_ Гр + Л244 — [ 4 J *

Отсюда вытекает:

/ ^\ _ ( 4“ 1, если р ее + 1 (m°d 8), \Р )( — 1, если р Е + 3 (mod8).' '

Из (6) и (8) получается далее

(ЕЕ?^ — / + ^ ссли Р = 1 или 3 (mod 8), п \ Р )( — 1, если р~ \ или —3 (mod 8).' '

вычетах носитвычетах носитВажнейшее утверждение о квадратичных название закона взаимности. Этот закон дает

вычетах носит

вычетах носит

Теорема 6.

р\ М = q) xpJр\ М = q) xpJр-1q-X (-1) 2 2р-1q-X (-1) 2 2^p, q— нечетные простые числа).^p, q— нечетные простые числа).

р\ М = q) xpJ

р\ М = q) xpJ

р-1q-X (-1) 2 2

р-1q-X (-1) 2 2

^p, q— нечетные простые числа).

^p, q— нечетные простые числа).

Доказательство. Пусть снова p=2h -|~ 1 > q=M + 1.

(

а \ используем лемму Гаусса и положим

?v=[j-]p + ?,(v=l, 2, ... , А).(12)

Обозначим через rv rv , г те вычеты pv, которые <ZpI%> а через р — r'v р — г^ ... , р — г^—^, которые ^р^. Просуммировав все равенства (12), получаем:

Так как требуется лишь выяснить четность или нечетность X, то рассмотрим это равенство по mod 2. При выводе леммы Гаусса было установлено, что

к21

V = 1

так что вследствие р = q = 1 (mod 2) получаем: isi=£ [fl (™d-2)-

Таким же образом получаем для показателя степени, соот

ветствующего в формуле (9) символу

^=\=S [у] (mod2)-т=1 L Ч J

Осталось показать еще, что X-\-Xx-==hl (mod 2). Здесь имеет место даже равенство. Построим hl величин qv — рт, ни одна из которых не равна нулю. Среди них будет ровно

1 положительных. Действительно, при фиксированном v(v = = 1, 2, . , . , k) будет q^ — рт > О для т = 1, 2, , , . , ^] , т. е. для ^у] значений т, так что после суммирования по v получим точно X положительных значений. Так же при фиксированном т будет q^— /)т<^0 для v=l, 2, ,, ^] , так что имеется At отрицательных величин. Теорема 6 доказана.

Закон взаимности показывает, что квадратичный характер р по mod q совпадает с квадратичным характером q по mod р, кроме случая, когда оба числа — wp^q — имеют вид 4л4”3. В этом случае характеры противоположны.

С помощью теоремы 6 символ Лежандра легко вычисляется.

„/ЮХ/ 2 X / 5 X/13Х/ 3 X

Пример.^13J(13Д13)(5)^sj

= —(у)=—(-l^+h Проба: 62=10 (mod 13).

Имея в виду использование этого в дальнейшем, выясним для каких простых модулей р числа +3 являются квадратичным вычетом или невычетом.

По теореме 6 и (7) имеем:

f) (-1)2 =(-Ч2 Р (mod 3).

/ з \

Для выполнения равенства J = 1 нужно пли чтобы (р — — 1)/2 было четным и р = 1 (mod 3), или чтобы (р— 1)/2 было нечетным и р = — 1 (mod 3). В первом случае р=12^-|- 1, а во втором р=12/г—1. Равенство j =—1 получается или при нечетном (р—1)/2 и p=l(mod3), или при четном (р— — 1)/2 и р~ — 1 (mod 3). В первом случае р = 12&— 5, а во втором р=12&-|-5. Резюмируя, имеем:

f j_\/ 4" Ь если Р ^ zb 1 (mod 12),. 1

\Р )I — 1, если р = + 5 (mod 12).' '

Из (7), (8) и теоремы 6 получаем далее

и отсюда

Г — 3\ ( -f- 1, если р ~ 1 (mod 6),

\ Р /( — 1, если р = — 1 (mod 6) *).

Аналогично

так что

(15)(15)— 1, если р = 3, = 5, = 6 (mod 7), -j- 1, если р ~ 1, = 2, =4 (mod 7).

(15)

(15)

Теорема Акселя Туэ. В § 21 мы будем пользоваться следующей леммой Туэ. Пусть п^> \ и 5— наименьшее целое число >"Кл, тогда для каждого натурального числа а, взаимно простого с п, существуют два таких натуральных числа х ^ е — 1, у ^е — 1, что ay = + х (mod nY Для доказательства используется принцип Дирихле, который утверждает, что при распределении N объектов между N— 1 ящиками хотя бы в одном ящике должно находиться 2 объекта. Рассмотрим все е2 чисел вида ау ~|~ х, где х, у = 0, 1, 2, . .., е — 1. Так как е2 > п, то хотя бы два таких числа должны иметь равные вычеты по mod п, так что существует сравнение аухД-хх~ = ау2-|-^2 (mod nY Отсюда следует, что а^ух—у^ = х2— — хх (mod nY Вследствие неравенств j^—_у2|^5—^» |х2 — хх\^е—1 из равенства хх=х2 вытекает, что и ух = =У2 и наоборот, так как в противном случае разность не будет делиться на п. Таким образом, хх ^= х2, ух^=у2, ау = =у1—у2 и Azx = xx—х2 при подходящем выборе знака окажутся требуемыми числами.

Пример, п = 23, 5 = 5, а = 9, За = 4 (mod 23) или ах = 10, <2ах~ — 3 (mod 23).

II. ТЕОРЕТИКОЧИСЛОВЫЕ ФУНКЦИИ

Определение. Под теоретикочисловой функцией мы понимаем функцию, определенную для любого натурального числа п. Значения функции могут быть вещественными или комплексными, /(/г) называется мультипликативной, если из

') Для нечетного р из сравнения р = ± 1 (mod 3) следует р в zt 1 (mod 6).

(zzz, zz) = l следует, что f ^mn^=f^tnyf ^п\ Если это свойство справедливо для всех т, п, то функция называется вполне мультипликативной.

Сумма У f^ — F ^nY распространенная по всем делите- d\nо

лям d числа п (включая 1 и nY называется сумматорной функцией для f^nY Если /(zz) мультипликативна, то мультипликативной будет и F^nY

Для (zzz, п) = 1 и d | тп имеет место представление d = = dxd^ где dx\m и d2\n, (dx, d2) — l. Отсюда

fm= 2 / W= 2 fW=d\mndx\m

d2\n

=W ^/(dt) = F^F(n). di\m d2\n

ср-функция Эйлера. Символом ср (zz) для zz ^ 1 обозначают количество чисел ^zz, взаимно простых с zz.

Пример. ср(1)=1, ср(7) = 6, ср(10) = 4.

Покажем в первую очередь, что ср (zz) мультипликативна. Пусть (т, zz)=l. Если в выражении mq-\-r г пробегает числа 0, 1,2, ... , т — 1 , a q — числа 0, 1, 2, ... , zz — 1, то мы получим все неотрицательные целые числа < тп без повторений. Число mq-^-r взаимно просто с т тогда и только тогда, когда (г, т) = 1. Существует ср (zzz) таких г. Если гх одно из них, то различные по mod п числа гХ1 т-^гх, 2т-{-гх, . . . ..., (zz — 1) т -{- гх образуют полную систему вычетов по mod zz. Среди этих чисел точно ср (zz) взаимно простых с zz, т. с. взаимно простых с тп. Всего получаем ср (zzz) ср (zz) чисел, взаимно простых с тп.

Для вычисления ср (zz) теперь достаточно уметь вычислять эту функцию для степени простого числа ре. Так как только числа kp (1 ^ к ^Рв^х) не взаимно просты с ре, то (р(ре) = — ре— ре~х. Отсюда

'?(«)=!!?(рр)=«Пf1«=Прр • о6)

iр\п X Р /i

Для сумматорной функции имеем:

2 (р(</) = п p4-(p(^.)4-(p(p2)_|_..>_j_(p(Pei) । _

d\ni

— Д Р? = п’ 07)

Так как при перемножении скобок получим точно все значения ср (/Г).

Функция Мебиуса р.(п), которая в дальнейшем окажется особенно важной, определена следующими равенствами:

И(1) = 1, wW= /И(1) = 1, wW= /О для п, делящихся на квадрат, ( — 1)* для п—р^ рг...рк iPi^Pj}.

И(1) = 1, wW= /

И(1) = 1, wW= /

Примеры. pi(12) = 0, ц(15) = 1, g(30) =— 1, ц(п), очевидно, мультипликативна. Для сумматорной функции имеем:

2м*)=/Ор1I2м*)=/Ор1I1 для п = 1,1 для п = 1,О для п > 1.О для п > 1.(18)(18)

2м*)=/

Ор1I

2м*)=/

Ор1I

1 для п = 1,

1 для п = 1,

О для п > 1.

О для п > 1.

(18)

(18)

Доказательство. Для п = рр Р22 • • • Ре£ (^^ ^)

Важнейшим применением функции pi (п) является формула обращения Мебиуса, с помощью которой /(м) следующим образом выражается через сумматорную функцию:

/(«)=Sixw^(4), FW=Lm 09) а]л''d\n

Доказательство. Изменением порядка суммирования В двойной сумме получим:

Lm^ (|)=Ен(^Е/(с)=Еи^)/(с)= d\n'' d\n_ncd\n

d

Вследствие (18) внутренняя сумма последнего выражения не равна нулю лишь для с = п (в этом случае она равна 1), так что двойная сумма сводится к члену Дп\ чт0 и требовалось доказать.

В качестве примера можно снова получить (16) из (17) и (19)

Для доказательства теоремы 4 мы используем в § 55 более общую формулу обращения1). Пусть Р^— вполне мультипликативная теоретикочисловая функция, для которой Р(1) = 1, a fW — функция, определенная для всех вещественных х > О, принимающая вещественные или комплексные значения. Тогда

из g"(x)= У2 PWf (^) следует /(х) =п х47

= 2 v-WPW g(^Y= 2 v-WPW g(^Y(20)(20)

= 2 v-WPW g(^Y

= 2 v-WPW g(^Y

(20)

(20)

Доказательство. Из уравнения, определяющего g^x^ следует

Xh(«)^(«)^(^-) = Хи(«)^(«) X pwH^Y=

п^х7 п^хх7

7Й^ П

= х и w р w•

тп ^хх 7

Положим с = тп, тогда из (18)

X wWPW g^\ = 52 pW (y) 52 М^=АхУ

п^ х' 7 с^х4 7 п с

Функция Мангольдта обозначается символом А (л). Она имеет значение log р, если п — простое число р или степень простого числа р, а в остальных случаях ее значение — нуль:

A(/z) = logjo, если п = рт; К^ = ^, если п^рт.

Нам будут нужны следующие свойства А (п):

у А ^ = log л,А(я) = 52?л(6?) 1о£4р d\n(21)(22)у А ^ = log л,А(я) = 52?л(6?) 1о£4р d\n(21)(22)2А(</)= 2 iog^^S eP^°gp=\°gп. d\nра\п2А(</)= 2 iog^^S eP^°gp=\°gп. d\nра\пОчевидно, имеем:Очевидно, имеем:

у А ^ = log л,

А(я) = 52?л(6?) 1о£4р d\n

(21)

(22)

у А ^ = log л,

А(я) = 52?л(6?) 1о£4р d\n

(21)

(22)

2А(</)= 2 iog^^S eP^°gp=\°gп. d\nра\п

2А(</)= 2 iog^^S eP^°gp=\°gп. d\nра\п

Очевидно, имеем:

Очевидно, имеем:

т) См. Shapiro [25], S. 232,

где ра пробегает все степени простых, входящие в п, а р входит в п с показателем е . (22) следует из (21) с помощью формулы обращения Мебиуса (19).

Характеры. Пусть к— натуральное число. Теоретикочисловая функция ^ (а) называется характером по mod к, если она обладает следующими четырьмя свойствами:

А. у(я) = 0, если {а, к)^=\\ В. у (1)^=0;

С. 1ДаЬ^ = ^^ЬУ. D. x(«) = ZW.

если a = b (mod к).

Характер, определенный равенством yt {а) = 1 для всех а, взаимно простых с к, называется главным характером по mod к. Очевидно, что при любых возможных определениях у (а) всегда у(1)=1, так как по свойству С у(1) у(1) = у(1), а по свойству В обе части можно разделить на X (1). Из свойств С и D и теоремы 5 для {а, к) = 1 получаем { у (zz)}t?^> = = у {a^W) — 1, следовательно, у {а) является корнем из 1 степени <р (к) и может принимать таким образом комплексные значения.

Примеры характеров Ц = У—1):

6 = 3: х(0) = 0, X (1)=1, Z(2) = -h

6 = 4: Х(0) = 0, X (П^, Х(2) = 0, X (3) = — 1;

6 = 5: у(0) = 0, х ОМ, Z(2)=^ Z(3) = —Л Z(4)=-L

Покажем теперь, что для любого d > 0, {d, к) = 1 и d ^ 1 (mod к) существует такой характер у по m°d 6, Для которого у (d) ^ 1.

Пусть каноническое разложение к имеет вид &=JJ// р^>2. По § 10 существует первообразный корень г по mod ре, так что при (а, к) = 1 будет а = ? (mod ре), 0 ^ / < <р {ре) = s, где t однозначно определяется числом а. Теперь характер у {а) можно определить с помощью первообразногот) корня степейии 5 из единицы

V 2п , . . 2лр = е s = cosн z sin— ,

если положить у (я) — р\ для {а, к)=Л и у(а) = 0 в противном случае. Условия В, С, D теперь выполняются:

*) р^ = 1, но рл ^ 1 для 0 < п < 5.

В: у(1) = р°=1; С: если (а\^) = 1, аг = ? (mod реу то аа’нг^ (mod ре^ и ^ДаУ1Да'^ = ^г =^^^: из

a = a'(mod к) следует а = а\тоД реу так что/ = ^ и у(я) = = ХИ

Если d ^ 1 (mod к\ то для характера, определенного таким образом, очевидно, будет у (rf) ^А 1, так как р — первообразный корень из единицы.

Теперь осталось установить существование таких характеров для k = Y, где е>2, так как для 2 и 4 первообразные корни существуют. Каждому а^^п-^Х вследствие (5) соответствует некоторое с и характер в этом случае мы можем определить равенствами у(2л) = О, ^ (2лг —[— 1) = р^, где р = _^2^/s^ s_ 2е”2. А, В и D выполняются тривиальным образом.

Для доказательства С заметим, что из ^а—1)(^—1) = 0 (mod 4) для нечетных а, а*, следует

— + —2“ =—2 (m0d 2)(23)

и отсюда

аа =^—1) 25е+е/ (mod 2е) или ^ (а) у (o’) = ^^аа’У

Для определенного таким образом характера у (а) = 1 лишь а—1*

для 1 = 0, а в этом случае аа\—1) 2 (mod 2е). Итак, если d г 1 (mod 4) и ^ 1 (mod 2е), то наверняка у {d}^ 1. Для d = — 1 (mod 4) определяем характер равенствами у0 ^п -f- 1 )= = (—1)”, уо(2и) = О, так что Хо(^)=^- То, что у0 (а?) является характером, непосредственно следует из (23).

Таким образом, для любого числа d ^ 1 (mod к^ можно выбрать такой характер (определенный для всех /г), чтобы было Z № 7 1 ■

Так как характер у по mod к полностью определяется ср (£) значениями у (и) [1 ^ п ^ к, ^п, к) = 1], каждое из которых является одним из ср ^к) корней степени ср (/г) из единицы, то различных характеров по mod к не более чем ср ^ку^ ^\ [Число распределений ср (£) элементов по ср (/г) классам.] Таким образом, количество Z характеров по mod к конечно.

Теперь мы в состоянии установить для характеров некоторые важные соотношения, которые будут использованы позднее при доказательстве теоремы 4:

Пусть а пробегает полную систему вычетов по mod А?, тогда

у х(й)= J ^W^ X=Z1,(24)

а К I 0 для XT^Xi'

Доказательство. Достаточно доказать вторую часть. Для XT^Zi существует такое натуральное взаимно простое с к число Ь, для которого х W ^ 1 • Вместе с а полную систему вычетов по mod к пробегает и ab, так что 2 X W = 2 X w= = XWSx(°)- Так как х^т^Ь то 2х(а) Должна обращаться в нуль.

Пусть а — фиксированное натуральное число, а уу пробегает все Z характеров по mod к, тогда

2 ху(а)=(2 ху(а)=(Z, если я=1 (mod к\mgx

2 ху(а)=(

2 ху(а)=(

0у если а ^ 1 (mod ку

Доказательство. В первом случае уу (я) = 1 Для всех j. Для ^а, к^^\ вторая часть (25) справедлива, так как в этом случае уу(я) = О. Таким образом, осталось теперь предположить (а, А) = 1, а ^ 1 (mod ку В этом случае, как показано выше, существует характер у^, для которого у^ (я) ^ 1. Произведение у5 (а) Уу (а) вместе с уу. (а) пробегает все Z характеров, так как из равенства 1^а)^уа^ = \Дд^^ следует уу(я) = = Х/(а)> поскольку у5(а)^=0. Отсюда вытекает равенство ^Х/(а) = ^Х/(аШа) = ХЛа) ^1)^ и так как XsW#1. то сумма 2Х/(Д) Должна обращаться в нуль. Просуммировав по всем а и у и изменив порядок суммирования, получаем:

^=2 2 z W=2 2 z w=v W •(26)

« XX «

Пусть (/, &)=1 и у (/) = 1/у (/)— число, комплексно сопряженное с у (/), которое, очевидно, также является характером. Тогда

Vv Ы? и\Д^ если a = Hmod^). ,27) 4<Х/(°)Х/(0—о, если а -^ t (mod ку

Доказательство. В соответствии с § 9 мы можем выбрать такое натуральное s, чтобы было st = 1 (mod&). Тогда

Х(»)Х(О = Х(»О = 1, или x(s) = X(O-

Теперь

3 X/ («) X/ (0=S X/ w Xi (»)=2 X/ Н, //j

где последняя сумма вследствие (25) и (26) для as ~ 1 (mod^) принимает значение ^^к^ а в противном случае обращается в нуль. Доказательство завершается умножением сравнения as ее 1 (mod к) на t.

ОБЩИЕ КРИТЕРИИ ПРОСТЫХ ЧИСЕЛ

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

£#]~МН<28>

т L J L J J

которое справедливо тогда и только тогда, когда п является простым числом. Так как слагаемые равны 1, если т делитель п, и равны нулю, если это нс так, то сумма (конечная) представляет собой число d (п) делителей п, а равенство ^(и) = 2 характеризует простые числа. Естественно, (28), как и многие другие критерии, нс пригодно для практических целей.

Теорема Вильсона. Следующая теорема, впервые доказанная в 1770 г. Барингом и приписанная им Д. Вильсону (1741 —1793), представляют собой, пожалуй, наиболее известный критерий простоты числа.

Теорема 7. Натуральное число п > 1 тогда и только тогда является простым, когда (п—1)1—|—1 =0 (modи).

Доказательство. По теореме 5 хр-х — 1=0 (modр^ имеет р—1 решений 1, ..., р—1, так что вследствие (3)

хР-'^х — 1)(х — 2). .Дх — p4-l)+pF(x).

Положим х = 0, тогда (^р—1)! =— 1 (mod/?). Если же п составное, то оно содержит простой множитель q<^n. q является делителем (и—1)!, так что ^п—1)!-|-1 не делится на q, а значит, и на п.

В качестве следствия Клементом [4] доказана красивая Теорема 8. Числа п и п-^^ тогда и только тогда являются простыми близнецами, когда 4 [(и— 1)! 4™ 1]-4^=^ [mod /г (zz —|— 2)], п > 1.

Доказательство. Если это условие выполнено, то так как «4=2 или 4, должно быть (п—1)! 4~ 1 = 0 (mod п^ следовательно по теореме 7 п— нечетное простое число. Так как п = — 2 (mod /г 4“ 2)’ то (л4-1Н = 2(л—1)! (mod/г 4~ 2). Отсюда следует

0 = 4[(Л-1)! + 1] + л=2(Л+1)! +

4- 2 = 2 [(и 4-1)! + 1] (mod п + 2), (29) так что по теореме 7 простым числом является и п 4-2. Предположим, наоборот, что п и л 4" 2— простые числа, тогда 4[(«—1)! -)- 1]4"п делится по теореме 7 на л, а вследствие (29) на п 4- 2, так что делится и на /г (и 4" 2).

Обращение теоремы Ферма. Непосредственное обращение теоремы 5 ошибочно, так как сравнение ап~х = 1 (modи) может иметь место и для составных п.

П р и м е р. 341 = 11 • 31,210 = 1024 = 1 (mod 341), (210)34= = 2840 = 1 (mod 341). Лемер и Поулет составили таблицы, содержащие все составные /го^1О8, для которых 2”о~1 = 1 (mod«o). Существует бесчисленное множество таких показателей /г0, так как для /г1 = 2”о—1, вследствие

пх — 1 = 2 ^о"1 — 1) = ^qn^ имеем:

2”!-1 —1=22^о—1 =

= (2”о— 1) (2<2^-1) ”о4- ... 4-1)^0 (mod/zj.

Если пй = ич)— составное, то

пх = 2“у — 1 = (2я — 1) (2(г,"1)ы4- ... 4- 1)

также составное. В качестве следующего составного решения сравнения 2”1=1 (mod л) можно взять « = 2”1—1 и т. д. (Steuerwald [28]).

Существуют даже составные числа тп (числа Кармайкла), для которых am~x = 1 (mod т) для каждого а. взаимно простого с пи Необходимым и достаточным для этого является выполнение условия т— 1^0 (mod pz— 1) для всех Pi I m *)•

Пример, т = 561 = 3 • 11 • 17.

Один из критериев простого числа дает

Теорема 9. Если существует такое число а, взаимно п — 1

простое с п, что ап-х ~ 1 (mod/z), но а р ^ 1 (mod л) для любого простого делителя р числа п—1, то п— простое число.

Доказательство. Так как каждый нетривиальный делитель t числа п — 1 входит в один из «наибольших» делителей ^п—Х^р, то из предположения теоремы следует, что также а1 ^ 1 (mod/z), так как в противном случае существо- п — 1

вало бы р, для которого было бы а Р ее 1 (mod/z). Если а принадлежит показателю d (§ 10), то ad = 1 (mod /z) и d должно быть делителем п — 1, что возможно лишь для d = n — 1. Таким образом, п—1 является делителем ф (/z). Вследствие (16) для составных п всегда cp(/zX/z—1, так что п должно быть простым числом. Если, наоборот, п—р, то первообразный корень по mod/? осуществляет условия теоремы 9.

Такая проверка простоты числа осуществима, если известны различные простые множители числа п — 1 и если их не очень много. В качестве основания выберем небольшое число, например 2 или 3, а степени ах заменим их вычетами по mod п.

Пример. zz= 101, п— 1 = 100 = 22-52. Для mod 101 имеем 28=8,26=64, 212=56, 225 = 2-224=2.5= 10, 250=—1, 2100=1. Так как 250 ^ 1 и 220 = (210)2 = 142 = 95 ^ 1, то 101—простое число. Само собой разумеется, что п не простое число, если ап-х ^ 1 (mod/z).

Для практического исследования большого числа п, не имеющего специального вида, полезна следующая теорема Д. X. Лемера1).

п — 1

Теорема 10. Если ап-х = 1 (mod/z), а р еег^ 1 (mod/z), где р — простой делитель п — 1, и (г — 1, /z) = 8, то все делители п, взаимно простые с 8, имеют вид рах -j- 1, где п—1 делится точно на ра(а^1).

Доказательство. Положим п—\=qp = mp. Если t — простой делитель /z, не входящий в 8, и а по mod t принадлежит показателю т, то из ап-х = 1 (mod/) следует, что п—1 =0(modT). Но т не может делить т, так как в противном случае было бы ат = г = 1 (mod /) и, следовательно, / было бы делителем г—1 и /z, т. е. вопреки предположению

t должно было бы входить в 8.Положим т = пх р^, (пи р) = 1, р ^ 0. Так как (/г—1 )/т = ^qp^KniP^ — целое число и (р, <?)=!, то а ^ р и q\nx целое. С другой стороны, tti^ = (qpa”^jknxp^ — не целое, так что р>а—1. Отсюда а = р, так что т = zz^. Так как по теореме 5 t?"1 ~ 1 (mod/), то /—1 делится на т, и / имеет вид х//*-)-!. Так как произведение множителей такого вида имеет такую же форму, то теорема доказана.

Пример. и = 341, п — 1 = 340 = 22-5-17, р = 5, (п—1)/р = 68. Из сравнения 210 = 1024 ~ 1 (mod341) следует 2540 = (210)54 = 1 (mod 341), 268 = 28 = 256 (mod 341). Так как (255, 341) —1, то 8=1 и все делители 341 имеют вид 5х-|- 1. Действительно, 341 = 11 - 31 ==(5 • 2 —|— 1) (5 • 6—{—1).

Вычеты степени az по mod п для больших г можно сравнительно просто вычислить с помощью вычислительной машины.

Если предположения теоремы 10 выполнены и 8=1, a N составное, то оно должно иметь простой делитель х//-|-1 с x<Z^^2P~^- Если р^^ЬГ^ то х = 0 и N — простое. Если р° не намного меньше №2, то нужно будет испытать лишь немногие значения х, число которых можно еще больше ограничить, исходя из специфических свойств N. Так, для нечетных р можно рассматривать лишь четные х и вообще пропускать хр* -^- 1, кратные небольшим простым числам, не входящим в N. Если, кроме р, известен еще один простой делитель q числа N— 1, для которого выполнены условия теоремы 10 при 8=1, то делители N имеют также вид yq^ -|- 1, где теперь должно быть _у = г/Л Если p^q^^ N\ то N—простое. Эту операцию можно продолжать.

Лемер приводит наряду с другими следующий пример:

/V=22E1 = ю16 — 108 4- 1 = 9 999 999 900 000 001,

N — 1 = 108^=^=:28.58.Зг. 11-73-ЮЬ 137.

Имеем:

7 10 ее 7 128 121 476 353 673 = /- (mod/V), N—l

г2 ее 7 5 ее 428 233 546 143 224 (mod/V), г5 ее — 1 (mod N^ г10 ее 1 (mod N).

Так как (г2 — 1, N) = 1, что можно установить последовательным делением, то каждый делитель N имеет вид х*58-[- 1.

Так как (г5—• 1, N)=l, то каждый делитель N имеет также вид jz• 28 —|— 1, следовательно, и вид ^г-Ю8—|— 1. Так как 108^>№^, то N—простое число.

Интересное применение теорема 10 нашла в 1951 году. Если р— простое число >2 и k<^p[2— натуральное число, то ^=2^p—[— 1 будет простым числом, если а2кр = 1 (modN) и а2к ^ 12б (mod TV). Если 8 = (г —-1, N\ где а2к = г (mod N^ то все делители N, взаимно простые с 5, имеют вид хр -4- 1, так как N—1 не делится на р2. Так как {хр -f- 1) {ур 1) = ^{^РА” X-V^ Р + Ь то произведение двух отличных от 1 множителей такого вида уже больше N.

Таким образом, существует разложение ДГ=2^-|-1 = — {xp-^-l^d, где d во всяком случае множитель, не взаимно простой с 5. Отсюда, однако, следует, что d ее 1 (modp), т. е. d имеет форму j^-|-l. Таким образом, d=\ и TV является простым числом. По теореме 4 таких простых TV существует бесконечно много.

Если взять в качестве р наибольшее известное простое число, которым в начале 1951 года еще было 2127—1, то можно таким способом открыть новые, еще большие простые числа. С помощью электронных вычислительных машин SEA С (Вашингтон) и EDSAC (Кембридж, Англия) Д. К. П. Миллер и Д. Д. Уилер нашли, что 2^(2127— 1)-|-1—простое число для 2^=114, 124, 388, 408, 498, 696, 738, 774,780,934, 978. Аналогичным образом они нашли наибольшее простое число 1951 года, число 180 (2127—I)2—|— 1, состоящее из 79 цифр.

Представление простых чисел квадратичными формами (Numeri idonei). Вследствие тождества 2лг —|— 1 = — {n-\-W— я2 каждое нечетное число представимо в виде разности двух квадратов. Для любого нечетного простого числа такое представление, очевидно, однозначно, так как из

р = 2п -)- 1 = х2 —у2 = {х —у) {х + у) следует

х —у 1, х -1“ у = 2 л —|— 1, т. с.

х = л —|—1, у = п.

Покажем теперь, что и общая форма ax2-|-^v2, где a, b— натуральные числа, представляет простое число самое большее одним способом,

Из р = ах2 4- by2 = аи2 4" ^2, где х' N^11^ — натуральные числа, (х, у^ = \ц, т/)=1, следует после исключения в

р С^2 —^2) = а ^^ —^2^2)

и так как а<^р, то уи не + xv (mod р).(30)

Перемножив оба представления, получим:

р2 = ^ахи + byvy 4- ab (иу + vx^,(31)

где можно взять или верхние, или нижние знаки. Если uy = vx, то вследствие (и, v) = (х, у) = 1 будет и | х и х\и, т. е. и = х и v=y. Если иу^их, то из (30) и (31) |^+^|=Р? а = Ь=\1 axu4-byv = 0,

так как иначе (31) не выполняется. Таким образом, хи = Ц-уу и х = + v, у = + и и представление р = х2 4~ у2 ^а = Ь=\^ однозначно.

Если бы мы показали, что составные числа, имеющие собственное (т. е. с взаимно простыми х и у^ представление ах2-\-Ьу\ допускают более одного представления, то мы получили бы критерий простых чисел, так как в этом случае простые числа характеризовались бы однозначным представлением. Представление 2х2 4- 3j/2 = 14, имеющее единственное решение х=У _у = 2, показывает, что это не выполняется для всех а, Ь.

Эйлер заметил, что х2 4~ dy2 (d ^ 1) для специальных значений d однозначно и собственным образом представляет лишь простые числа. Коэффициенты d он назвал «подходящими» числами (Numeri idonei) и указал следующие 65 их значений: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 18, 21, 22, 24, 25, 28, 30, 33, 37, 40, 42, 45, 48, 57, 58, 60, 70, 72, 78, 85, 88, 93, 102, 105, 112, 120, 130, 133, 165, 168, 177, 190, 210, 232, 240, 253, 273,280,312, 330,345, 357, 385, 408, 462, 520, 760, 840, 1320, 1365, 1848. Вывод критерия, с помощью которого Эйлер получил Numeri idonei, не является вполне обоснованным, однако Гаусс с помощью своей более тонкой теории квадратичных форм нашел эти же самые 65 чисел, тем самым их существование обосновано.

Хотя Эйлер продолжал свои вычисления за пределы 10 000, он не нашел больше Numeri idonei, что показалось ему пара-

доксальным. Только из новых глубоко лежащих результатов следует конечность количества подходящих чисел, однако не известно, является ли 1848 наибольшим из них.

Докажем, что d=\x 2, 3, 7— «подходящие» числа. Необходимым условием для'представимости р в форме х-|-^2, (d, р) = 1 является разрешимость сравнения х2 -|- dy2 = О (modp), (х, j/) = 1, которое можно также записать в форме г2 = (яу-1)2 = —d (modр^(32)

так как сравнение yz = х (mod р) вследствие (j/,p) = l имеет единственное решение z. Таким образом,— d должно быть квадратичным вычетом по modp.

Пусть это условие выполнено, тогда (32) разрешимо с z, взаимно простым с р. Пусть также х, ^Ур, ух <С Vp удовлетворяют сравнению zyx = + хх (modp) (такие числа существуют по теореме Туэ, § 12). Тогда

^! (г2 + d) = х? + dy\ = тр,(33)

где m^d, так как Xi<.p, У1<_р. Покажем, что для d=1, 2, 3, 7 следует положить т=1. Тогда для этих d все простые делители числа N, имеющего собственные представления в форме x*-\-dy\ сами будут представимы в такой форме !). Из тождества

(^ + dy?) (х22 + dy^ = кхххг + dy,y^ + d (x,yt ±лхг)8 (34) вытекает, что вообще все делители N будут представимы в такой форме. Далее, из (34) вытекает, что произведение двух простых чисел, взаимно простых с d, представимо по крайней мере двумя различными способами. Эти два представления осуществляются вследствие ххухх^у2^^ выбором знаков2). Повторное применение (34) показывает, что любое составное N представимо более чем одним способом, так что простые числа характеризуются однозначным собственным представлением.

d=V Сравнение (32) разрешимо лишь для (—-) = 1, так что вследствие (8) должно быть р — 1 (mod 4). Из (33) немедленно следует, что^=1, чем и доказано существование представления. Таким образом, справедлива

’) Действительно, если разрешимо сравнение хг + ^у2 = 0 (mod А/), то это сравнение разрешимо и по mod/?, где p\N. (Прим, перев.)

Теорема 11. Нечетное число вида 4т 4-1 тогда и только тогда является простым, когда оно лить единственным образом представимо в виде суммы двух взаимно простых квадратов.

/2\

d = 2. Из (32) следует j = l, так что вследствие (11) р=1 или 3(mod8). В (33) теперь т=\ или 2, так что или х2 4~2у2 = р, или х2 Ц-2у2 = 2р. Положим во втором случае х = 2хп тогда 2х2 4~у2 = Р, т. е. снова имеем представление требуемого вида. Этим доказана

Теорема 12. Нечетное число вида 8/^4”! или 8m—|—3 тогда и только тогда является простым, когда оно лить единственным образом ^собственной представимо в виде х2-\-^У2.

— 1 = 1, так что вследствие (14) p=l(mod6). Теперь следует рассмотреть в (33) случаи т—\, 2, 3. Равенство х2 4™З^у2 = 2р невозможно, так как X и у должны быть нечетными, поскольку р^^^ а тогда х2 -р ^У2 = 0 (mod 4), что невозможно.

Если Зр = х2 ~4^2, то, снова положив х=3хп получим: р = Зх2 -р.У2- Отсюда следует

Теорема 13. Нечетное число вида 6zn4“l тогда и только тогда является простым, когда оно имеет лить единственное собственное представление в виде х2-\-^у2.

/

d = 7. Здесь должно бытьПо (15)р = 1 или

9, или 11 (mod 14). В равенстве (33) следует исследовать случаи т = \, 2, 3, 4, 5, 6, 7.

Если т = 2 или 6, то х и у оба должны быть нечетными, так что х2 4~ 7у20 (mod 8), что невозможно. Для т = 4

имеем или x = 2xn у = 2ух, откуда получаем х2 4- 7у\ =Р, или х и у оба нечетные, что приводит к тому же противоречию, что и выше. В случае х2 4- 7у2 = Зр будет Ку, 3) = 1, так как р т^З. Отсюда — 7 = (.ry”42 (mod 3), тогда как по (8) /7\/1 \.

должно быть — = — =—1. Итак, случай т = ^ невозможен и также отпадает случай т = 5, так как вследствие (И) (-у ) = ( -у ) = — 1 • В случае х2 4~ 7у2 = 7р положим снова х = 7хх и получим у2 4~7х2—р, чем и доказано существование представления. Таким образом, получается

Теорема 14. Нечетное число вида \^т-\-\Д^т-\-9 или 1 ^т -|- 11 тогда и только тогда является простым, когда оно лишь единственным образом собственно представимо в виде х2^!^^.

Естественно возникает вопрос, как установить единственность разложения для большого числа. Во всяком случае нужно будет использовать как можно большее подходящее число d. Принцип исследования иллюстрируется следующим примером.

N— 18 518 809 = 1972 + 1848.1 ОО2 = х2 + 1848/.

Имеем у ^ (18 518 808/1848)1/2^ 100. Рассмотрим прежде всего представление по mod 5. Сравнение N= х2 -|- 3_у2 ^ (mod 5) допускает решение при квадратичных вычетах х2 = 1, 4, 0 по mod 5 лишь при у = 0 или у е + 1. Таким образом, числа у = 5Z? + 2 отпадают, но остается еще 60 возможных значений для у. По mod 13 имеем N^ х2 -j- 2у2 ее 10. Квадратичными вычетами являются числа 1,4, 9, 3, 12, 10, 0. Отсюда у2 ^ 1, 4, 9, так что можно зачеркнуть числа 13 k + 1, 13 & + 2, 13^ + 3. Остается еще 24 числа. По mod 17 мы имеем квадратичные вычеты 1, 4, 9, 16, 8, 2, 15, 13, 0.

Сравнение N = х2 — 5_у2 ^ 12 не разрешимо при у2 = 9, 16, 2, 0, так что отпадают числа 17 ^ + /(/ = 3, 4, 6,0), и остается испытать 19 значений у. Это количество можно свести к 12, если рассмотреть представление еще по mod 19. Теперь можно быстро убедиться в том, что N— 1848j/2 является квадратом лишь для_у = 100, следовательно N—простое число.

Разложение на множители. В то время как небольшие составные числа можно раскладывать на множители с помощью таблиц простых чисел или таблиц множителей, разложение на множители больших чисел, выходящих за пределы таблиц, является проблемой, для решения которой не известно общего метода. Так, например, из критериев простоты числа известно, что 2128-|- 1,2256 -|- 1,2257— 1 —составные числа, но ни один из их делителей не известен. Наиболее эффективным является и сейчас метод представления N квадратичной формой, употреблявшийся еще Ферма и Эйлером. Встречающиеся при этом вычисления можно значительно сократить искусным использованием особенностей числа ^1).

9 Подробное изложение можно найти у Менхена [16]. Ср. также Л. Эйлер, Opera omnia 13 и I4.

Метод Ферма относится к представлению N в виде разности двух квадратов. Пусть N—ab, a^b— нечетное составное число, тогда имеем целочисленное представлениеN— х2—_у2, х = ((7-[-^)/2, j/ = (a— b) / 2. В равенстве х2 = ^-|-J/2 будет х2 ^ N, так что x^VN. Если z — наименьшее целое число ^ VN, т0 мы должны в последовательности чисел z2 — N^ (z 1 )2 — /У, (^ “F ^)2 — N, ... Дг-^-ку — N отыскать квадрат. Это произойдет нс позднее, чем при .?4-£ = (W4-1) / 2. Последнее, однако, приводит к тривиальному разложению N* 1.

Для составного N = ab квадрат встретится раньше, так как (а-\-Ь)/2<ЦМ-^- 1)/ 2 для Ь>\. В качестве побочного результата получаем следующий старый !) критерий простого числа: N тогда и только тогда простое число, когда N-^-k2 не является квадратом для к= 1, 2, . . . , (N—3) / 2.

Практическое вычисление (^-j-^)2— N производится последовательным добавлением разностей 2z-|-l, 2^-|-3,2^-|-5,...

Пример (Ферма). N = 2 027 651 281, г = 45030.

г2 — А = 496192z 4- 1= 90061 (2-pi)2 —А = 139 680 2^4-3=90063(24-2)2-^=229 743 2г 4-5=90065(z 4-3)2— А= 319 808 2^4-7=90067(2 4-4)2-/7=409 875 2г 4-9=90069г2 — А = 496192z 4- 1= 90061 (2-pi)2 —А = 139 680 2^4-3=90063(24-2)2-^=229 743 2г 4-5=90065(z 4-3)2— А= 319 808 2^4-7=90067(2 4-4)2-/7=409 875 2г 4-9=90069(2 4-5)2-Л = 499 944 2г + 11 = 90 071 (2 4-б)2-//=590 015 2г 4-13 = 90 073 (2 4-7)2— N=680 088 2г 4-15 = 90 075 (г48)2 —JV=770 163 2г4-17 = 90 077 (г 4-9)2— А=860 240 2г 4-19 = 90 079(2 4-5)2-Л = 499 944 2г + 11 = 90 071 (2 4-б)2-//=590 015 2г 4-13 = 90 073 (2 4-7)2— N=680 088 2г 4-15 = 90 075 (г48)2 —JV=770 163 2г4-17 = 90 077 (г 4-9)2— А=860 240 2г 4-19 = 90 079(г 4-10)2-Л =950 319 2г4-21= 90 081(г 4-И)2 — N =1 040 400= =10202*=45 041у = 1020а=х-|-у = 46 061Ь=х — у=44 021(г 4-10)2-Л =950 319 2г4-21= 90 081(г 4-И)2 — N =1 040 400= =10202*=45 041у = 1020а=х-|-у = 46 061Ь=х — у=44 021

г2 — А = 49619

2z 4- 1= 90061 (2-pi)2 —А = 139 680 2^4-3=90063

(24-2)2-^=229 743 2г 4-5=90065

(z 4-3)2— А= 319 808 2^4-7=90067

(2 4-4)2-/7=409 875 2г 4-9=90069

г2 — А = 49619

2z 4- 1= 90061 (2-pi)2 —А = 139 680 2^4-3=90063

(24-2)2-^=229 743 2г 4-5=90065

(z 4-3)2— А= 319 808 2^4-7=90067

(2 4-4)2-/7=409 875 2г 4-9=90069

(2 4-5)2-Л = 499 944 2г + 11 = 90 071 (2 4-б)2-//=590 015 2г 4-13 = 90 073 (2 4-7)2— N=680 088 2г 4-15 = 90 075 (г48)2 —JV=770 163 2г4-17 = 90 077 (г 4-9)2— А=860 240 2г 4-19 = 90 079

(2 4-5)2-Л = 499 944 2г + 11 = 90 071 (2 4-б)2-//=590 015 2г 4-13 = 90 073 (2 4-7)2— N=680 088 2г 4-15 = 90 075 (г48)2 —JV=770 163 2г4-17 = 90 077 (г 4-9)2— А=860 240 2г 4-19 = 90 079

(г 4-10)2-Л =950 319 2г4-21= 90 081

(г 4-И)2 — N =1 040 400= =10202

*=45 041

у = 1020

а=х-|-у = 46 061

Ь=х — у=44 021

(г 4-10)2-Л =950 319 2г4-21= 90 081

(г 4-И)2 — N =1 040 400= =10202

*=45 041

у = 1020

а=х-|-у = 46 061

Ь=х — у=44 021

В этом случае к цели приходят сравнительно быстро, так как а и b мало отличаются друг от друга. Вследствие этого часто подходящее кратное числа N разлагается легче, чем само N. Установить, что число является квадратом будет легче, если иметь в виду, что квадраты могут последней парой знаков иметь лишь 00,01,04,09,16,21,24,25,29,36,41,44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96. Таким образом, в нашем примере следует испытывать лишь 499 944 и 1 040 400.

Рассмотренное в § 21 представление формой х2 Ц-^_у2 (d > 0) использовалось Эйлером для разложения на множители. Если для N существуют два различных представления, то N можно

9 А. С. де Монтферре, Gorresp. math. phys. 5, 94—96 (1829). Жигмонди показал (Mh. Math. Phys. 5, 123 (1894)), что (W — 3) / 2 можно заменить на ^—9)/ 6.

разложить на два множителя. Из N=x\-\-dy\ = x^-\-dyl следует именно

X, — Xs d (X —у2) или ^‘"^ = d ^"h^*.

Сократив дроби, получим целые, отличные от нуля, числа и, -v, 5, /, (и, г/)=1, такие, что

а)х,—х2 = М b) у2 — yt=vt, 1(35)

d) x,4-x2 = vs. J v ’

Отсюда получаем хг = ^dut-^-DS^ / 2, ^x = ^us— -и/)/2 и

A^ + ^-l^ + ^^H^(36)

Если d четное, то вследствие предположения о нечетности N, числа хх и хг должны быть нечетными, так что по (35, d^ хотя бы одно из чисел -и, 5 четное. Если 5 (соответственно -и) нечетное, то по (35, Ь, с) и (соответственно /) четное, так как Л"НЛ и Л—У\ нмеют одинаковую четность. В каждом случае, таким образом, одна из скобок в (36) делится на 4. Для нечетного dxi n_yz (/ = 1,2) имеют различную четность, так что ^Чл^ и yt Ч- у, одновременно нечетные или четные. В первом случае и, -и, 5, / — нечетные и каждая из скобок в (36)—• четная. Во втором случае из (35) вследствие ^и, -v) = 1 следует, что 5 и / — четные, так что вторая скобка в (36) делится на 4. Таким образом, во всех случаях (36) дает нетривиальное разложение N.

Разыскивая представления N, снова можно использовать упрощения, упомянутые в методе Ферма, и часто количество случаев, подлежащих испытанию, допускает значительное сокращение.

Пример 1.

N = 1 000 009 = 1 0002 -|- З2 = 9722 + 2352, d^, и = 7, v = 58, / = 4, 5 = 34, N = (72 4- 582) (22 4- 172) = 3413 • 293.

Пример 2.

N= 13 717 421 = 7612 4- 7 • 13702 = 4392 4- 7 • 1390й, d = 1, и = Ж, ^=10, / = 2, 5=120, N= (102 4- 7 • 232) (602 4- 7.12) = 3803 • 3607.

IV. СПЕЦИАЛЬНЫЕ ПРОСТЫЕ ЧИСЛА

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

Легко можно показать, что никакой многочлен, отличный от постоянной, с целыми коэффициентами не может для всех п, или для всех достаточно больших п, представлять простые числа. Для доказательства рассмотрим y—f^ = aQxk-\- -\-аххк-г -\- . . .-А-а^а^^^. Для достаточно больших х0 будет -у0=/(х0)> 1. Натуральные числа /(^0 + х0), г = 0, 1, 2, . . . все делятся на _у0, что видно из разложения членов а^ (ryQ -|- х0)к-'4 по биному. Таким образом, существуют сколь угодно большие составные значения /(л). Как мы увидим в § 26, даже для квадратичной функции существуют сравнительно длинные последовательности простых значений.

Естественно рассмотреть показательные функции типа /^ = an + bn, где а, b— целые. Здесь следует принять во внимание разложения

ап — Ьп = {а — Ь^ (ап~1 + an-* b + . . . + abn"2 + Ьп”1), (37) + 1 = (^„^П-Х Ь_^ # е_аЬ2П-Х_^Ь.Пу ^

Заменив в (37) а и b соответственно на ат и Ьт, увидим, что, кроме тривиальных исключений, число атп — Ьтп является составным. Простые числа могут появиться лишь при а — b = 1 и простом показателе степени. Простейший случай а = 2, b = 1 приводит к простым числам вида Мр — ^Р—1 (простые числа Мерсенна), которые мы рассмотрим в § 24. Из (38) следует, что ят4~^т может быть простым числом лишь тогда, когда т не имеет нечетных простых делителей, т. е. является степенью числа 2. Для а = 2, #=1 получаем простые числа

т) Функцию /(/?) = \п У^2] можно, например, использовать лишь до тех пор, пока известно десятичное разложение для }^2. Число [1,414 ...*п\ для п > 1000 уже не определено, (так как у 2" задан здесь только с тремя знаками после запятой).

вида Fn = 22n-41 (простые числа Ферма). Ферма полагал, что Fn является простым числом для всех zz, однако Эйлер показал, что уже F5 является составным (см. § 25).

Новые большие простые числа часто также находят вычеркиванием получаемых из (37) или (38) делителей составного ат Ч- Ьт. Так, А. Ферье в 1951 г. нашел 44-значное число (2148 -|- 1) / 17. Далее, простым является число, состоящее из 23 единиц (1023 — 1)/9.

Простые числа Мерсенна М-=2Р — 1 имеют особое значение вследствие их связи со знаменитой проблемой совершенных чисел. Число N называется совершенным, если оно равно сумме своих собственных делителей, т. е. если для суммы a (N) всех делителей будет а (M) = 2/V.

Пример. 6=1 —|—2—|—3. Эвклид доказал, что если ^=2^(2^ + 1 — 1) = 2гр, где р— простое число, то N—совершенное число. Действительно,

° W = ^ 4” ^ 4" 22 4" • • . 4" 2* 4" Р 4" 2р -(- . . . 4~ ^р = = kP~V l)(2f+1 — 1)= 2t+1(2^+1— 1) = 2М

Так как Л42, М3, М5, уИ7— простые числа, то получаем четные совершенные числа 6, 28, 496, 8128.

Эйлер заметил, что и, наоборот, каждое четное совершенное число N имеет форму, указанную Эвклидом. Для доказательства предположим, что М=21и, где и — нечетное, является совершенным числом. Каждый делитель N имеет вид 2а 8, где 8 | и и 0 ^ а ^ Л Отсюда упорядочиванием по степеням 27 получается:

0 ^ = a (zz) (1 4- 2 + ... 4- 2f) = а (и) (2'+1 — 1) = 2N=2f+xu,

откуда, вследствие нечетности и1 а (и) должно иметь вид: ^•2f+1, a u^d^1^1—1). Если бы былоб?^!, то имели бы a(zz)>^4-(2/+1 — ^d = d.2u\

так что d=\ и и имеет делителями лишь 1 и 2/+1— 1, т. е. является простым числом. До сих пор не известно, существуют ли нечетные совершенные числа.

Число М не для всех р является простым, как видно из примера Л4П = 2047 = 23-89. Мерсенн в 1664 г. для р ^ 257 указал все Мр1 которые он считал простыми числами. Исследования в этой области, законченные лишь в последнее время, показали, что в пяти случаях Мерсенн ошибся. Сегодня из-

вестно, что Мр является простым числом для р = 2, 3,5, 7, 13, 17, 19, 31, 61, 89, 107, 127 и составным для всех остальных р ^ 257. С помощью электронной счетной машины SWAC (Калифорния) летом 1952 г. найдены новые простые числа Мерсенна Л4521 и Л4607. Между Л4127 и Л/521 лежат 66 составных Мр.

Наконец, SWAC установила еще, что Л41279 является простым числом. Это число имеет 386 знаков, тогда как открытое Лукасом в 1876 г. число Л4127, которое в течение 75 лет было наибольшим известным простым числом, имеет лишь 39 знаковх).

Основой всех этих результатов является критерий для М р, идущий в основном от Лукаса и весьма изящно доказанный Д. X. Лемером [15] в следующей форме.

Теорема 15. Число Мр = 2р— 1, где р— нечетное простое, тогда и только тогда простое, когда Мр делит (р— 1)-й член рекуррентной последовательности sx — 4, s2 = 14, . .. ,^ = 5^ — 2.

Пример. р = 7,714=127, s3 = 67(mod!27),

s4 = 672 — 2 = 42 (mod 127),55 = 422 — 2 ее —16

(mod 127), se = 162— 2 = 254 = 0 (mod 127). Условие теоремы 15 можно несколько ослабить. Для того чтобы М было

простым числом, достаточно, очевидно, чтобы sp_2~ + 2 2 (mod Му так как отсюда следует s x~2p + 1— 2 = = 2(2^— 1) = 0 (mod^).

Подготавливая доказательство теоремы 15, положим я=1-|-)/"3, Ь=1—У 3, так что a-\-b = 2, ab = —2, а—^=2]/3. Определим две последовательности целых чисел иг и -иг равенствами ur = (яг — br^ / (а — by vr = аг +^\ так что их = 1, и2 = 2, и3 = 6, и4 = 16,, . . ^х = 2, ^2 = 8, ^ = 20, . . . Легко проверяются соотношения

2«г+5=иг^ + ^,(39)

(— 2}s” ur_s=usvr — urvs,(40)

2vr+s = vrvs4-12urus,(41)

«гг=“г^>(42)

^r = ^ + (-2)r+1,(43)

г'2— 12 u2r=(—2p2.(44)

9 386 знаков M1279, так же как 770 знаков соответствующего совершенного числа, см, у Улера (Uhler) [30].

Пусть р>3 и (йм, р^=р, но ^ипр^=1 для r^w, т. е. ту— наименьший индекс, для которого uto делится на р. Таким образом, простому числу р соответствует «ранг» <о; например, 11 имеет ранг 5. Мы увидим, что для каждого р > 3 существует конечное <о.

Лемма 1. Если со — ранг числа р, то р входит в иг тогда и только тогда, когда г кратно со.

Доказательство. Пусть ЗЛ— множество всех индексов г, для которых иг ~ 0 (mod pY По (39) и (40) вместе с г и 5 в состав ЗЛ входят и r + s. Если <о наименьшее положительное число в ЗЛ, то последовательным вычитанием (о получим г — ^<0 = 0, так как для любого целого к число г — кю входит в ЗЛ и не может находиться между 0 и <о. Таким образом, r = kto.

Лемма 2. ир = ^j-^ (mod pY ч)р™2 (mod pY

Доказательство. На основании (7) и того факта, что за исключением первого и последнего биномиальные коэффициенты р-й степени делятся на р, получаем:

р-1

{о +К5)'-(1 -ИЗ)"} =2 ^+1)з* =

fк — 0

= 2 — (у) (mod PV

Так же получаем:

р-1

__2

^ = (1+КЗ)/' + (1-КЗ)" = 2 £(2^)3A = 2(mod р).

л=о

Лемма 3. Если (о — ранг р, то со =^ р —|— 1.

Доказательство. Достаточно показать, что ирЛ.хир_х делится на р, так как тогда р будет входить в ирА.х или up_v

Положим в (39) и (40) г — р и 5=1, тогда вследствие того, что их=\ и Dx = 2,

2"p+i = 2«p + ^ 4^., = ^ —2ир)

и по лемме 2

8^+1 ^-т = 4^ —^ = 4•(-{- I)2 — 4 = 0 (mod р).

Доказательство теоремы 15. а) Условие необходимо.

Пусть Мр— простое число. Мы должны показать, что5р-1=0 (mod ^р)1 вместо Sk мы можем рассмотреть также а^=22 5А:а, = 8, а2 = 56, а3 = ЗЮ4. Именно, так

как Мр нечетное, то из ар_г — 0 (mod М3 следует тотчас 8р_, = 0 (mod Мр). Так как St+1 = S^ —2; то аА+1==а| — — 22*+1. Положим в (43)г = 2”, тогда v^,—у^— 22*+*.

Из обоих последних равенств вследствие *иг = ^ = at следует, что а^ = ^. Теперь нужно показать, что г^р-1 = = ^(д^^/г делится на Мр. Положим в (43) г = (^4 0 / 2, тогда получим:

Alp—1

1= ^р + 14 * ^ 2 •(45)

2

/ 2 \

Так как Мр имеет форму 8х— 1, то вследствие (10) ( — 1 = 1 и по (7)Р

Му—Л

2 2 = 1 (mod мру

Подставим это в (45), тогда останется показать, что ^4-1 = — 4 (mod Мр^ так как тогда

'UMp-vi = 0 (mod Мр\

2

По (41) имеем:

^Mp-V 1 = ^Мр^х + 1 ^Mpttx = ^Мр + 12Пмр> (46)

Вследствие (38) Мр = (2^ -f- 1) — 2 = 1 (mod 3) и по теореме 6 далее получаем:

Мр)—и;-

так что из леммы 2 и (46) следует

^+1 = ^Мр + 6иМр ЕЕ 2 — 6 ЕЕ — 4 (mod Мр\ что и оставалось доказать.

б) Условие достаточно. Пусть £„_, делится на N=2n—1. Тогда N делит также ап_1 =^«-1. Пусть р— простой делитель N и со — его ранг. Так как по (42) N делит иу = •= uy-w^n-i, то ы2п=0 (modp), так что по лемме 1 числом делит 2я. С другой стороны, со не должно входить в 2я"1, так как иначе по лемме 1 наряду с -и2п-1 на р делилось бы

и M2n~i, а это противоречило бы равенству (44), правая часть которого ^0 (mod pY Отсюда следует, что а) = 2я. По лемме 3 имеем, однако, р^^—1=2Я—1 — /V, так что p = N и N—простое число.

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

Теоремы 16. Если числа р = 4п-|“ 3 и q = 2р -|- 1 = = 8^4*7— °^а простые, то Мр = ^ (mod qY

Доказательство. Если q— простое число, то вслед-

ствиествие1, так что по (7) №-^^ = 2^= 1 (mod ^) и

ствие

ствие

Мр = 0 (mod qY Так как для р*>3 всегда 2Р—12> 2р —|— 1, то в этом случае Мp>q, т. е. составное. Примеры: 23|AfH, 47|/И2„ 503|/И251.

Вообще говоря, разложение на множители Мр, о которых известно, что они составные, не найдено. Другой нерешенной

проблемой является вопрос о существовании бесчисленного множества простых чисел Мерсенна.

Простые числа Ферма Еп — ^-^-Х имеют значение для задачи деления круга. Гаусс доказал, что правильный

/n-угольник тогда и только тогда можно построить с помощью циркуля и линейки, когда в каноническом разложении (1) числа т каждое р'>2 имеет показатель ер=\ и является простым числом Ферма. В то время как показателям/г = 0, 1, 2, 3, 4 соответствуют простые числа, ^ = 2s2 —[— 17 как заметил Эйлер, уже составное. Именно, Fb делится на 641, как видно из следующих сравнений по mod 641: из равенства 641 =5-274-1 следует 5-27 = — 1, так что 54»228 = 1. Так как 641 = 54 -|“ 24, то 54 ее — 24, откуда 54- 228 = — 232 = 1, или 2"24~1 ~ 0. В настоящее время известно, что Fn для п = 5, 6, 7, 8, 9, 11, 12, 15, 18, 23, 36, 38, 73 является составным. Для каждого из этих Fn, кроме п = 7 и 8, известен один делитель. Так, F73 делится на простое число 5-2754~1. Для п^>4 не известны простые числа Fn, так что количество простых чисел Ферма, вероятно, конечно.

Критерием для простоты чисел Fn служит

Теорема 17. Число Fn = 22n1 тогда и только тогда простое, когда

Fn-\3 2 = —l(modF„).Fn-\3 2 = —l(modF„).(47)(47)

Fn-\

3 2 = —l(modF„).

Fn-\

3 2 = —l(modF„).

(47)

(47)

Пример. Fa=17, З8 = 812 = (—4)2 = — 1 (mod 17).

Доказательство. Так как 4^ = 4 (mod 12) для всех т^^, то Fn для п^Л имеет вид 12^—1—5. Если Fn — простое число, то вследствие (13) имеем =—1 п(47)тот- час вытекает из (7). Наоборот, из (47) следует, что 3^”1 = = 1 (mod FnY Если р простой делитель Fn и по mod р число 3 принадлежит показателю а, то Fn— 1=22” делится на а, т. е. а является степенью числа 2. Возможно лишь а = 22\ так как при меньшем а было бы 3(F«-1)2=1 (mod/?), а это

для р*>2 противоречит сравнению (47). Так как р—1 = = 0(mod6z), то p = ^.22”-|-1, но тогда ^ = 1 и p = Fn.

Мы можем легко указать форму делителей составного Fn с помощью

Теоремы 18. Для п> 1 каждый простой делитель числа Fn = 22n-\-\ имеет вид р = ^.2”+2-|-1.

Доказательство. Так как 22" =—1 (mod/?) и 22”+‘ = 1 (modp), то по mod/? число 2 принадлежит показателю 2” + 1, так что /?=1 (mod2” + 1). Для п^Х^ таким / о \ образом, р = 1 (mod 8), так что по (10) и (7) 2^-О/2 = / — 1=1 (mod/?). Отсюда (/?— 1)/2 делится на 2п + \ т. е. р = й-2п+2-\-\.

Возможные простые делители числа F5 имеют вид 128&-Р1, и теперь легко найти делитель 641 = 5 -128 —|— 1. Делители F73 имеют вид Д^ = &* 275 -]-1. Для к=\, 2, 3, 4 число Nk делится соответственно на 3, 17, 5, 3. Легко видеть, что F73 не делится на эти числа, так что первым делителем F73 может быть лишь Nv Морхед показал, что это действительно так. Так как N^ наименьший делитель числа F73, то N5 простое число. Таким способом можно открывать новые большие простые числа.

Последовательность чисел Fn всегда дает новые простые делители, так как Fn взаимно просто со всеми предшествующими Fs^s <^nY Это тотчас следует из соотношения F0F1 Рг ... Fn_x = 22n— 1 =Fn — 2, которое выводится пере-

множением п тождеств (22Г—1) (22Г4™ 1) = 22Г+1—1 (/• = 0, 1,2, . . ..п—1). Это дает еще одно доказательство теоремы 2.

Так как 4т = 4 (mod 12), то Fn = 5 (mod 12), так что по (13) для Fn=p будет 3^-1)/2 = ^) =— 1 (modp). Это означает, что число 3 — первообразный корень для любого простого числа Ферма; каждый собственный делитель числа р—1 является одновременно делителем (р—1)/2 = 22””1, так что 3<^~1>/2 = 4* L если 3 не принадлежит по modp показателю р — 1. Если бы целое число g могло быть первообразным корнем лишь для конечного числа р, то было бы лишь конечное число простых чисел Ферма. Однако еще не доказанное предположение Артина гласит, что любое g^+l, не являющееся квадратом1), — первообразный корень для бесконечного множества р.

Простые числа как значения квадратичной функции. В то время как значения функции ах-^-Ь для (а, £)=1 по теореме 4 бесконечно много раз бывают простыми числами, соответствующая теорема для / (х) = ахг 4* Ьх 4* с не известна даже для простейшего частного случая х2 -|- 1. Разумеется, дискриминант Д = £2— Атас не должен быть квадратом и числа с и а-^-b не могут быть одновременно четными. Так как 4а (ax2-|-6x4-c) = (2ax-J-^)2 — Д, то ^А^ — 1 для всех простых делителей /(х), где р называется простым .делителем /(х), если существует такое х0, что /(хо) = О (modp).

В 1772 году Эйлер открыл, что Д (х) = х2 4"*4~ 41 для Х = 0, 1,2, . ..,39 является простым числом. Все значения этой функции — нечетные и для всех нечетных p^Vj\{39) = = /1601 <41 число Д =—163 является квадратичным невычетом, так что ни одно из 40 чисел /х (0), fx (1), . .. ,Д (39) не может быть составным. Еще более длинные интервалы простых значений имеют функции/2 (х) = х2—х—}—41 и

/8(х) = х2 —79x4-1601 =(х — 40)2 + (х —40)4-41, для которых также Д =— 163. Функция/2 (х) для 0^х^40 дает простые числа, так как /2 (40)= 1601. Функция Д(х)

для 0^х^79 даст простые числа, так как /3(79) = =/3(0)=1601.

Если поставить вопрос, для каких простых чисел А функция /4 (х) = х2 4- х А принимает подряд простые значения для О^х^Л— 2, то легко отыскиваются малые значения Л = 3, 5, 11, 17. Несмотря на далеко идущие вычисления, не найдено никаких А >41.

Значения функции Д (х) для х>40 не делятся на р ^ 37 и следует полагать, что Д (х) вообще представляет много простых чисел. Действительно, для х^ 11 000 функция Д (х) дает 4506 простых чисел. Еще больше простых чисел, именно 4923 для х^ 11 000, дает функция х2Ц-х~4 4-72 491, дискриминант которой, равный 289 963, является квадратичным невычетом для 2 <>^43, так что ее значения взаимно просты с р^431)’

Л. Полетти вычислил простые значения между 107 и5-108 для некоторых квадратичных функций и нашел 17 200 простых чисел.

Для примитивных квадратичных форм имеет место найденный Дирихле аналог теоремы 4:

Форма ах2 -|“ Ьху 4~ су2 представляет бесконечно много простых чисел, если а, Ь, с взаимно просты. Частный случай формы, разлагающейся на множители

(ах + ^ ^х 4- ^ = аух2 + (аЗ + ЭД ху + рЗ/, (48) где (а, ^) = (у, §) = 1 легко сводится к теореме 4. Очевидно, должно иметь место уравнение ах -[- ^ = 1, которое разрешимо, так как (а, р)=1. Из решения х0, у0 получается бесконечно много решений х0>яр, у0— па. Второй множитель в (48) приобретает теперь вид ух0 4" £> "4" (У? — 8а) zz — = А-^-Вп. Так как аА-\-уоВ = ^, то общий делитель АиВ должен входить в у, следовательно, из-за (a, j/0) = 1 также и в 8. Из условия (у, 8)=1 следует теперь (Л, В)=1, так что можно воспользоваться теоремой 4.

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

х) См. N. G. W. Н. В ее ger, Nieuw Archief voor Wiskunde [2k 20, 48—50 (1939).

что [Л3<г] для х— 1, 2, 3 . . ., всегда будет простым числом. Этот результат имеет лишь теоретическое значение. Так как известны лишь немногие знаки Л, то действительно вычислить можно лишь немногие простые числа. То же возражение вызывает доказанная Е. М. Райтом [31]

Теорема 19. Существует вещественное число а —а0, обладающее тем свойством, что числа [2ао], [2*1], . определенные рекуррентной формулой ап+] = 27”, все являются простыми.

Доказательство. По теореме 31, § 39, между N и 2N для N^> 1 всегда лежат простые числа. Таким образом, мы можем построить такую последовательность простых чисел Р2, . . ., что

2р-<Р„ + х<Р„+1 + 1<2^+1 («=1,2,...). (49)

Пример. Рг = 3, Р2=13, Р8= 16381,... Под Logx будем понимать логарифм при основании 2, a Logkmx обозначает п раз последовательно взятый логарифм Log Log... Logx. Из (49) логарифмированием получаем:

Log*”’P„<Log*"+”Pn+I<Log*"+”(P„+1 + l)<

<Log'">(P„ + l).

Положим

^ = Log*"’P„, Y„-Log’">(P„ + l), тогда

Pn<P«+I<Yn+1<b (« = 1,2,3, ...).

Вытекающая отсюда цепочка неравенств

₽1<?2<?з<--- <Р„<уп<Г»-1< ••• <Ys<Y.

при п—> оо определяет, очевидно, число а как общий предел рп и уи, причем ри < а < уи Для всех л- Возвращаясь от логарифмов к числам, получаем:

Log*”-1> Р„ < 2’ = а, < Log*""1 > (Р„ + 1),

Log*"-2’ Р„ < 2’- = а2 < Log*"'2) ^Р„ + 1),

рп < 2’Л-1 = «„<^+1,

или /’„ = [«"], ч. т. д.

Для Р]=3, Р2=13, Р5-- pi=Log3 = 1,58495, p2 = Log(2)13 = 1,88765, p3 = Log(3) 16381 = 1,92877,

16381 получаем:

— Log 4 =2,00000; y2 = Log<2) 14 = 1,92877; y3 = Log(3) 16382 = 1,92877.

Здесь a = 1,92878... P4 имеет уже около 5000 знаков.

Простые числа с заданными первыми и последними цифрами. Из критериев делимости следует, что последними цифрами простых чисел могут быть лишь 1, 3, 7 или 9, тогда как первой цифрой может быть каждое из чисел 1, 2, . . ., 9, как видно уже на простых числах <2 100. Серпинский [27] доказал следующие общие теоремы:

Теорема 20. Если cv с2, . .., ст — конечное число цифр десятичной системы и сх ^ 0, то существует сколь угодно много простых чисел, начинающихся последовательностью Цифр cv ...,ст.

Доказательство. Пусть а — zn-значное число, построенное из cv cz, . . ., ст, взятых в указанном порядке. Достаточно показать, что

lim {тг [(<2 —1) 10п] — тт (а- 10”)} = оо, (50)

так как тогда для заданного а существует бесконечно много таких п, что

71^4-1). 10”] — TV (6Z-10") > 1,

а каждое из таких неравенств подтверждает существование простого числа между а* 10” и (^4* 1 причем все такие числа начинаются теми же цифрами, что и а. Для доказательства (50) воспользуемся теоремой 3. Так как

, Z2loglO + log(^ + l)_1

Zoo zHoglO + log^ — 1

то после простых преобразований получаем:

ИЛИ1аИЛИ1а. к[(« + 1).10П_^+1к (а-10^— а ’

ИЛИ

1а

ИЛИ

1а

т; [(я+1). 10"](л. 10")

, ооТГ^.Ю")

Так как знаменатель стремится к бесконечности, а отношение остается положительным, то и числитель должен стремиться к бесконечности, ч. т. д.

Теорема 21. Если cvcv...,cm— конечное число десятичных знаков и ст=\, 3, 7 или 9, то существует бесконечно много простых чисел, оканчивающихся последовательностью знаков cv с^ ...,ст.

Доказательство. Число я, построенное из cvc^... • *•,ст, взятых в такой последовательности, взаимно просто с 10ш. По теореме 4 существует бесконечно много р = ^-10т-(- 4~а, h > 0. Последние т цифр числа р совпадают со знаками а, ч. т. д.

Пример. Существует бесконечно много простых чисел вида 111... или... 111, где в начале или конце стоит, например, 10 единиц.

V. СУММЫ ПО ПРОСТЫМ ЧИСЛАМ

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

Если /(х) и g (х)—две функции неограниченно возрастающей вещественной переменной х, g (х) )> 0 и существуют два положительных постоянных числа С, и С2 J), таких, что |/(х) | << Cxg (х) для всех х^>С^ то пишут /(х) — О[^(х)]. Это означает, таким образом, что отношение |/(х)|/^(х) при х—> оо остается конечным. Функция g(x) дает, таким образом, асимптотическое поведение /(х) в указанном выше смысле и, естественно, ни в косм случае не определяется функцией /(х) однозначно. В частности, символом 0(1) обозначаем любую функцию, ограниченную для х>02.

Примеры.

2х-4-]//' x=0(x),x-f-x-1 = О(х),

sinx=O(l), х(х— 3)-1 = 0(1), log х = О (х),log х = О ^V-к),

log log х = О (log х),ch х = О ^ех\

ВО (х) + 50 (log х) = О (х).

Если отношение f(x)lg(x) для х—>оо стремится к нулю, то пишем fVx^ — °\gkxW В частности, о(1)— величина, стремящаяся к нулю. Очевидно, из f (х) = о [g (х)] следует также /(х) = О [g(x)J, но не наоборот.

Примеры:

х = о (х2), sin х = о (]/"х), л (х) = [1 4" ° (Uj^/log^*

Мы часто пользуемся соотношением

(51)(51)\о^х — о (хЗ), а — любое, Р>0.

(51)

(51)

При доказательстве можно предположить, что а^>0. Далее, по правилу раскрытия неопределенностей

lim х”^ logax = ( Иш х а log х)” = ( Иш аЗ Хх а)а = 0.

Х-> 00

Таким образом, logx стремится к бесконечности медленнее, чем любая степень х со сколь угодно малым положительным показателем, log logx и log log logx растут еще медленнее; так, log log log (101000) = 2,04...

Если отношение f(x)lg(x) стремится к 1 при х—> оо, то пишем /(x)^g(x), а функции называем асимптотически равными. В этом случае можно также писать /(х) = g(x) [14~о(1)]«

Примеры, х-|-sin х ^ х, л (х) x/logx. Эти равенства обладают свойствами рефлексивности и транзитивности, так как из / ^ g, g h вследствие того, что (lim//g) (lim g//z)= = 11ш//Л=1, следует, что f к.

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

У -= Г^а-г+О^^к^х + С. + О f-) , (52) п^х 1

^-р-^+с. + о^-1-?).^-р-^+с. + о^-1-?).(53)(53)

^-р-^+с. + о^-1-?).

^-р-^+с. + о^-1-?).

(53)

(53)

Для р > О получаемДля р > О получаем^л—^О(1).^л—^О(1).

Для р > О получаем

Для р > О получаем

^л—^О(1).

^л—^О(1).

X

У, log п=^ log и du -|- О (log х) =

= х log х — х -|- О (log х\(54)

= —4. г -к О f .(57)

logx 110 1 \xlog2xy'

Так как вследствие (51) \^п<^пА для постоянных к > О

и п^п^ то для /^1,5 по (53) имеем:

(58)(58)У п-^ log^ л< У л"/+0,25 = О(1).

(58)

(58)

п^хп^х

При всех этих оценках следует различать главный член и 0-член, или остаточный член. В главный член следует включать лишь такие слагаемые, которые имеют больший порядок, чем остаточный член, и следовательно, не могут быть поглощены им.

Следствие из канонического разложения п\ ’). Логарифмированием получаем из (2)

£log&=£ [7] Ц [4] logp+...

£ = 1Р^п Jр^п VP J

Для 1^2^ /^2 вследствие Xogp^Vp и (53) имеем:

^Г [^-] Xogp^p-t'ogp^p-^ <Спп.

Формула (54) приводит теперь к соотношению

^ (”) = У. [—1 logp = П log п 4- О (л).(59)

Так как [^/р] = [И/р], то это имеет место и для нецелых/?.

Выясним теперь, что произойдет, если опустить квадратные скобки в (59). Заметив, что неравенство п/2 <р ^ п равносильно неравенству 1^у<2, вследствие [х]— 2[х/2]^0 для х>0, получим:

О(л) = Л(л) —2Л (у) =

= 0(л)-0(|) ,

где для краткости введено обозначение 0(х) = S !ogp.

р^х

Итак, существует такое С12, что

^ (^2^ у^ у 2Z + 1 у <^ ^1 2 У ^^’ 2, , . е

Сложение этих неравенств дает

■&(«)< Схйп У = 2С^п, или ^(/г) —O(/z).(60)

z—о

Если теперь опустить в (59) квадратные скобки, то ошибка будет<^^(//) = 0(//). Делением на п получается важная

Теорема 22.

£^ = logx+O(l).

р^х

Как следствие, получаем для A (zz) (см. § 16)

Е ^ = 105^ + 0(1),(61)

п^х

так как вследствие (58) часть суммы, распространенная на л=//(/^ 2), сходится.

Частное суммирование. Абелем было указано следующее очень полезное для оценок формальное преобразование конечной суммы, законность которого легко проверить:

2 а^ = ах (Ьх — »2) + (а, + а2) (»2 — Ь^ + (а, + а2 + а,) X 1=1

X (^, - »4) +.. . = 2 ( 2 аД (bk - Ьк+ J + bn+x 2 «,- (62) к=\ V=1/Z = 1

Положим ai = ci — ci_v c0 = О, тогда получим формулу, часто оказывающуюся более удобной

2 кч —<4-^= 2 ^(»»—^+J+^A+i-(63)

z = lк=1

Для приложений используем то, Что по формуле Тейлора

/ (х + 1) =/ (х) +/' (X) +,

где 0 < 0 < 1. Отсюда легко получаются равенства

l°g(^-|- l) = log^ + ^"1 -|~0(^“2), ч 1_11।? (64)

log ^к + 1) log к к log2 к *Т* к2 ) * '

Пример. По определению функции 0(х) в § 31 имеем d(/z) — ^(/z— l)z=logzz для п — р и нуль в противном случае. По (63) получаем для целых х

2iog2p= 2 pw—9(z—i)]iog/=

р^хi = 1

= Е ^W'og-rrr + ^W log(x + l).

Вследствие (60), (64), (52)

|£Wogy£r|<2c12x+

+Clllogx+C„ + o(l)=O (х).

Так как

0(х)log (х4-1) = »(х) Iogx4-C144-O (-i-) , то

2 log2 р = $ (х) log х О (х) — О^х log xY р^х

Следующие оценки будем применять в дальнейшем. Из теоремы 22, (60), (63) и (53)

10gx + О(1)==

_ уI »И _У ^W h 1 I linm

— 2- A(fc + 1)+ х + 1 ”^ ^ V к +°(1)-

Таким образом, имеем:

Е ^ = Iog* + O(l).(65)

Из (61), (62), (64), (55), (52), (58) следует далее

у Л (”) 1

^—Xogn^

П^х

=-£{1ое»+о(1)}[т+°Ш] +

+ [logx + O(l)] |^logx + O (4-)] = = — 0,5 log2 x-\-0 (log x) -|- О (1) -j- log2x -]- О (log x). Таким образом,

T. ^- log и = у log2 x + О (log x).(66)

Теперь (61) и (66) дают

Епт^хЕпт^хА (л) А ^птА (л) А ^пт£УЯ £y=uy/k,gi + o(,)llto

Епт^х

Епт^х

А (л) А ^пт

А (л) А ^пт

п тI ^п 1 х Ц п

П^Х m^.2L п^х V/

= 10gx Х^ — £ ^log«4-O(logx) = n^XП^Х

= log2 X — У ^ log п + О (logx) =

= ^-log2x4-O(logx).(67)

Из (67), (62), (64) следует

£^=2{|*жм}х

жп^хк^х 'J

( 111 । 0,5 log2x + О (log х)

I log ft log (А 4- 1)/ ”* log (%+ 1)

ЧЕ4+о(Ек^хх к^хЧЕ4+о(Ек^хх к^х1к log к1к log кlog%+ 0(1).log%+ 0(1).

ЧЕ4+о(Е

к^хх к^х

ЧЕ4+о(Е

к^хх к^х

1

к log к

1

к log к

log%+ 0(1).

log%+ 0(1).

Таким образом, вследствие (52) и (56)

У1 ^т) Л ^ — log х -j- О (log log х).(68)

^*^ тп \vgmn о i \ s о /х /

(52), ряд ^у-(52), ряд ^у-Сумма величин, обратных простым числам. Хотя

(52), ряд ^у-

(52), ряд ^у-

гармонический ряд расходится вследствие

может сходиться. Это означало бы, что р по сравнению со

всеми натуральными п встречаются очень редко. Однако еще Эйлер доказал, что ^— также расходится. Таким образом,

простые числа встречаются чаще, чем квадраты, для которых ряд обратных величин сходится по (53). Напротив, в § 68 мы увидим, что ряд из величин, обратных простым близнецам, сходится к конечной сумме.

Из теоремы 1 и (52) следует для достаточно больших х рх= П О-р-'Г^ II (1+р-+р-2 + ...)>

Р^Хр^Х

>E-^>i°gx,(69)

поскольку каждое слагаемое правой части встречается в разложении произведения, потому что в разложение п входят лишь р^х. Теперь

Ю^=-Е ю6(> -^)= Е ±+«Е ^=

р^х х г ' р^Х г р^х'

= £7+0(1), 0<6<1.(70)

Р^х

Из (69) теперь следует неравенство ^-^-^loglogx — 0(1), что и доказывает расходимость ряда.

Для того чтобы точнее определить порядок роста суммы У,—, применим частное суммирование в форме (62). С помощью теоремы 22, (64), (56), (57) легко получается:

у 1 у logjo 1 у Н^ — Нп — 1) 1

рр log рп log 11

р^Х Рр^х Рп=2S

„fjiogi+Od)) ^-]-^}+25LL±om =

= е?2"^°^^0(^^^) + 1 +°(1>

= loglogx+Cl$4-o(l).

Таким образом, получается Теорема 23.

52-^- = logl°gx4-Ci5 + o(l).

По Россеру [21] С„ = 0,261497...

Рассмотрим расходящееся к нулю произведение Р^'Ч Из (69) следует, что

С помощью теоремы 23 получается теперь из (70)

Теорема 24.

гт /1 \е-С16 [14-0(1)]

П (1— —1•

\Р')1о§х

По Мертенсу С16 = 0,5772157... (постоянная Эйлера)). Заме- 12

ним в (70) — на — и исключим р = 2. Тогда аналогичным образом получается.

Теорема 25.

П ^\сХ1-уо^

р) 1о2* *

По Россеру [21] С17 = 0,832429...

VI. ОБЩИЕ ТЕОРЕМЫ ОТНОСИТЕЛЬНО л(х) И рп^

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

+X{1 —lim [1—II (^тУ-Г}

I /л—>со L£=2 \ ^ / J 7

На самом деле такие формулы дают мало сведений о природе функции, определяющей распределение простых чисел.

До некоторой степени практически полезный подход к вычислению л(х) дает решето Эратосфена (§ 4). Если вычеркнуть из последовательности натуральных чисел ^ х простые числа рх^У х вместе с их кратными, то останется л (х) — л (]/х) простых чисел > ]/х и сверх того число 1.

Этот процесс приводит к соотношению

-1:Ш+-= Е м^Щ. 1)

Kj<k 1 J кАd\pxpi- Рт\У х^ ^ J

Так как при вычеркивании — чисел, кратных рь LA’JL PiPj J

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

дважды и нужно снова один раз отнять это количество и т. д. После конечного числа шагов ряд обрывается.

Пример, л (30) —л (5) + 1 = 30 — (15 + 10 + 6) + + (5 + 3 + 2)—1.

Е. Мейссель доказал в 1870 г. теорему, которая позволяет проводить практическое вычисление л (х) далеко за пределами таблиц простых чисел. С помощью этой теоремы было вычислено л (109) = 50 847 478.

Теорема 26. Пусть ср (х, г) означает количество натуральных чисел ^ х, не делящихся ни на одно из первых г простых чисел рх = 2, р2 = 3, . . . , рг Если положить л (х1/з) = пг, ъ(х'^) = п и п — m = s, то

S

л(х) = <р(х, т^т (s+l) + ^i^—i-^1^^-)- (72)

Доказательство1). Существует ср (х, к — 1) натуральных чисел ^ х, взаимно простых с pv рг1 . . . , pk_v Из них ровно ср (^Р"1, к— 1) делится на рь так как в ср (х, к— 1) учтены лишь те целые кратные hpk, h^xp”1, для которых (Л, Р^Р2* • -^-J^^^* Таким образом,

ср(х, к^^^х, к—1) — ^txp™\ к—1).(73)

Просуммировав (73) для к = т-^- 1, т-^-2, ... , п, получим: f^, /г) = <р(х, т) — 2 у(xp-|t, /»4-т—1).(74)

Из определения tn, п и s следует 112

<Рт+-^х- ^хр-^т<х3(т=1, 2, ... , s).(75)

Для ^<^а^Ь^а^ имеем ср[^, п(а)] = 1-|-л(^) — л(^)> так как числами, учитываемыми символом ср [#, п (а)], являются 1 и простые р, для которых а<^р^Ь. Для Ь — х и а = хх^

^{х, п} = 1 -|- и (х)— п или п (х) = ср (х, п) + п—1.(76)

По (75)

, или l^xzHгт-¥хг< лл + т>

так ЧТО

/» + т—1)=1.

При а = рт+т, Ь = хр-^Х

V'« + т) = 1 + п ^Р"^^-) — т — "

и отсюда вследствие (73)

Vte+T- "^ + Т — 1 ) = ^ (^z^+t’ /« + ^) +

+ <?(^+т>^ + т—П^тг^р-^) —(/« + t —2).(77)

Из (76), (74) и (77) получаем окончательно

п(х) = ф(х, от) — 2 ^^Рт+т* m-Vt— b^-OT-j-s — 1 =

= ф(х,от) — 2 "(^+4 + 2 (от + т~ ^A-mYs— 1 =

5

= ^kx, TH) + /и (s + 1) 4- --(,y ~!) — 1 — 2, n kxp-^Y

T = 1

При применении (72) больше всего труда требует вычи

сление ср (х, ту Если Vx"\ = gpxp^.. .рк-у-г, где g и г — неотрицательные целые числа, то

^Y, к> = ^кР1Рг. • .PA-V^V, к\ <1^

Среди чисел 1, 2, ... , {plPi ... р^, ... , g^p.p^ ... р^ имеется точно g'^ (рхр2 ... р^, взаимно простых с pv р2, ... , pki так как каждая полная система вычетов по mod рхр2 ... рк

содержит ^кРхРг • • • Pt^ таких чисел. Для того чтобы

gpvP^ • * * Pk"Yz kz—V 2, ... , г) было взаимно просто с РХР2 ••• Pk"Vz' нужно чтобы этим качеством обладало и х^ так что таких чисел имеется у (г, ^). Полезной является также легко проверяемая формула

<SKpj>v -Р^ K\ = Q£WxPv .рк, &) = 0,5р(р1р2.. .pkY (79)

С помощью (73), (78) и (79) можно постепенно вычислить р (х, ^)-

Пример.

х=1000, м = п(10) = 4, /г = п(31,6)=11, s = 7,

п(1000) = <р(1000,4)4-32 4-21 — 1 —2 тг(Ю00р^т);

/1000Х„. /ЮООХ 1С /1000\ 1С /юсо\ ..

Ччг)=21- ЧЧП^1’ Kl-IFj = 15> Ччг) ’

/1000\../1000Х..лапах

я ( -^д -1 = 11, п -jj- 1 = 11, так что л (1 000) =

= р (1000,4) — 60,

р (1000,4) = 4р (210) 4-<р (160,4)= 192 -|-ф (160,4),

(160,4) = р (160,3) — р (22,3) =

= 5р (30) 4- р (10,3) — р (22,3) = 42 — р (22,3),

р (22,3) = р (22,2) — р (4,2) = Зр (6) = 6,

р (1000,4) = 192 4- 42 — 6 = 228, п (1000) = 228 — 60 = 168.

Так как п(х‘/з) = т, то р„., Ч-х1'’, так что хр~ 1 ,^х2/з Для того чтобы с помощью (72) можно было вычислить л(х), достаточно, таким образом, знать отдельные простые числа ^х1/з и значения л (.у) для j/^x2/».

Простые оценки для л(х). Очевидно, что каждое натуральное число однозначно представляется в виде произведения квадрата и числа, свободного от квадратов. Количество квадратных чисел ^п будет ^V п* Все числа, не содержащие квадратов, содержатся среди 2ТС<") делителей произведения рхрг. .. р л ^). Если перемножить все эти делители и все квадратные числа ^д, то мы получим все натуральные

числа ^п. Отсюда следует, что л ^ 2"^) ]/« или и (//) (2 log 2)-1 log я ’).

Для того чтобы оценить и (х) сверху, используем метод решета. Если ср ^х, г) имеет тот же смысл, что и в теореме 26, то аналогично (71) имеем:

где d пробегает все делители числа рхр2 .. . рг. Очевидно, и(х) ^ ср (х, г)-]-г. Если опустить квадратные скобки, количество которых составляет 2Г, то ошибка будет не больше 2Г. Отсюда вытекает (см. § 15), вследствие (69) и рг^>г,

П(л:Хх ][ (1 —р *) +

Р^Рт

+ ^ + ^<х П (l_p-i) + 2^<]^7 + 2-\ Р^Рт6

Выберем r = c\o^x, с <1/log 2, так что х>2г, тогда вследствие с log 2 < 1

ТГ (X) < -ji4—ih 2хс tog 2= О f.

V 7 log С + log log X 1\ log log X )

Таким образом доказана

Теорема 27. п(х) = о(х), т. е. «почти все» числа составные.

Истинный порядок роста п(х). Мы ищем для п(х) как можно лучшую приближающую функцию /(х), такую, чтобы относительная погрешность была как можно меньше. Из требования Нт [п(х)—/(х)]//(х) = 0 следует/(х)^-п (х).

Х-->О)

По теореме 3 функцией, удовлетворяющей этому условию, является x/logx. Эту форму функции /(х) открыл эмпирически еще Гаусс, тогда как Лежандр в 1798 г. предположил, что /(x) = x/(logx— 1,08366). Выбор функции x/logx можно обосновать следующим образом. Из (63) получаем:

V^ 1 7С (m) — к (m — 1) утс (^). л (х)

А т —6(6 + 0

’) Сообщено П. Эрдёшем.

Эта сумма по теореме 23 расходится, тогда как сумма 2^ /^(^ + О сходится и л(х) = о(х); таким образом, расходимость должны вызывать множители л (&).

Если A (k) — положительная, ограниченная функция, Л(А)<С20, то ряд 2&1-e?1(^)^(^+1XC2oSA_1_e и схо' дится для любого 8>0. Таким образом, для бесконечно многих к должно быть л (&) > кх~ £А (к), следовательно, л(&) растет быстрее, чем кх — 8 при любом е>0, однако медленнее, очевидно, чем к. Простой функцией, обладающей таким свойством, является k/\ogk, так как k^log к = (&/log k) :кх —8 вследствие (51) неограниченно возрастает. Естественно, функция kjloglogk также удовлетворяет этому требованию. Нужно, таким образом, показать, что kj\ogk дает истинный порядок роста.

Для этого используем введенную уже в § 31 функцию W = 2 log р. По (60) д (хХ ^ х. Рассмотрим часть этой суммы 21°^^’ распространенную на ах^р^х, 0<^а<1, тогда из теоремы 22 следует

^ ±у', у'1оо =

ах ахрр

= log х — log ах — О (1) — log -| — 0(1).

Мы можем а выбрать столь малым, что правая часть окажется >1. Таким образом, имеем:

ах <3 (хХ р х.(80)

Если 2" обозначает часть суммы для ^(х), распространенную на Ух^р^х, члены которой, таким образом, больше, чем log Ух, то

[л (х) — л (К X)] log V X < 2" log р ^ О (х) ^ л (х) log X.

Из (80) вследствие п(1^х) ^Ух = О (x/log х), следует

Таким образом получена

Теорема 28. Для всех х^2 имеем*.

Сы log X ^^ХХ jog % ’

Теорема 28 принадлежит Чебышеву и является главным результатом классической теории простых чисел. По теореме 3 С21 ^ 1 ^ С22 и для достаточно больших х С21 и С22 могут быть придвинуты к 1 сколь угодно близко.

По (80) 0 фх/а) > офх/а = ^х> 0 (х), следовательно, между х и рх/а для любого х лежат простые числа. По сделанному выше замечанию из теоремы 3 следует, что для достаточно больших х и достаточно малых е > 0 между х и (1Ц-е)х лежат простые числа. С помощью глубоко лежащих методов Р. Бройш [2] доказал, что для х ^ 48 между х и 9х/8 всегда имеются простые числа. Ингам доказал, что для всех достаточно больших х между х3 и (х -(- 1 )3 лежит простое число. Будет ли это справедливо для х2 и (х —]— 1 )2 — до сих пор не установлено. Дальнейшие утверждения этого типа мы получим в § 39.

Функции Э(х) и ф(х). Вместе с п(х) и ^(х) в теории простых чисел играет роль и функция ф (х) = 2 log Р = 2 ^ (л)> рт^хп^х

где А (/г)— функция, определенная в § 16.

Если рт— наивысшая степень р, не превосходящая х, то в ф(х) logp встречается т раз, так что ф(х) равна логарифму общего наименьшего кратного чисел от 1 до [х]

4(x) = log{l, 2, ... , [х]}= £ [S^llogP- (81) P^X L

Пример, ф (10) = 3 log 2 —1~ 2 log 3 Ц- log 5 -ф- log 7. Так как неравенство р1 ^х равносильно неравенству р ^ / х, то имеет место соотношение

111

ф(х) = 0(х) + -&(х2)+0(х3) + .. . =5d(xq.(82)

1

Ряд оборвется, как только будет хг < 2, т. е. г> (logx)/log 2. Несмотря не внешне сложное определение, ф (х) является одной из простейших функций характеризующей распределение простых чисел.

В (60) мы видели, что 0 (х) = О (х). Это имеет место и для ф(х). Так как (82) содержит O(logx) членов, а для х^2 будет 0 (х) < х log х, 0 (х1^) <^ xlir log х ^ х1'2 log х для г ^2, то имеем:

1

ф (х) = 0 (х) + О (х2 log2 х) = 0 (х) 4" ° U) = О кхУ (83)

Отсюда следует, что отношения ф (х)/х и ^Цх^х для х—► оо или оба стремятся к общему пределу, или оба не имеют предела. Теорема 3 эквивалентна тому факту, что этот предел существует и равен 1. Именно имеет место

Теорема 29. d (х) ^ п (х) log х.

Доказательство. Имеем:

тг (х) log х ^ д (х) Ss 2 1о£ ^ X1 ~ S) log х {п (х) — п (Х% где сумма 2' распространена по всем р, для которых х^-^^р^х, 0<6<Ч. Отсюда с помощью теоремы 28 вытекает неравенство.

тс (х) log хх(х)С21

Положим S = 1/log log х, тогда х^—> оо при х—> оо, что и доказывает теорему 29.

Таким образом, соотношения 9 (х) ^ х, ф (х) ^- х, n(x)logx^-x равнозначны. Из определения У(х) и ф(х) получаются также следующие другие формулировки теоремы 3:

Р1Рг-• -P^w еп+°<п> или lim ^рхрг. . .ря(„) = е, п-*ао

{1,2, 3,..., л} еп +° (")или lim ^{1,2,.. ., л} = е. н-юо

Из теоремы 29 без асимптотического закона распределе- 1

ния простых чисел вытекает, что ^рхр2.. .Pk^))7^ ^ л1-^1) (среднее геометрическое).

Биномиальный коэффициент (^) может дать нам сведения о простых числах в интервале п<^р ^Sn, так как вследствие ^р > 2л он содержит каждое из этих простых чисел точно в первой степени. Докажем прежде всего с помощью полной индукции неравенство

(2л)! _ л! л!(2л)! _ л! л!4"2 У л4"2 У л(л>1).(л>1).(84)(84)

(2л)! _ л! л!

(2л)! _ л! л!

4"

2 У л

4"

2 У л

(л>1).

(л>1).

(84)

(84)

Из предположения о справедливости (84) для всех натуральных чисел ^ л вследствие (2л -ф- 1 )2 > 4л (л -ф- 1) получаем:

2(л+1)А_9л-Н Z2(л+1)А_9л-Н Z2л + 1л + 12л + 1л + 1

2(л+1)А_9л-Н Z

2(л+1)А_9л-Н Z

2л + 1л + 1

2л + 1л + 1

что и доказывает (84) для всех п^Х. В дальнейшем нам понадобится и сама по себе интересная

Теорема 30.

П Р<ЛX

Доказательство1). Мы можем считать х целым. Для х = 2 теорема справедлива; предположим, что она верна для всех х ^ п — 1. Если п — четное, то теорема верна для х = п, так как п—не простое число. Пусть теперь n = 2k-^-\. Все р, для которых к-\-2^р^2к-\-\, являются делителями ^2^^"^» Этот биномиальный коэффициент <4А, что видно из неравенства

(14- i)sA+i(14- i)sA+iСТЖЛ'НГИ-СТЖЛ'НГИ-

(14- i)sA+i

(14- i)sA+i

СТЖЛ'НГИ-

СТЖЛ'НГИ-

Отсюда и из предположения индукции

П Р^Р^Ч П p<4A-4A+I=42A+1, ^2^ + 1X/р^к-^1

что и доказывает теорему. По Россеру [21] более точно Пр<2,83 далее Пр>2* для х>29.

^^ Xр^Х

Рассмотрим теперь каноническое разложение (2/г)!/тг!л! = = Пр^р- Так как по (2) р входит в п\ с показателем \гЦрЛ Н" \_п1рЧ 4“ • • •, имеем:

Г2«1— четное, LPZ—т нечетное.Lpz JГ2«1— четное, LPZ—т нечетное.Lpz J0, если1, еслиV0, если1, еслиVЕсли n = qpl -\-r, 0^г<р,1 то

Г2«1

— четное, LPZ

—т нечетное.

Lpz J

Г2«1

— четное, LPZ

—т нечетное.

Lpz J

0, если

1, если

V

0, если

1, если

V

2^' 2 /г "2г" pl J VP1 J LPl _

Таким образом, ер равно количеству нечетных чисел в обрывающейся последовательности [2«/р], [2п/р2],.. .Теперь мы можем сделать следующие утверждения:

Для р ^ У2п будет ^ ^ 1. Для р2 = 2я, где р = 2 = л, это ясно. Для р2^>2п в (85) отличаться от нуля может не более чем одна круглая скобка.

Для ра ^ 2п < ра +1 будет ер^т, так как в (85) отличны от нуля не более а круглых скобок. Таким образом, рер ^2п и(2пу

Для 2п\^ <^р ^ п и п^>2 будет ^ = 0. Так как 2п]р<^31 то для нечетного [2zz/p] следует рассмотреть лишь случай 1 < 2п]р < 2, а это означает, что р^> п. В этом случае р должно быть нечетным, так как из р = 2 следовало бы лг <2 3, тогда как по предположению л >2.

Для п<^р <^2п всегда е =1, так как 1 < 2п[р <^ 2.

39. Теорема Чебышева. В 1852 г. Чебышев доказал, что для любого л^1 среди чисел лг —|— 1, П-У2,..., 2п встречается по крайней мере одно простое число. Таким образом, имеет место

Теорема 31. п(2/г) — п(/г)^1 для /г^1.

Доказательство1). Достаточно показать, что произведение Рп всех р из интервала п < р ^ 2п не является пустым, т. е. >1- Положим ^^=QnPn1 тогда по § 38 (с) в Qn не входят простые множители р'>2п^. Произведение всех различных p\Qn не превосходит, таким образом, произведения всех р ^ 2п[3, следовательно, по теореме 30 оно <'42п/31 []0 § 38 (а) неравенство ер^> 1 возможно лишь для р<^У*2/г1 а число таких р будет ^; (|/*2/г)/2 = l/zz/2. Произведение соответственных степеней рер по § 38 (Ь) будет ^(2/z)^/2. Таким образом, Qn 42п/3 ^2пУп12, где р с показателем е >1, в правой части учитываются с показателями ер -|- 1 вместо ер — 1.

Учитывая (84), получаем теперь

4й 143

Qn(86)

2 V п 2V п <2п\ п

Возведя дробь, дим, что Р„>1,Возведя дробь, дим, что Р„>1,стоящую в правой части, в квадрат, уви- как только 42и 3 )> 2 ^л)^2"-^ Положим

Возведя дробь, дим, что Р„>1,

Возведя дробь, дим, что Р„>1,

Zn — x2, тогда должно быть 4х2 3 > 2х2 С^ + О. Это верно для х=12. Легко убедиться в том, что производная логарифма левой части для х ^ 7 больше производной логарифма правой части, так как для х ^ 7 будет 0,667 х log 2 > 1 -|- х~1 -|- log х. Таким образом, р„>1 для всех /z = 0,5х2 ^ 72. Если р— наибольшее простое число интервала а <^р ^2а, то теорема 31 очевидно верна для а^п^р — 1. Таким образом, достаточно простых чисел 2, 3, 5, 7, 13, 23, 43, 83, чтобы обеспечить справедливость теоремы 31 для n<^lZ.

Финслер получил таким методом значительно лучшую оценку для п (2/z)— n(/z). Обозначим дробь, стоящую в правой части (86), через (2/z)x, так что Рл>(2я)х, тогда x<^n(2/z)— п(/г), так как по определению Рп не содержит квадратов. Легко убедиться в том, что для п 2500

xlog2«=" flog4-^^-^^V — .

S 3 \ 6 Zn v Zn 1 ъ

Из таблиц простых чисел видно, что n(2/z)— n(/z)^2, 3,9, 25, 50, 100, если /z^6, 9, 36, 135, 321, 720. Так как n/31og2/z<l, 3, 9, 25, 50, 100 для п <8, 39, 150, 500, 1000, 2500, то вообще n(2/z)— п (/z) > х^> п/3 log Zn.

Для того чтобы получить оценку сверху, используем неравенство ^^ <14". Оно вытекает из равенства (1 —|—1)2" = = 2 С^- Отсюда

[п (2я) — тт (я)] log п ^ 2 1о£ р = n^p^ln

= og log — <С п log 4 <7 — •

Таким образом доказана принадлежащая Финслеру Теорема 32.

п3 log 2/2п3 log 2/2<п(2я) — п (/z)<п(2я) — п (/z)7/25 log п7/25 log п(ZZ>1).(ZZ>1).

п

3 log 2/2

п

3 log 2/2

<п(2я) — п (/z)

<п(2я) — п (/z)

7/2

5 log п

7/2

5 log п

(ZZ>1).

(ZZ>1).

Числовые значения для постоянных С2] и С22 теоремы 28. Из § 38 (Ь) следует, что если log(2/z)I взять за верхнюю, a log п\ за нижнюю интегральную сумму соответ-

ствующего интеграла, то

п (2л) log 2л log (2л)! — 2 log л! =

2«п4" + 1

= У log k — 2 У log к > \ log х dx — 2 \ logx dx =

= 2л log 2л — 2 (л -|- 1) log (л -|- 1) 4- 4 log 2 — 1,

>^ i _logj_ /1 +±\/, П

2л / ь п Х'л/^Х'л/*

4 log 2 + 1

2л

Для л ^200 правая часть ^2/3. Если в левой части заменить 2л на 2л — 1, то неравенство сохранится, так как левая часть увеличится, поскольку и (2л) = и (2л—1). Как показывает непосредственная проверка для х = р—1 000, имеем С21 = 2/3 для всех х^>\.

Следующие вспомогательные вычисления способствуют получению хорошего значения для С22. Если а >1,4— вещественная постоянная и х 2^, где

5а+7

5а -7’

то имеем:то имеем:(87)(87)

то имеем:

то имеем:

(87)

(87)

Предположим теперь, что оценка п (х) <>х/х log х справедлива для x<^2s+\ следовательно, в частности, и для интервала "2s ^х ^Y^^. Из теоремы 32 и (87) теперь следует

и (2х) = п (2х) — п (х) 4"л (^)и (2х) = п (2х) — п (х) 4"л (^)2хlog 2х ’2хlog 2х ’/ 7 .\ х .

и (2х) = п (2х) — п (х) 4"л (^)

и (2х) = п (2х) — п (х) 4"л (^)

2х

log 2х ’

2х

log 2х ’

<4 (—г & ) 1—

\ 5 1/ log X

интервала Для дока- что дляинтервала Для дока- что длят. е. оценка с постоянной а имеет место и для У^1 ^х <^2s^a и, следовательно, вообще верна, зательства неравенства для х<2,У+1 заметим, xt<x<x2 из n(x2)<ax1/logx1 следует

интервала Для дока- что для

интервала Для дока- что для

п(х)

п(х2)

аХ]10gXi

ахlogx"

Положим теперь а = 8/5, так что s=15. Так как 30 000 < < 215 < 216 < 70 000, приводимая таблица показывает справедливость оценки для 215^х<216. Продолжением таблицы1) оценка легко проверяется для всех х<^216, так что для всех х^1 постоянная С22=1,6.

X

л(х)

1,6 x/log X

70 000

6 935

10041

50 000

5133

7 395

40 000

4 203

6 043

30 000

3 245

4 657

Очень хорошую численную оценку несколько другого рода указал Россер [21]. Для х^55 имеем:

хbgx + 2хbgx + 2<п(х)<п(х)Xlog х — 4 *Xlog х — 4 *

х

bgx + 2

х

bgx + 2

<п(х)

<п(х)

Xlog х — 4 *

Xlog х — 4 *

4L Логарифмическое свойство л(х). Согласно Ишикава [11] имеет место

Теорема 33. л(х_у)>л(х)-4л(у) для ^^2, х^б,

х^у\ Доказательство, а) Пусть 2^j/<40, х^57, так

что л (j/) ^4.

Из теоремы 32 теперь вытекает

п ^ 5= п (2х) = л (2х) — л (х) + л (х) > л (х) + 3-jog2-

^ л (х) + 4 ^ л (х) -]- л(у).

б) Для j/^10 воспользуемся теоремой 28 с С21 = 2/3 и С22 = 8/5. Получаем:

, х , х 2ху 8х 20х 8х

Л 3 logxy 5 1ogx^31ogx2 51ogx

26 х 8у , х

15 log х 5 log у Л

Для 6^х<57 теорему 33 можно проверить непосредственно, рассматривая простые значения х и у.

Утверждения о л-м простом числе рп • Эквивалентной теореме 3 будет

Теорема 34. р,^ пХо^п.

Доказательство. Положим j = п (х), тогда из теоремы 3 при х —> оо следует log j/ -|“ 1°£ 1°S х —log х —* $, следовательно, (log_y)/(log х)—>1 и

У logy _У loglogy ]

XX log X *

Для х = рп будет л (ри) = п, и мы получаем, что п log п ^ рп. Вывод теоремы 3 из теоремы 34 мы оставляем читателю. Сверх теоремы 34 известно, что для любого п (Россер [20])

л log л < р„ < я (log л + [14-0(1)] log log л).

Обе следующие теоремы принадлежат Ишикава:

Теорема 35. Р„ + рп+1>Рп+2 для п>\.

Доказательство. По теореме 32 для рп^7 между Рп н РпА" Рп+х^^Рп лежат по крайней мере два простых числа рп+1 и рп+2. Так как З-^З^? и 5 -j-7 >11, то теорема верна вообще.

Теорема 36. р„рп>рт+п.

Доказательство. Пусть т ^п.

7^=1^ 2, 3; «^2. Из теоремы 35 следует

Р\Рп^Рп > Рп-1 "4“ Рп > Рп +

P,Pn = '&Pn> Рп-хА- РпА" Рп^ Рп +. + Рп> Рп+а-

Использовав теорему 31, получаем далее

РаРп^Рп > Рп - 1 Ч~ ^Рп ^ Рп + 1 “F ^Рп >" Рп+2 ”Н

“F ^Рп > Рп + 2 Ч- Рп +1 >" Рп + г*

т ^ 4. Теорема 33 приводит к неравенству

л U>mPA > л (Р J + л (Рп) = /Я + Я = П (рт+„),

следовательно, РтРп^ Рт+т ч- т- Д- Из теоремы 36 получаем неравенство

П РкРп + х-к>РПп + Ь

которая приводит к оценке)

рп+1<1 Й4 •(88)

Формула (88) дает возможность доказать следующее утверждение: если постоянное г ^ 1 и п^ р^Хлу то среди ср (zz) чисел ^zz и взаимно простых с п существует по крайней мере одна степень простого р^ь Если бы п делилось на pv р^..., Р2г+2 и Уже рУ+з ^ я, то имели бы — в противоречии с (88) —• неравенство рхр2.. .р2Г+2 ^ п ^ рУ^ Для г=1 должно быть п ^ 49. Известно, что 30 является последним числом zzz, которое обладает тем свойством, что все числа, взаимно простые с т и меньшие пц являются простыми.

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

ni = n — л (zz + zz, + ... + zz^J V^— L 2,...).

Очевидно, п ^ пх ^ zz2 ^. .. Так как

П1 — ni^ = Tt (« + «1 + • • • + ”,) —

то все zzz^O, так что всегда п^ тЦп-^ пх-^ . ..-^ М;_ху Так как правая часть возрастает, то должно встретиться пг = 6, чем процесс и будет прерван. Тогда рп = п + пх + ... -Ynr_v Пример.

Л2 = 8,я4 = 8 — Л (17) = 1,

^ = 8 —л (8) = 4, zz5 = 8 — л(18)=1, л2 = 8—л (12) = 3, zz6 = 8 — л(19) = 0, zzs = 8 — л (15) = 2, р8 = 8 + 4 + 34-24-14-1^ 19.

Разность между двумя последовательными простыми числами. Значительная нерегулярность в распределении простых чисел проявляется в поведении разности dn = pn+x—рп) которая была предметом многочисленных исследований).

Теорема 40 особенно ясно показывает, что dn не ограничено. Известно даже, что верхняя грань для dnl\ogpn бесконечна. С другой стороны, существует предположение, что^й = 2для бесконечного множества п (существование бесконечного множества пар простых близнецов). Это означало бы, что dn постоянно колеблется между 2 и сколь угодно большими значениями.

Эрдёш и Туран доказали, что нет такого места, начиная с которого dn монотонно возрастало бы или убывало.

Для достаточно больших п по Ингаму dn<^p^. По- линьяк высказал предположение, что среди чисел d^ d3,.. . каждое четное число встречается бесконечно часто. Прахару недавно удалось показать с помощью метода решета Бруна, что множество различных dn по меньшей мере имеет положительную плотность).

Дзета-функция Римана ^^^ обоими представлениями

C(s) = 2 n"s= П (1 — Р"Т\ $ = » + «(89)

И=1Р

определена как аналитическая, регулярная для а>1. Представление бесконечным произведением в (89) является аналитическим эквивалентом теоремы 1; оно показывает, что ^(б') тесно связана с распределением простых чисел. Мы можем легко установить зависимость между С (s) и п(х). Для а^>1 из (89), (63) и теоремы 27 следует

iog:(s)=—2iog(i —р"^=

р

СО

— — 2 {тг(л) —п(га—1)} log(1= п = 2

ОО

= 2 M«){log(l——log[l—(«+1)"*]}=:

со"+1СО

хС sdxС тс (х)

Л (/Z)\\dx.

х ' J х(х5— 1)1)

n—‘ln2

Дзета-функция, определенная до сих пор лишь в полуплоскости о> 1, допускает продолжение на всю комплексную плоскость и оказывается регулярной для всех s, кроме s = 1, где она имеет простой полюс с вычетом 1. ^^ удовлетворяет функциональному уравнению

C(s) = 2^-’ sin^Г(1 —s)C(l — s)').(90)

Особый интерес представляют нули функции £ (s). Так как произведение в (89) сходится, то ^(5)^0 для о>1. Из уравнения (90) следует, что ;(s)^0 для а <^ 1, за исключением точек $ =— 2, —4, —6,..., где sinns/2 обращается в нуль, а Г(1—s)— нет. Таким образом, все нули £(s), кроме «тривиальных» —2, —4, . .., лежат в полосе 0 ^ а ^ 1. Все нетривиальные нули р являются комплексными числами и их бесконечно много. Вследствие (90) вместе с р = а —|—Zp нулями являются также 1—ри 1—р=1— — а —|—/р, так что или все р лежат на прямой о =1/2, или расположены парами симметрично относительно этой прямой. Риман предположил, что имеет место лишь первая возможность, т. е. что всегда а =1/2. Эта знаменитая гипотеза до сих пор не доказана и не опровергнута. Все же, непосредственным вычислением можно показать, что все р, ординаты которых по модулю ^ 1468, действительно лежат на о =1/2. Если No (Т) означает количество р = 1 /2 —|— /т, для которых 0 <^т^ 7, то No > С80 Г log Т. Этот результат, полученный недавно А. Сельбергом, показывает, что на прямой о=1/2 лежит конечная часть р, так как известно, что количество всех р, удовлетворяющих условию 0 < т ^ 7, 0 ^ о ^ 1, асимптотически равно (2п)-1 Т log Т.

Для теории чисел важно как можно больше расширить область, не содержащую нулей £(s). Адамар и Валле — Пуссен доказали в 1896 г., что ^^ не имеет нулей на прямой о=1, а значит, вследствие (90) и на прямой о = 0, и пока-

9 Гамма-функция Г (s) определяется разложением

Она везде регулярна, кроме точек *9 = 0, — 1, — 2, . . . , в которых

имеет простые полюсы.

зали, что это утверждение эквивалентно асимптотическому закону распределения простых чисел. Формула

11= П(1 —Р-> = Х^’= П(1 —Р-> = Х^’

1

1

= П(1 —Р-> = Х^’

= П(1 —Р-> = Х^’

справедливая для о>1, верна, таким образом, еще и для 5=1, и вытекающее отсюда соотношение 2М^)/я = 0, справедливость которого предположил еще в 1748 г. Эйлер, оказывается равнозначным асимптотическому закону распределения простых чисел.

Риман указал интересную зависимость между п (х) и комплексными нулями £ (s). Пусть

/(Х)—п(х) + у п(*2) 4-jn(x3) -|-. • • =

—Е-М^У (91)

п=Л'

Пример.

/(12)=п(12) + 1п(К12) + 1п(УТ2) =

=5+1.2+-l.i==6y.

/(х) получается, если к л (х) прибавить половину числа тех р, для которых р2 ^ х, одну треть тех р, для которых р3 ^ х, и т. д. Если x1/7z^2, х1 (^+0 <2, то (91) содержит т членов, отличных от нуля, так. как т ^ (log x)/(log 2). Каждый член, очевидно, не больше предыдущего и так как и (х) = O(x/logx), то

/(х) —п(х) = |п/(х) —п(х) = |п

/(х) —п(х) = |п

/(х) —п(х) = |п

Таким образом, при замене п(х) на /(х) допускается относительная ошибка О (11 gx) = о (1). Впрочем, (91) допускает

обращение. Положив и = тп с помощью (18), получаем:

со!

и = 1 т\ах

Если положить теперь /0(х)—/(х) для х^рг(г^1) и /о(х)=/(х)— 1г для х=рг (среднее значение в точках скачкообразного разрыва /(х)), то имеет место формула Римана, доказанная в 1895 г. фон Мангольдтом !),

/ (х) = 11 х — У iх'*°& ^ (х >> 1).

1 J (м2 — 1) u log и 6\)

Здесь Их — интегральный логарифм, определенный для вещественных х равенством

* J l°gy log х** J l°gy log х*

* J l°gy log х*

* J l°gy log х*

Сумма, распространенная на комплексные нули, расположена по возрастающим ординатам р.

Интегрированием по частям находим:

УхX

।С du* Сdu

Их О ( 1 )-Г- ]\,9Н \1 2—<С

v 71 log X1Jlog2 и1 Jlog2 и

2Vx

/1 \ ।-^। V2 । x J^x

1 ;TUgx ‘ log2 2‘ iog2 y-^—

r4-+ ° (1) + о (/^) + о f r4-

log X 1 I О / I \l°g x/

(92)(92)— ——ю( x 'I

(92)

(92)

logx 1 \log2X/ *

Отсюда вытекает, что И х x/log х л (х). Помещенная ниже таблица показывает, как можно было ожидать вследствие формулы Римана, что lix дает лучшее приближение к п(х), чем x/logx. Порядок роста разности Р(х) = л(х)— lix обстоятельно изучался.

Если 6 является верхним пределом вещественной части р, следовательно 0,5 ^6<1, то Р(х) = О (хб logx).

Точность приближения л (х) функцией lix, таким образом, существенно зависит от расположения р. Из справедливости гипотезы Римана следовало бы, таким образом, Р(х) = = О (х1'2 log х). Это — очень сильная оценка, так как известно, что равенство Р(х) = О(ха) для а <0,5 не может быть справедливым.

Хотя в пределах таблиц Р^ все время остается отрицательной, знак этой величины должен бесконечно много раз изменяться. Этот факт установлен Литтльвудом независимо от того, справедлива или нет гипотеза Римана. Правда, не известно такое х0, что Р^х^^>^. Принимая гипотезу Римана, Скевес вывел, что существует х0, меньшее

X

7Г (х)

П х

i: (х) И х

Т (х) x/logx

1000

168

178

0,94

1,159

10 000

1 226

1246

0,98

1,132

50 000

5133

5 167

0,993

1,111

100 000

9 592

9 630

0,996

1,104

500 000

41 538

41 606

0,9983

1,090

1 000 000

78 498

78 628

0,9983

1,084

2 000 000

148 933

149 055

0,9991

1,080

5 000 000

348 513

348 638

0,9996

1,075

10 000 000

664 579

664 918

0,9994

1,071

20 000 000

1 270 607

1 270 905

0,9997

1,068

90 000 000

5 216 954

5 217810

0,99983

1,062

100 000 000

5 761 455

5 762 209

0,99986

1,061

1 000 000 000

50 847 478

50 849 235

0,99996

1,053

VII. ЭЛЕМЕНТАРНОЕ ДОКАЗАТЕЛЬСТВОАСИМПТОТИЧЕСКОГО ЗАКОНА РАСПРЕДЕЛЕНИЯПРОСТЫХ ЧИСЕЛ

Формула Сельберга. Основой всех элементарных доказательств является формула А. Сельберга, которую, следуя Исеки и Татузава [10], мы докажем в следующей форме.

Теорема 37.

ф (х) log х 4- ^ ф f ^\ А (л) = 2х log х -]- О ^х\ (93) п^х х 7

Доказательство. Прежде всего мы покажем, что если F(x) и G^ определены для х^ 1 и G(x) = 2 F^х\т^\о^х, т^х

ТО

/r(x)logx+ 52 f 4) M«) = 52^) G ("j) • (94)

п^х хd^xХ 7

Вследствие (18) и (22) имеем:

F^ log^+ 52 л 4) А(и) =

= 52 4^)1о^52ит52 4 4£иШо&^=

п^х х 7а\пп^х х d\n

п^хй\пп^хd\n

Изменив порядок суммирования, получим, что последняя двойная сумма равна

Ем^Ег(^>^=5>иа(^).

d^xх х 'd^xх '

т^—

Положим в (94), во-первых, F = Fx^=^^x\ тогда из (21) и (54), положив mn = k, получим:

Ох^= 52т(^-) logx = logx 52А(й) = т^х хтп^.х

= log X 51 Уl^^.n^ = log X 2 log к =к^х п\кк ^х

= X log2*X log X -]- О (log2 х\

Теперь положим F=F2^ = x— С3—1, где С3— постоянная формулы (52). Тогда с помощью (52) получаем:

G2 (х) = log х £ {^ — С, — 1} =

= х log2 х 4“ С3 х log х 4- О (log х) — (С3 -|- 1) х log х = = X log2 XX log X 4" О (log xY

Так как О (log х) = О (log2 х) = O(V^x), то О, и О2 будут равны, если в обоих случаях поставить остаточный член О^х). Теперь

1>Wo(/5-)=°(4 /4-о(Кх$4)=О(х), d^x\d^x /\ о /

так что теперь для /71 и Л2 правые части в (94) совпадают до величин O^xY Это должно иметь место и для левых частей. Для Fx левая часть совпадает с левой частью формулы (93). Таким образом, нужно вычислить левую часть (94), для F2. Из (61) и (83) получаем:

(x-C8-l)logx+£{^-C3-l} Х^ =

=2х log х — (С3 4~ 4 [logx 4- ф W] + О (х) = 2х log х 4- О(х).

Теорема 37 доказана.

Применение формулы Сельберга. Мы будем пользоваться (93) с несколько худшим остаточным членом O(xlogx)1). Асимптотический закон будем доказывать в форме ф(х)^х. Положим (b(x)=x4™^4)i тогда нужно будет показать, что А?(х) = о(х). Из (61) и (93) следует

/?(х) logx+ 52 ^4) -М«) = о ^ logx). (95) п^х '

Вычтем из обеих частей (95) 5 ^ W^) ^ W и возьмем затем абсолютные величины, тогда

|/?(x)|logx< 52 I r(^ I А (л) + о (х log х).(96)

п^х X ✓ I

*) В доказательстве Сельберга применяется О(х) (см. Сельберг [22]).

В первую очередь мы так преобразуем (96), чтобы исчезли множители А (/г).

Напишем (93) в форме

Т, А (т) А (п) = У, фТ, А (т) А (п) = У, фА (//) =А (//) =п^хп^х

Т, А (т) А (п) = У, ф

Т, А (т) А (п) = У, ф

А (//) =

А (//) =

п^х

п^х

= 2х log Xф (х) log X 4“ о (х log х),

тогда из (62) с учетом (64), (83), (55) и вытекающего из (92) соотношения

1log п1log пO(lix) = ofO(lix) = of

1log п

1log п

O(lix) = of

O(lix) = of

получаем:

£ 1§П^) = £<2А1о£6 —Ф<^х

тп^х 6А=2

У ‘' log(6 + D) + Р* loS * — Ф И log 1 + о (х log х)]Х

Хк^+Т)=2»—№ + «№■ РП

Использовав получающееся из (97) выражение для ф (х), получаем далее:

= 2хУ ^-У А(н) У ^ДИ п *^ 1 log тг

п^хп^х_ X

тг^—п

Изменив порядок суммирования в двойной сумме, получим вследствие (61)

У W(«) + ^ WW2L) =х ' а / ।\oomr J

mn^xmr^x °х z

= 2х log х-[“ о (х log х) ’).

Это равенство позволяет записать (93) в виде

№logx= £ пЙ^ф(^)+°(х1о^А (98)mr ^х s47

Из (68) и (98) получаем:

/?(x)logx = У^ —:r(—4~o(xlogx). (99)

\log тг\тг) х х 6 ' х ’

тг^х Ь

Возьмем в (99) абсолютные величины и сложим с (96), тогда будетВозьмем в (99) абсолютные величины и сложим с (96), тогда будет2|/?(x)|10gx^ £ |/?М|л(/0+ £п ^.х47тг^х2|/?(x)|10gx^ £ |/?М|л(/0+ £п ^.х47тг^хА (т) А (г)log тгА (т) А (г)log тг\r(—)|+\r(—)|+-[“ о (х log х).-[“ о (х log х).

Возьмем в (99) абсолютные величины и сложим с (96), тогда будет

Возьмем в (99) абсолютные величины и сложим с (96), тогда будет

2|/?(x)|10gx^ £ |/?М|л(/0+ £

п ^.х47тг^х

2|/?(x)|10gx^ £ |/?М|л(/0+ £

п ^.х47тг^х

А (т) А (г)log тг

А (т) А (г)log тг

\r(—)|+

\r(—)|+

-[“ о (х log х).

-[“ о (х log х).

С помощью частного суммирования, учитывая, что последний член в (62) вследствие (83), (97) и неравенства R [хДхЦ- 1)] | < 1 входит в остаточный член, получаем:

2^W|logx«;£ /£аи+ £ T^lX

к ^ х | п ^ кmr^k 6)

X {1/?(^)|—кС^тт) ,}+0<'10^')

или вследствие (97)

2| /?W|logx^2 ^^ { | ^(^) | —| ^(д^л) | } +

+»(£^ {к(т)|-|/?(т)1 B+o^iogx). (юо)

При этом вследствие (63)

ЕЧ|«(|)Н«(^)|}=

— у I p(L\ l — Frll р(—хI —

4<х' ^/' I \1х1 + |/1

= Е ^(т)^0^!0^^- (101)

Вследствие (83) /?(х) = 0(х), так что из (101) и (52) на основании примечания на стр. 82 следует, что первый о- член

в (100) также имеет порядок o(xlogx). Из (100) и (101) получаем теперь важное неравенство

(Ю2)(Ю2)

(Ю2)

(Ю2)

С помощью (102) мы докажем, что для каждого (сколь угодно малого) г > 0 существует такое Zj = Tj (s), что | /? (х) | < sx для всех х>т^. Это, очевидно, эквивалентно утверждению /?(х) = о (х).

Лемма А. Для z "> z имеем | R (z) — /? (/) | ^ z*— — г + »(г').

Доказательство. Так как ф(/) — ф (г) = У — z-f- -\-R^z)— R^^O, то при R^z'^ — ^(^ХО утверждение теоремы очевидно. В противном случае, положив в (97) х =/, x = z, после вычитания получим:

Так как сумма неотрицательна, то лемма А верна и в этом случае.

Лемма В. Если 6<1—произвольное фиксированное положительное число. то существуют такое р (8) > 1 и такое х0 = х0(8), что для любого х^>х^ в промежутке (х, рх) найдется такая точка у. для которой | R (у) | < Йу.

Доказательство. Из (83), (65) и (58) следует

L ®= Е ^ + O('L‘4log’^ = logz+O(.) k^xk^x\к^х/

или вследствие (52)

где 0(1) ограничено для любого конечного х. Отсюда вытекает существование такой абсолютной постоянной Kv > 0, что

для всех х > 4 и р > 1

ER№ER№х ^к^рхх ^к^рх

ER№

ER№

х ^к^рх

х ^к^рх

Действительно, если бы такой отрезок ряда мог принимать сколь угодно большие значения, то то же самое (с противо-

положным знаком) имело бы место и для суммы по k от 1 до х, тогда как известно, что эта сумма ограничена.

Если R^ не изменяет знак между х и рх, то в интервале х ^у ^^х существует такое у, что

у Я№/г2у Я№/г2

у Я№

/г2

у Я№

/г2

так что вследствие (52) при соответствующей постоянной

Кг ^ 1 будет

|/?(У)| / К.

Если же в промежутке (х, рх) R^ изменяет знак, то будем различать два случая:

RW = фСу) -.у > О, Riy +1)=Ф Су +1) - СУч-1 )<о. Если ф(у) = ф (у4~ 1), то /?(у)<1 и R(y)j У<Щ У- То же самое имеет место для ф (у 4~ 1) > ф (у), так как из ф (у -|- 1) = ф (у) -р log р <^у 4" 1 снова следует, что R (у) < 1 (и Р = ^.

RW^^ ^Су4-1)>°? так что у 4" 1— Рг- Из того, что JR (у 4" 1) = ФСу)4"г‘"1 log О'+ !)— У— 1 = Ш + 4" г 1 ^Я ^ + 1) — 1 > 0, и из условия R (у)<С 0 следует неравенство

I ^(^Х^Су+В1 / log(y + l)-l

I У Iг уу у *

к2

Положим теперь р = р(8) = е5 и выберем х0 = х0 (8) > 8 столь большим, чтобы было 1 < log (х04- 1)—1 ^ 8х0. Таким образом, во всех случаях лемма В доказана.

Лемма С. Если х^хх (8)^х0(8), то в интервале {х, рх) содержится такой частичный интервал у ^ z ^ е^у. что для любого z из него будет |/?(^)X38z.

Доказательство. Из оценки леммы А следует

|/?(г)| = |ад-А>Су) + ЯО')|<:

Выберем на основании леммы В такое у, чтобы было |/?(у)|<6у. Пусть теперь х1=х1(8) будет столь большим, что, во-первых, хх ^ х0 (8) и, во-вторых, чтобы было

0 к2) < 0,58^0,58^ 2у.

Тогда вследствие неравенства ^<^ 1-j-s-b^2 (^—$) ^ $<С1 имеем:

^I^I^I^SJL^ _! । 0,5^2 <2й4-к-^< 35

г I I jv I11 2 — о

ч. т. д.

Доказательство асимптотического закона. На основании леммы С мы получаем теперь для постоянного ха ^ хх (6) последовательность (зависящую от 5) интервалов

5

x2pz~1 <Л1 ^ х ^у/1^ х^1 < х, (1 ^ Z ^ /), (ЮЗ)

где

t= [(log?)-1 log (^)J = [г^-1 log (У].

Положим z = x)n, где х— постоянное и п—целое, тогда из (103) получаем соответствующую последовательность интерва

лов для п\

8

(Ю4)(Ю4)XоXX _ / .к jX

(Ю4)

(Ю4)

У/У/Х2 “Х2

(1 < i^O-

Формула О03) осуществляет разбиение как на «широкие» интервалы [x2pz“\ x2pz], так и на «узкие», когда выделяются еще и малые интервалы (у, jz^/2). Из (82), (81), (80), теоремы 28 и § 40 для х^2 и 0<а<^1 получаем:

ах < 0 (х) ^ ф (х) ^ л (х) log х <^ 1,6х,

следовательно, |/?(х)|<<х. Таким образом, для х^х2 справедлива оценка | ^ (х) | <^ atx, где a ^ 1. Положим теперь d = 8i=a1/6. Тогда на малых интервалах получаем оценку

\R^\\R^\а^Т 'а^Т '

\R^\

\R^\

а^

Т '

а^

Т '

тогда как в общем случае было бы лишь | R ^ | < а^. Теперь напишем (102) в форме

I^W |^г^- У -|-r(-A I+oW. (105) 1' 71 log х ^ п х \ п /1 х '''

1=5-

Суммирование здесь производится по п, а х— это число из (103) и (104). Для интервала \^х\п<^хг, примыкающего слева к последовательности интервалов (103), число п лежит в интервале xjx^<^n^ х, примыкающем к интервалам (104) справа. В этом интервале мы воспользуемся лишь оценкой I я (г) I о

Для остальных интервалов мы можем использовать опенку Т^х'х") Н^01!* Теперь из (105) и (52) получаем неравенство

Irwi<e|i[i»^.+o(^)]4Irwi<e|i[i»^.+o(^)]4,^И+с.+,^И+с.+

Irwi<e|i[i»^.+o(^)]4

Irwi<e|i[i»^.+o(^)]4

,^И+с.+

,^И+с.+

+°(5) +°w=a^+»w- (1°6)

Это неравенство не даст какого-либо выигрыша для оценки | /? (х) |. Учтем, однако, что для малых интервалов j/z < z ^у^!2 справедлива оценка | R (z) | < 0,5 а^, тогда можно будет получить более точную оценку для |/?(х)|, если из правой части (106) вычесть лишнее. 2 Чп для z"r0 малого интервала в (104) имеет величину 8J2 -|- О (х2р/х). Поэтому из правой части (106) вычитаем величину

“Iх J ^ Si I П хг V И _ “1х }Л I

2 log X ( 2 “Г\ х .^ ^ у I — 2 log х Г 2 "Г"

"4" 0 W = 144^ "4" 0 W

и получаем неравенствои получаем неравенство|Я(х)|<а, (1|Я(х)|<а, (1a2 \144^/ х + <> W-a2 \144^/ х + <> W-

и получаем неравенство

и получаем неравенство

|Я(х)|<а, (1

|Я(х)|<а, (1

a2 \

144^/ х + <> W-

a2 \

144^/ х + <> W-

а2\1 —-^У х = а4х,а2\1 —-^У х = а4х,|Я(х)|<а,|Я(х)|<а,Теперь можно выбрать такое постоянное /^^ 144/<22> 144 и такое постоянное х8 > х2 ^ х, (8), чтобы для всех х>х3 было

а2\

1 —-^У х = а4х,

а2\

1 —-^У х = а4х,

|Я(х)|<а,

|Я(х)|<а,

причем аг<^ах^. 1. Положим теперь 82 = а2/6, тогда существует такое достаточно большое постоянное х4^х3, что для любого х>х4 имеет место разбиение на интервалы (103) и

при § = 52 и х4 вместо х2. Для х<^х4 используем оценку 17? (х) | < х, а для х х4 — оценку | R (х) | << а2 х. Как и раньше, теперь можно указать такое x6j>x4, что для всех х>х6 будет

|W)K«2 (1 ”1?-) х=аах.

a„+i = «»(1 — -^) <4 (п=1, 2,...)(107)a„+i = «»(1 — -^) <4 (п=1, 2,...)(107)Таким образом возможен процесс итерации. Положим ( а2 \

a„+i = «»(1 — -^) <4 (п=1, 2,...)(107)

a„+i = «»(1 — -^) <4 (п=1, 2,...)(107)

и построим для 5П разбиение на интервалы, тогда получим убывающую последовательность постоянных ^ чисел х2и+1 >х Л таких, что

I^WK^-H-V Для *>*2П + 1-

Из (107) ясно, что an стремится к нулю с ростом п. С помощью полной индукции можно показать, что ап < ]/ К^п. Подставим это в (107). Учитывая, что кубическая функция от ап в (107) убывает вместе с an, если аи < ]/?</3, из неравенств /г~^2(1 — 1/2/г) <^ (/:-{-1)~12 Для л ^1/3 и

4<VK\4 получаем неравенство

Теперь можно п выбрать столь большим, что будет ал<е. Теперь т^ — хгп_х позволяет получить неравенство, упомянутое в конце § 46, что и доказывает асимптотический закон распределения простых чисел.

VIII. ЭЛЕМЕНТАРНОЕ ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫОБ АРИФМЕТИЧЕСКОЙ ПРОГРЕССИИ

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

х) х2п должно быть постоянным, для того чтобы в (106) все члены, кроме апх, поглощались остаточным членом.

VIII]

которых p = a(modm). Следуя X. Н. Шапиро [25], нами будет доказана аналогичная теореме 22

Теорема 38.

21+(°- m) = 1-

р — a (mod т^

Так как правая часть бесконечно возрастает вместе с х, то из теоремы 38 тотчас следует теорема 4.

Роль характеров. Главной проблемой при доказательстве теоремы 38 является, очевидно, выделение простых чисел, принадлежащих тому же классу вычетов по mod т, что и а. Если мы хотим, чтобы сумма ^/^ была распространена лишь на простые числа р, входящие в этот класс, то нужно все слагаемые /(р) умножить на множитель, который обращается в нуль для р ^а (mod т^ а для р~а имеет значение 1. Этим свойством обладает вследствие (27) сумма характеров

VW^Z^ZW-

Z

Тем самым в первую очередь возникает задача оценки суммы вида 2 /Wl^PV В качестве подготовки к этому рассмотрим р ^ х

сперва соответствующие суммы, распространенные на все п ^ х.

Лемма 1. Если /(х) для достаточно больших х монотонно стремится к нулю при стремлении х к бесконечности, а ч не является главным характером ^ по mod/л, то

2 z(”)/(")=0[/^)]-

п > z

Доказательство. Так как ч^*^ то вследствие (24) имеем:

|SM|=I 2 Z(«)I<O(1).(108)

П ^ X

Учитывая (108) и то, что /(/z)—>0, получаем из (63)

2 lWW = 5 {S(n) — S(n— !)}/(«) = лгn^z

= 2sW{f(A)-/(HDH(^-i)/(z)=

k ^ z

=о( 2 W)-/(*+i)}) + o[(/(*))]=o[^

к ^ z

ч. т. д. Для /(х)=1/х, /(х) = х“1 log х, /(х) = х~12 ИЗ леммы 1 следует сходимость рядов

п-\И = 1п = 1 г Л

Далее, получаем оценки

ӣU5! = Z.,,(Z) + o(l),(109)

z'l^'-i.izi + o^).<И0)

п^х'

Е/^.щ+о^).он.

Лемма 2. Если х^Ъ—вещественный характер по mod т, то Lo (/) ^ 0.

Доказательство. Сумма F(n) = 2/W, распростра- d[n

ненная на все делители d числа п, как сумматорная функция для X (/z), является мультипликативной по § 13. Так как XW вполне мультипликативна, то для « = ПрГ имеем: ^(”)=П^(р.-‘)=П {1+z(Pi)+z2(p,)+- • •+z,?i (^,)}«

Так как у (pz) = -4- 11 то для всех п будет F(/z)^O и F V^^ 1 • Отсюда вытекает расходимость ряда G = ^F (п)^п, так как гармонический ряд является для него минорантой. Покажем теперь, что из равенства Ао(у) = О вытекала бы сходимость G.

Положим n = dd* и проведем суммирование по d и d', тогда

п^х ' п^х ' п d пdd' ^х ' d yd

Двойная сумма распространена на все пары натуральных чисел d, d*, для которых dd' ^ х. Эти пары соответствуют целым точкам, лежащим на гиперболе и под гиперболой dd* = х, причем точки, лежащие на оси абсцисс (dl = 0) и оси ординат (^7 = 0), исключаются. Разделим эту область на две части перпендикуляром d = )^х и будем суммировать

в левой части вдоль вертикалей, а в правой части — вдоль горизонталей. Это дает следующее разбиение суммы

d^VxV аd*<VxVad^VxV аd*<VxVa/х < d^^-/х < d^^-Х<£)Vd *Х<£)Vd *

d^VxV аd*<VxVa

d^VxV аd*<VxVa

/х < d^^-

/х < d^^-

Х<£)

Vd *

Х<£)

Vd *

Применив (53) для р =— 0,5, а также (111), получим;

Проведение суммирований с учетом (108), (109), (111) и (53) дает

G(x) = 2x2 £ ^4-О(1) = 2х2 ^o(Z) + O(x 2)) + d С Ух"

+ О(1) = 2х^£0(Х) + О(1).

Из равенства А0(Х) — 0 теперь получилось бы G(x) = O(l), что противоречит расходимости G. Лемма 2 доказана.

Следующая сумма характеров играет важную роль в нашем доказательстве. Она получится применением (20) к функции

gW = ^ Ц^=х £ ^- = хЛ0(х) + °(1) (Z^Z.)-

При Р(и) = у(и) и /(х) = х получаем:

*= X rWl (»>{■£ ^о (X) + ° <1 >} =

п ^ X или после деления на х

^o(Z)£^ = 0(l).(112)

п ^х

Равенство (112) справедливо для всех характеров XT^Zi* Для не вещественного у множитель Lo ^ может обращаться в нуль, а тогда (112) ничего не дает. В этом случае еще раз применим (20) при Р(п^ = ^^ и f^ = xlogxn вследствие (109), (ПО) и Z,o (х) = 0 получим:

g^ = S Z(«)^loS f = У ЧГ^2^

= x7ogx ^_x £11^ =

= Ц (Z) x\ogx — xL, to 4- О (log x) = = — xLx to 4-0 (log x).

Формула обращения дает теперь

xlogx= £ V-tolW { — ^l(Z)^ + ofl°g^)} =

= —=L, (Z)£ №l+0|x)]n ^ X

так как из (54) следует

I s ^wzw ° o°g ^) |<

<C40/xlogx— У log«l = 0 (x).(113)

'n ^ X1

Итак, если Ло(х) = О, то LXV^^9, так как в противном случае получилась бы невозможная оценка х log х — О (х). Теперь из равенства (112), учитывая, что Lo (/) и Lx (х) — конечные числа, для XT^Zi имеем:

L (у) У t^l^= /— logx+O(l), если £0 to = °. (Ц4) пех ")0(1), если L.to^O. '

Лемма 3. Для X=7^Zi справедливо равенство

р^хр^хХ(Р)1°8РРХ(Р)1°8РРO(i),если Loto 7^0, П15,— logх4-0(1), если Leto = °-O(i),если Loto 7^0, П15,— logх4-0(1), если Leto = °-

р^х

р^х

Х(Р)1°8РР

Х(Р)1°8РР

O(i),если Loto 7^0, П15,

— logх4-0(1), если Leto = °-

O(i),если Loto 7^0, П15,

— logх4-0(1), если Leto = °-

Доказательство. Из (53) для s^ 1 имеем:

0(1).0(1).^ xW^P_ ^ X^Hp o(i)__ y^ xW^L p^Xp^X Pn^X П

0(1).

0(1).

Из (22) теперь следует, если положить n = dcT и использовать (110) и (113), п^хп^х d\n

„ у xWliM log<Z'_ у »№1№ у x(^')log</'_ ^^'— jfci d ^ d'

dd*^хd^xd* ^ x,d

d^x\.

=£. (z)E ^^4-0(1).

Теперь отсюда и из (114) непосредственно вытекает утверждение леммы.

Отличие Lo (/) от нуля. Покажем теперь, что £о(^)^О для любого характера *^ = ^Х1 т. е. не только для вещественных /. Это центральное место в классическом доказательстве теоремы Дирихле. Если N означает количество Z^^, для которых Z,o(/) = O, то из (25), (26), теоремы 22 и (115) следует

Р^х/ р^Х

р = 1 (mod т)

= S !®+Е хги^о-л^+ои).

Р^ X Р Х^Тл Р^х Р

(Р, т)=1

Так как Q(x)^0, то O^N^l. Отсюда следует, что ^о (Х) ^ ^ также и для комплексных /. Действительно, если бы £0 (/) обращалось в нуль для комплексного ^ то это было бы и для комплексно-сопряженного характера z1), а тогда было бы N^^.

Окончание доказательства. Для всех / = /г имеем теперь по (115) 2/ Wp-1 \ogp = O (1). Из (27), теоремы 22 и конечности числа характеров следует, таким образом, для (а, т^=\ равенство

■к») Е ^=Е>(«> Е ‘-^

Р^х РIр^х Р

р = a (mod m)

= Е ^+Еад Е’-^-^+от.

р^х Р t^/л Р^х Р

чем и доказана теорема 38.

Дальнейшие результаты. Правая часть оценки в теореме 38 для всех классов вычетов а по mod т, взаимно простых с т, содержит один и тот же главный член, поэтому естественно предположить, что все такие классы вычетов содержат асимптотически равное количество простых чисел. Если па (х) обозначает количество р = а-\- кт ^ х, (a, zzz) = 1, то действительно

lim =

X -> ОО к W ? И

Это тотчас следует из «асимптотического закона» для арифметической прогрессии

ла(х) ^x^W logx]"1, который сегодня также может быть доказан «элементарно». Особенно интересен вопрос о наименьшем простом числе, входящем в класс вычетов, взаимно простой с т. Линник получил в этом направлении следующий важный результат: существует такая абсолютная постоянная С50, что для любого натурального т в каждом классе вычетов по mod т^ взаимно простом с т, имеется простое число р < тс^.

МЕТОД РЕШЕТА

Метод решета Бруна служит для «просеивания» чисел п ^ х арифметической прогрессии F с начальным членом а>0 и разностью tZ>0. «Решето» строится следующим образом: из последовательности простых чисел вычеркиваем конечное число членов, в том числе 2 и простые делители dw

Расположенные в порядке роста оставшиеся простые числа обозначим qv q^ q3, ... Пусть л' (_у) означает количество чисел q^^y. Каждому qt^y сопоставим две1) арифметические прогрессии At и В{ с начальными членами а( и Ь, и разностью ql, где 0 ^a(^qb 0 ^ b( ^ qb а{=^Ьь 2л' (у) последовательностей А( и В( используем теперь для просеивания, удалив из F те п, которые лежат в одной из последовательностей А. или Вь Оставшиеся п ^ х удовлетворяют, таким образом, условиям: п^а (mod dV п ^ а( (mod q^, п ^ bf (mod q^, af ^ ЬР Количество таких п обозначим символом N(d, х, у). Мы будем устанавливать лишь такие свойства N ^d, х, yY которые не зависят от выбора чисел a, ah bh так что эти аргументы не нужно вводить в обозначение функции. Цель метода решета — получить как можно лучшие оценки для N Vd, у).

Иллюстрацией служит следующий пример: а=1, d = <21 qA=3, q2 = S, qi — p.+i; а{ — 0 для всех I; Ь(~ х (mod q^ для х ^ 0 (mod q-Y но b( ^ х (mod q^, если х ~ 0 (mod q^. Если х—четное и и ^ 2— целое, то ^(2, х, х1'")— количество нечетных п ^ х, обладающих тем свойством, что ни гц ни х — п не делятся на простые числа ^xxiu.

Действительно, из х— п = 0 (mod q^ вытекает, что п ее Ь( (mod q^, если х ^ О (mod q^, и /г = 0 (mod q^, если х ее О (mod ^).

Таким образом, все простые делители п и х— п будут > х1/и, т. е. как гц так и х— п состоят не более чем из и—1 простых множителей. Из неравенства Л'(2, х, х1/2)^2 вытекало бы существование представления х = п-\-^х— /г), в котором п и х — п— простые числа, как предположил в 1742 г. Гольдбах (см. гл. X).

Алгебраическая рекуррентная формула. Разность N^d, х, qk_x^ — N^d, х, q^ равна, очевидно, количеству тех пц которые удовлетворяют следующим условиям:

т ^ х, т = a (mod d^ m~ak или = Ьк (mod q^,(т — а^т — b^ 0 (mod q^ (/=1, 2, . .. , к—1). (116)Так как ^d, ^)=1, то существуют целые и, v, для кото-

^ При решении некоторых задач достаточно сопоставлять q^ одну последовательность Af, можно, однако, строить также трех- или многократное решето. Здесь рассматривается лишь двойное решето.

рых ^4"^=^» а также целые и\ v', и", V', для которых а — ак = ud-^-Vq^ а — bk = u"d -f- v”qk. Положим теперь а — и d — ak-Yч)’qk = d, а — it'd= bk-^-i)”qk = а!\ тогда совокупность т, удовлетворяющих (116), совпадает с совокупностью т. для которых

т ^ х. т~а или = ci’ (mod dq^.

Кт— a^Vm — b^ ^ 0 (mod ^) (Z=l, 2, .... к — 1). (117)

Действительно, из сравнения т = ак (mod q^ следует: т—а’= т— a-^u'd = ^ (modtf), т— d = m—ак—Vq^O (mod qkY так что т ~а' (modtf^). Обратное утверждение получается так же.

Количество чисел т. удовлетворяющих (117), можно обозначить "IN^dq^ х. qk_xY Естественно, что слагаемые, соответствующие а’ и а”. не равны точно, однако они будут одинаково оцениваться, так что мы можем символически объединить эти члены. Таким образом, получаем рекуррентную формулу

N^d, х, q^ = Ntd, х, qk.^ — ^NViqk, х, qk_x\ (118)

Для k=\ пишем справа N^d, х)— 2N[dqk, х). где N^d. х) означает количество чисел п ^ х любой арифметической прогрессии с разностью d. При любом начальном члене имеем:

NKd, х)=у + &, |»|<1.(119)

С помощью (118) можно, очевидно, выразить N{d,x. q^ исключительно через слагаемые вида (119) и получить, таким образом, оценку, справедливую при всех а. а^ Ь(.

В первую очередь из (118) выводим равенство

N(d,x, q^ = NVd, х) — 2 2 ^Мп, х, qri_x). (120)

Если каждое слагаемое правой части снова выразить по формуле (120), то получим:

N\d, х, q^ = N(d,x) — 2 ^N(dqri, x) +

+ 4 2 2 N<dqrxqri, x, qr,_x\ (121)

Вообще для t^k имеем:

N^d, х, q^ = N{d,x) — <2^t N{dqr„ x} 4-

F^^

+ 4 5 5 М^гДгР X) —8 2 2 2 N<аЯг,ЯгДг„ x) + ...

FiS^F^F,Fl ^A F2<F1 F3 <F2

...+(-2),S... 2 Nkdqri...qrpx,qrt_tY (122) rx^k ri<rt_i

Для t = k с помощью (119) легко получаем из (122) к

N<d,x, q^ = ^ П(1-2»71)+^(123)

Развернув произведение, получим Зд членов, каждый из которых вносит в остаточный член R величину, не превосходящую по модулю 1. Таким образом, |/?|^3^.

Для оценки N^d.x.x1^ равенство (123) не пригодно.

Действительно, из теоремы 3 к = л ^xXiu^ ^ uxiul\ogx, а по теореме 25

П(1 —з^г1)--^,х' log2 X ’

так что R имеет больший порядок роста, чем главный член. Вигго Брун [3] показал, как можно так сократить число членов в (123), чтобы R оказалось меньшего порядка, чем главный член.

Введение чисел решета к^ Теперь должна быть выведена оценка сверху1) для N^d, х, q^. Положим в (122) / — Зи потребуем, чтобы, кроме условия r3 <V2, выполнялось еще неравенство гг^кх. Если в тройной сумме опустить некоторые члены, то правая часть увеличится. Если в получившемся, таким образом, неравенстве члены тройной суммы выразить с помощью (121), то получится в результате пятикратная сумма, из которой можно снова исключить несколько членов с помощью условия г6^к2. Таким образом, мы получим разложение, аналогичное разложению (122), которое оканчивается отрицательной (2s-[-1 )-кратной суммой, где должно быть 2s -|“ ^ <^к. Применим к этой сумме еще раз (118),

*) Для вывода оценки снизу требуются лишь незначительные изменения.

тогда в конце правой части неравенства окажется положительная (2s -]- 2)-кратная сумма. Ее можно еще увеличить, если символы N^dqri . . . qr2s+2l х, qm*2_x^ заменить символами N ^dqri.. . qrg+2l х\ Из (119) теперь получаем:

N^d.x, Чк><^ Е"У^

5=1-2(+++22 №)

...+(-1Г+2 2 • • • 2 (Вд • • • №^. (124)

Для индексов суммирования имеем:

8</V (125)8</V (125)гг^Х^ гг).^<к) (у = 0, 1, 2,.. ,,s),

8</V (125)

8</V (125)

К К^К^. . .^К^ 1, 1 <\'2^+2\Л2^+1^

Все члены содержатся в разложении произведения (i-2 27,+ ..(i-2 2+*J.

Таким образом, ]/?| не превосходит числа членов ^qr qr^ ...)”

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

I ЯI ^ (2&0 + 1 )2 (2^ + 1 )2. . . (2^ + 1 )2.(126)

Структура главного члена Е. Положительную /-кратную сумму в (124) обозначим символом Е^ и положим £(°)=1. Далее, пусть Ет обозначает сумму всех таких слагаемых (2^7/).. .(2^) в (124), у которых все rw > km. Вследствие (125) это возможно лишь для jjk; 2m, так что в Е^ при 1^>2т такие слагаемые не входят. Если Ет представляет собой пересечение Ет и Е^\ то Е^ = ^ для 1^>2т, так что имеем:

2т

Ет^ 2 (-1V5™, 5^ = 1.

/=о

Положим еще ^+1=0 (на конструкцию Е это не окажет влияния), тогда E = ES+X.

Простые числа qxi q^...qkm по определению не входят в Ет. При переходе от Ет к Ет^х добавляются еще N=km—ктл.х простых чисел qz с km^x <^z ^ кт. Символом 5^1 обозначим

р-ю элементарную симметрическую функцию1) N чисел 2^”\ тогда легко получим соотношения

/2т -|- 2 /

1 = 2 ^^\ Ет+1= 2 2 НГ S^W, (127) ^ —Оf=0 v=0

где S^i =0 для |i>N. С другой стороны, получаем:

2т N

Ет П (1 - 2^*) = 2 2 (- 1У+ 3 ^т S^x =

Zа = 0 Р = О

^4-2тп /

= 2 2 (-1/е^^Т.

i—0 у—О

Положив т = /—2т и приняв во внимание, что Е^ = 0 для <и^>2т, из (127) получим:

N2т

^+1=£ОТП(1 -^- 2 (- i)T 2 ^№-"\ (128) гт=3-у=0

Двойная сумма впервые встречается при ^^3. Для ^= 1 или 2

Ет^Еа П(1—2^7*).

Числа kj мы определим так, чтобы за исключением конечного числа исключений было

s^-^2^1 <i.

Из оценки2)

^ + 1

вытекает, что внутренние суммы в двойной сумме равенства

^ Элементарные симметрические функции $^\ ^\ ..., $^ переменных xv х2, ... ,хп определяются разложением (х — xj(х — х2)... . .. (X — Х„) = S ^х" — s^x"-1 +... 4- (— 1)" jW

=) Имеем ^Yi ^S^tS^*), так как каждое слагаемое из S^+1 можно g способами записать в виде произведения некоторого слагаемого из S^^_t и некоторого слагаемого из S^^^ и все такие произведения встречаются в правой части. Оценка получается после перемножения таких неравенств для ^=2, 3, ..., L

(128) монотонно убывают с ростом т. Так как эти суммы имеют чередующиеся знаки, то двойная сумма больше, чем первый (отрицательный) член. Таким образом, имеем:

2/л

^+1<£тП(1+2^')+ 2 ^’^t3"^ (129)

X17 = 0

Определение чисел к. Пусть р, р0 — постоянные и

Ро>Р>1. 0<21ogp0<l.

Положим

Так как для простых чисел qj также справедливы (правда, с другими постоянными) теоремы 23 и 25, то для N простых чисел дг, km*x<z^km

Qk +> "2"Sm + l — 52 ^z logp + o(l),

2

(130)

2Г

Существует такое (о, зависящее лишь от р и р0, и такое целое Л1, что для ^W>^m+1><D соответственно пк^М, о-члены в (130) так малы, что

(131)(131)S^+1<2logpo<l, Pm+1>po-2.

(131)

(131)

Теперь мы должны выбрать интервалы kc+1 < /^ kc, где 1>/И4*1 для индексов I конечного числа простых чисел ^^(0. Для того чтобы сумму в (129) можно было опустить, достаточно положить кс— ^+1==2 или 1.

Оценка Е. Сумма в (129) состоит из различных произведений по ^т 4- 3 множителей 2^“^ где р> Z^,, поэтому она меньше, чем (2т~43)-я симметрическая функция p2/n+8i величин 2^“г, содержащая все произведения такого рода. Пока выполняется (131), имеем:

W = 5 2q;1 = ^’+, + ^ 4- .. . + ^ < 2 ^т 4- 1) log р0.

Из общей оценки1) следует при T = ilogp0

уЧВ/И+З)уЧВ/И+З)/ g/XD \2m + 3(2^4-3)/ g/XD \2m + 3(2^4-3)

уЧВ/И+З)

уЧВ/И+З)

/ g/XD \2m + 3

(2^4-3)

/ g/XD \2m + 3

(2^4-3)

Если в (129) сумма еще имеется, из (131) получаем:

Ет+1 < Ет П (1 - 2^7*) + ^ < Рт^х {Е^^ р«)

и отсюда путем итерации, учитывая, что Ео = 1,

Е^х <Рт+х Рт---Рх^ + ^ + . . . + ^ + ’ Р^’Г (132)

Если тр0 = гр0 log р0 < 1, то геометрическую прогрессию в (132) можно заменить бесконечной прогрессией, что сделает скобку не зависящей от т. Принимая во внимание соотношение Ес+Л ^ Ес^с-¥х для ^^^+1» получаем, наконец,

кт8р

£=^+1<8П(1-2^71), 6=1+77^, ^>3. (133)

Оценка остаточного члена R. Вследствие условия ^, ^ 3 всегда выполняется неравенство 2т -|- 1 ^ дт. Поэтому из (126) следует

I Р I ^ ^= ^. • • • Чкм Ам^-'-чХ^ Чк &м^ • •-qX" &А-

По § 64 величина А постоянная, зависящая лишь от р и р0, а для Q вследствие ^W^^,pm находим:

9 = 2 + 2?-+...+2р-« = 2^=ГЧ<^.

Отсюда получается оценка

2р

[/гкд^г^(134)

Результат применения метода решета. Если h = = ti ^хХ1и\ то из (133), (134) и теоремы 25 следует при условии 2р/(р—1)=/д

N Vd. х,хиХ Сь% -^ jog2 % + Сь^=

р ^2 х г 1 । СЬ9<1 log2x'>

— С58 d 10g2X V ‘

’; Применяется оценка, которая была доказана в примечании на стр. 99, и получающееся из (54) неравенство il>ile”1 (6 = 2,718...).

Вследствие (51) скобка при /<1 имеет порядок 1 -{—о (1). Это имеет место при р = 5/4 и д=11. Если положить р0= 1,2501, то предположения § 64 и § 65 выполняются, так как тр0 = 0,758. Для этих чисел 8=1,82. Скобка в (135), очевидно, и при и">\\ асимптотически равна 1. Если, наоборот, и при фиксированном х убывает, то решето может лишь расшириться, так как в нем, возможно, будет участвовать большее число простых чисел q{. Таким образом, N^d, х, xXiu^ при уменьшении и во всяком случае не увеличится, так что для и ^2 и х^х0 имеем:

N^x^^^L.(136)

Cw естественно, зависит от и. Оценка (136) дает истинный порядок роста величины N (d, х, х1'"), так как можно методом Бруна доказать также неравенство

N (d, х, х1'^ ^ Св1 x/log2 х, где Св1 2> 0 для и ^10.

До сих пор мы предполагали, что ai=^bi для всех L Если для некоторых «исключительных простых чисел» qo будет аа = Ьа) то N^d, х, х1/я) увеличится. Для того чтобы обобщить (136) на этот случай, сопоставим каждому q. число ^ таким образом, чтобы было vt = 2, если q( — нормальное простое число, и ^-=1, если q( — исключительное простое число. В предшествующем выводе мы можем вообще заменить ^qy1 на v^y1. Для произведения в (133) с помощью теоремы 24 получаем:

11(1-^7')< 11(1— д?г^ =

= П(1-<771)гП(1-97')-,=

-OWogAO-’ntl+^'Hl-.yr2)--}^

= О{(1о?х)-8П(1+971),

потому что П(1—^7')"’ сходится, как часть ряда ^п~\ Так как остаточный член не увеличится, то имеем общую оценку

Nkd, х, х") = О {х (log х)"2 П (1 +^7*)}.(137)

Простые близнецы. Из последовательности нечетных чисел п (а — 1, <^ = 2) требуется выделить простые близнецы. Числа п — 2 и /г Ы х оба являются простыми ">V х^ если они не делятся ни на одно р^ Ы V х^ т. е. когда п ф 0 (mod р^ п — 2^0 (mod р^. Если символом Z ^ обозначить количество пар близнецовых, то для а( = 0, Ь{ = 2, q. = pi+v х>х0 получим из (136)

ZW = N^,x, z-/=) + Z(Ka; + 2)<-^4

-\-Vx-V2-\-Vx-V2СцХlog2x *СцХlog2x *

-\-Vx-V2

-\-Vx-V2

СцХlog2x *

СцХlog2x *

Если tm большее простое число из w-й пары близнецов, то получаем таким образом

<

и7Ит/ u7i /^71

ИЛИ — < i о , ■ <С —1 о . log2 tm tm ™ log2 tm tn log2 tn

Так как по (57) рядТак как по (57) рядS tn log2 tnS tn log2 tnсходится, то имеет место досходится, то имеет место до

Так как по (57) ряд

Так как по (57) ряд

S tn log2 tn

S tn log2 tn

сходится, то имеет место до

сходится, то имеет место до

казанная Бруном в 1919 г.

Теорема 39. Ряд из величин* обратных простым близнецам, обрывается или сходится.

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

Количество представлений натурального числа в виде суммы или разности простых чисел. Символом L (х, у) при заданном четном у обозначим количество решений уравнения у = р — р' при рЫх, р'^хгу

Очевидно, L (х’\ у) Ы V х, так как дляры^х существует не более чем Vx решений. Если p^>Vx и p'>Vxi то первые п(У"х) простых чисел pz [Z=l, 2, ..., к(]/ х)] отличны от р и р . Если для некоторого п Ы х будет п ^ 0 (mod pz) и п—у ^ 0 (mod pz), то п и п—у — это нечетные простые числа — решения р, р'. Такие п можно найти просеиванием при a=\s d = 2, ai — ^, Ь(=у. Исключительными простыми числами в смысле § 67 являются простые делители у, так как

для них а( = Ь{. Так как Vх = о (х/log х), то из (37) получаем:

Z, (х, j/) ^ Л/(2, х, х1-/2)-|-2 Ух4-

+ C,гx(logx)-2П(l+p■,). (138)

Р\У

Рассмотрим теперь число решений L (х) уравнения х = ^р-^р'. Можно считать х четным и 7^ 4, тогда р и р— нечетные. Теперь р<^х. Для р^Ух или р ^Ух снова

существует не более чем 2 Ух решений. Решения ср^>|/ х, р' ^> Ух, как и прежде, находим просеиванием при а=1, ^ = 2, #z = 0, bt = х, причем исключительными простыми числами являются простые делители х. Таким образом, имеем:

А(х)<С,9х(1о§х)-2П(1+р’').(139)

Р\Х

Одна теорема Эрдёша особенно ясно подчеркивает упомянутую еще в § 5 нерегулярность в распределении простых чисел. По Эрдёшу [7] существует, например, 106 последовательных р, для которых разность между соседними простыми числами )> 1012. Точнее, справедлива

Теорема 40. Пусть D — фиксированная постоянная и п сколь угодно большое, тогда существует постоянная с, зависящая лишь от D, и r — \c log л] последовательных простых чисел

Рк+1<Рк+г<. • -<Рк+г<П,

таких, что

Pk+i — pk+i-1>DPk+i — pk+i-1>Dв — 1,2, ..., гув — 1,2, ..., гу

Pk+i — pk+i-1>D

Pk+i — pk+i-1>D

в — 1,2, ..., гу

в — 1,2, ..., гу

Доказательство. Количество /(л) решений неравенств рт+х—pm^D, рт+х^п меньше, чем общее число решений D уравнений р— p=ys р^п, X^y^D. Вследствие (138) получаем /(/z) < С74 п (log л)-2, где С74 зависит от D. Числа ртЛ.х^п распределим теперь на два класса, причем рт+1 принадлежит к первому классу, если рт+х —pm^D, и ко второму классу, если ртЛ.х—рт*>>Ог\ Каждой последовательности последовательных простых чисел Ра+Н

Pa-vv --^Ра+г второго класса соответствует простое число ра

первого класса. Если г^1—максимальная длина такой последовательности второго класса, то, очевидно, имеем тг (/z)< 2r/(/z). Из вышеупомянутой оценки для /(/z) и теоремы 28 следует

2/(72)2/(72)С,5 ^ ”'С,5 ^ ”'

2/(72)

2/(72)

С,5 ^ ”'

С,5 ^ ”'

где С75 = С21/2С74 зависит от D, что и требовалось доказать.

Замечания. В качестве простых чисел решета можно взять также р из некоторого подмножества ЭЛ' множества ЭЛ всех простых чисел, если для р ^ х из ЭЛ' имеет место формула

^Р 4ogp = plogx4-O(l), 0<р<11),

аналогичная теореме 22 (Риччи, Р. Д. Джемс). В этом случае величина О (x/log2?A:) дает истинный порядок роста N(d, х, xiuy Бухштаб улучшил постоянные С61 и С60 (ср. (136)) для малых значений и; в частности, Св1 > 0 для и ^ 5. Недавно А. Сельберг [23], [24] развил интересный метод решета, который приводит к поразительно хорошим результатам. Мы приведем результат просеивания для простейшего случая. Пусть дана любая последовательность из N натуральных чисел п. Предположим, что количество /z, делящихся на постоянное число к, может быть записано в форме Njf^-\-Rk, где /(^)— мультипликативная функция, для которой /(1) = 1, а для «остаточного члена» имеем ] Rk | ^ k\f^k\ Тогда для количества N2 тех /z, которые не делятся ни на какие простые числа р ^ z, получается оценка (ср. Чулановский [47])

Nz^Nl 2 |i2WlIpitNz^Nl 2 |i2WlIpit1/w-1/w-1P^z \1P^z \fwfw

Nz^Nl 2 |i2WlI

pit

Nz^Nl 2 |i2WlI

pit

1

/w-

1

/w-

1P^z \

1P^z \

fw

fw

Если /z = P(x), A^x^N, где P^ целозначный полином без постоянного простого делителя, а и^— количество несравнимых по mod d решений сравнения Р^~0 (mod d^ то существует Nd^u^-^- Rd делящихся на d чисел /z, где \Rd\^u^dY Таким образом, здесь f(d)=d]u(d). Функция /(d) мультипликативна, так как такой является и (d).

Для Р(х) = х(2-4-х) и г = (М-^ 2)12~е снова находим оценку для количества простых близнецов, полученную в § 68. Здесь С71=10,6, тогда как у Бруна С71 —100. Правда, использование формулы Сельберга является несколько трудным.

Интересные применения нашло также так называемое «большое решето» русского математика Линника. Простыми числами решета служат у любых простых чисел Pi <^VN (/=1,2, ..., у). Каждому р( сопоставляют f^p^ определенных классов вычетов по mod pz, где f(PiXPb и 113 ряда первых N -натуральных чисел n^N вычеркивают каждое л, которое хотя бы для одного р( входит в один из f^Pi) зафиксированных классов вычетов по mod pz. Если т— наименьшее из чисел /^Р^РсЛ0 после просеивания останется не более чем 20пт”2у“1М Это утверждение можно высказать также и в следующей эквивалентной форме: если каждому простому числу p<CVN сопоставить целое число /(рХА то z любых натуральных чисел пх <Спг <\..<пг^ N почти для всех p<JV ^ принадлежат по крайней мере р—/(р) различным классам вычетов по mod р. Количество исключительных простых чисел, которым соответствует меньшее число классов вычетов, не превышает величины 20nT"2z”W, где т — наименьшее из чисел f(p)jp для р ^ VN. Реньи заметил, что это вытекает из одной общей теоремы теории вероятностей, которая позволяет еще точнее описать распределение чисел п по классам вычетов по mod р. Основываясь на своем обобщении большого решета, Реньи удалось показать, что любое достаточно большое четное число является суммой простого и почти простого (л = Цре/7 называется почти простым, если ^ер^К, где К—абсолютная постоянная). Реньи удалось далее показать, что существует бесконечно много простых р, для которых рЦ-2 является почти простым.

ГИПОТЕЗА ГОЛЬДБАХА

Ранее полученные результаты. В 1742 г. в письме

К Эйлеру Гольдбах высказал следующие гипотезы:

Каждое четное число > 2 представимо в виде суммы двух простых чисел.

Каждое целое число > 5 представимо в виде суммы трех простых чисел.

Очевидно, гипотезы А и В эквивалентны. Из 2л— 2 = =Р1+Рг следует 2л = рх + рг + 2 и Чп +1 =рх +рг + 3. Наоборот, из 211= рх Ц-р2Ц-р3 следует, что pt = 2 и 2л — 2 = р2Ц-р3. Утверждения А и В до сих пор полностью не доказаны.

Из обобщенной гипотезы Римана в 1922 г. Харди и Литтльвуд смогли вывести, что каждое достаточно большое нечетное число представимо в виде суммы трех простых чисел. В 1937 г. Виноградову удалось получить этот результат независимо от недоказанной гипотезы1). Для количества A(N) представлений нечетного N в виде суммы трех простых чисел имеется выражение

x{n(i + (^)n^-?-^) + o(i>}, где первое произведение распространено на все р, а второе лишь на простые делители N.

Пиппинг представил все нечетные N из интервала 9 ^iV^ 360 749 в виде суммы трех нечетных простых чисел, наименьшее из которых равно 3, 5 или 7. Он подтвердил также гипотезу А для всех 100 000.

В направлении гипотезы А также достигнуты интересные результаты. Символом 5(х) обозначим количество таких четных п ^ х, которые нельзя представить в виде суммы двух простых, тогда lim S(x)/x = 0, т. е. «почти все» четные

X -> ОО

числа являются суммами двух простых чисел (Эстерман, ван дер Корпут). Несмотря на это, естественно, все еще возможно бесконечно много исключений.

Упомянутый в § 60 путь к доказательству гипотезы А методом решета не приводит к цели, так как оценки снизу положительным числом для N (2, х, х) не получены. Все же методом решета можно показать, что каждое достаточно

большое четное п допускает представление в форме п = ат A* bkS\ где avn составное число, состоящее не более чем из г простых множителей (дт = р, а'2' — р2 или рр s и т. д.). Примеры: г = 5 = 9 (Брун, 1919); г —^ = 7 (Радемахер, 1924); r = s = ^ (Эстерман, 1932); г = 5, 5 = 7; г—4, 5 = 9; г = 3, 5=15; г = 2, 5 = 366 (Риччи, 1936); г = s = 4 (Бухштаб, 1940); г=1, 5 =/С (абсолютная константа) (Реньи, 1947); г = 2, 5 = 3 (А. Сельберг, 1950).

Аддитивные представления натуральных чисел простыми числами. По гипотезе В в представлении

п—р Аг* р A* ри • • • 4* р^

всегда можно обойтись тремя слагаемыми. Без ограничения числа слагаемых легко получается доказанная Рихертом [19]

Теорема 41. Каждое натуральное число /г > 6 представимо в виде суммы неравных простых чисел.

Доказательство. Разложения 7 = 7, 8 = 5—}—3, 9 = 74-2, 10 = 74-3, 11 = 11, 12 = 7-|-5, 13=114-2, 14=114-3,15 = 74-54-3, 1б=н-|-5,17 = 74-54-34-2, 18=114-7, 19=114-54-3 показывают, что серия из 50=13^р6 последовательных чисел может быть построена из различных простых рх = 2, р2 = 3, р3 = 5, р4 = 7, ps = 11. Если к этим 50 числам прибавить р6=13, то всего получим 5t = s0 4- рв = 26 чисел 7 ^ п ^ 32, представленных в требуемой форме. Добавление р7=17 к уже представленным 5, числам расширит нашу область до 52 = 5} 4-Р^ = 43 чисел 7 ^ п ^ 49. Эта операция может быть бесконечно продолжаема, если в 5д+1 =5^4“Pe+k всегда p6+^^sfe. В этом мы можем убедиться с помощью полной индукции. Из p6 + ^_1 $к_г и теоремы 31 следует

Pe+6<2pe+6_]<sft_,+pe + »_1 = s6, ч. т. д.

В 1930 г. русским математиком Шнирельманом элементарным методом доказана существенно приближающаяся к гипотезе В

Теорема 42. Каждое натуральное п > 1 представимо в виде суммы не более чем S простых чисел. При этом S — абсолютная постоянная (постоянная Шнирельмана).

Мы легко проведем доказательство существования S после некоторых приготовлений. Численное значение S последовательно снижалось от 800 000 (Шнирельман) до 67 (Риччи,

1936). В 1951 г. Шапиро и Варга [30] методом решета Сельберга получили неравенство 5^20. Из теоремы Гольдбаха — Виноградова следует, что для достаточно больших п будет 5^4, так как из 2/г—1 — рх -|- р2 -]- р3 тотчас следует 2/г —|—2 = 3 —[—^ + р2 + р3

Плотность числовой последовательности является основным понятием при аддитивном представлении. Пусть Д = {а, = 1, я2, ...} подпоследовательность последовательности натуральных чисел, содержащая единицу, а А (х) обозначает количество а(^ х, а^А. Под плотностью а последовательности А понимают нижнюю грань отношения А^х^х. Таким образом, А^^ах для всех х^1 и O^a^l. Например, арифметическая прогрессия с первым членом 1 и разностью d имеет плотность \[d. Из а=1 следует A = R.

Из 5 последовательностей

с плотностями an a2, ..., as построим суммарную последовательность С= Ах -j- Д2 + • • • + Д5, которая содержит все различные положительные числа вида е^^-|-... 4“^^ (sv —9 или 1), расположенные в порядке возрастания. Если Ах — А3=... ...=AS=A и С содержит все натуральные числа C = sA = R, то это означает, что любое п допускает представление в виде суммы не более чем s слагаемых из А. Естественно спросить, как плотность у последовательности С зависит от плотностей an a2, ..., ar В 1942 г. X. Манн доказал давно предполагаемое соотношение

Y>a,4-a2+ ... +^ или у=1

в зависимости от того, будет ли at Ц- а2 -|* ... + as < 1 или ^1. Таким образом, при а>0 последовательность sA имеет плотность 1, если sa^ 1, а это означает, что каждое п допускает аддитивное представление с помощью не более чем [к-1]-4~1 элементов из А. Так как мы доказываем лишь существование постоянной Шнирельмана, нам достаточно получить худшую оценку для у, которая зато проще выводится.

Заметим, во-первых, что из 2a ^ 1 тотчас следует 2A = R. Действительно, если х > 1 не входит в Д, то А^х—1) = = Д (х) ax > а (х — 1). Количество положительных х— as^x—1 также равно Д (х—1). Если бы все as

их — as были различными, то существовало бы больше чем 2а (х—1) чисел ^ х—1, что невозможно, так как 2а ^1. Таким образом, хотя бы один раз х— as = at или x = as-\-at.

Лемма. Если последовательность А имеет плотность а^>0, то плотность ^Л по меньшей мере равна 1 — (1 — а/.

Доказательство. Рассмотрим сперва две последовательности А и В с плотностями а и р. Тогда С = А -^-В наверняка содержит следующие различные элементы ^ х:

Л(х)^ах чисел из A\av = \, а21 . ..,а,Аиу

B(ai+l — а( — 1)>^(а,.+ 1 — а,— 1) чисел а^Ь, между а{ и а(-+1 [ 1 Д (х)].

5(х —<z4 w)5sp(x —аД(х)) чисел аМх^Ьг^х.

Сложением получаем:

С(х) 5= А (х) + р {а4 (х) — а, — [Д (х) — 1 ] + х — аА (х)} =

= Д (х) + р[х —Д (х)] =

= £Sx —|™ (1 — р) А (х) ^ рх -|- (1 — р) ах =

= (а -|- р — ар) х.

Так как 2а — а2 = 1—(1—а)2, то лемма для 5 = 2 доказана. Для любого 5 доказательство получается полной индукцией. При р=1—(1—а)5-1 имеем:

С(х)^ {а-]- 1 —(1 —а)^-1 — а[1 —(1 —а/"1]}х = = {а-4”(1 —а)[1 —(1 —а)'?“1]}х={1 —(1 —а)*9} х, ч. т. д.

Так как мы можем теперь предположить, что а <1 /2, то существует такое наименьшее т, что 1—(1—а)т^1/2. Тогда 2 (/пЛ) = 2mA = R.

Доля метода решета в доказательстве существования S. По теореме 27 последовательность простых чисел имеет плотность нуль, даже если добавить впереди 1. Шни- рельманом доказана имеющая интерес сама по себе

Теорема 43. Последовательность, состоящая из 1 и сумм простых чисел р-^р, имеет положительную плотность.

Доказательство. Пусть М(х) означает количество чисел 4 ^ п ^ х, представимых в виде суммы р-\-р\ a D (/г)—

количество представлений для фиксированного п. Из неравенства Шварца1) следует

2 1 ‘Щл)1(х) 2 ^2 (л) нли

п=4*п. — ^

(2 D^V

(140)(140)М (X) >

(140)

(140)

2 D»W

2 О (/г) п2и = 42 О (/г) п2и = 4С х2log2x *С х2log2x *Для того чтобы иметь возможность применить (140), используем оценку снизу для числителя и оценку сверху для знаменателя. Оценку снизу легко получаем из теоремы 28

2 О (/г) п2

и = 4

2 О (/г) п2

и = 4

С х2

log2x *

С х2

log2x *

(141)

Для всех р ^ х^ р' ^ х/2 имеем р -{- р' ^ х, т. е. р-\-р' — представление, учтенное в 2^(я), ПРИ‘ чем р-^-р* и р'-^р для р^=р рассматриваются как различные.

Оценку сверху для D^ доставит нам оценка (139), доказанная методом решета. Для того чтобы оценить 2 О2 (л), рассмотрим разложение распространенного на все простые делители п произведения £J (1 +р ’)2=2й '2> 1 =Sw *, где а и b независимо пробегают все делители п^ свободные от квадратов. Если просуммировать теперь такие равенства для всех zz^x, то произведение ab при а^х, Ь^х встретится в правой части лишь тогда, когда общее наименьшее кратное {а, £} чисел а и b является делителем одного из п, а это для п^х будет точно [х {а, £}-1] раз. Так как {<2, 6} ^ <2, ^ Ь, то {a, £} ^ VаЬ, так что вследствие (.53)

*) (5 ct^nf ^ 2 <^п 2 ЬЧ Доказательство: квадратное уравнение 2 капх + ^nf = 0 не может иметь вещественных корней, кроме случая bilai — \, когда х1=х2 = —X. Следовательно, для дискриминанта имеем:

(2^А)2-2^2^^0.

при р = -|-0,5

х х3 со 3 оо 3

<2 2 x^ab^ ^<х а 2 2 ^ 2<С81х.

а=Л Ь=Ла = 16=1

Для x^n^S можно в неравенстве для D^n\ аналогичном (139), заменить n(logfl)“2 большей величиной x(logx)"2. Получим:

2 Z)2 W < С%\ Л-2 (log хГ4 С%хх = V (log х^\ п^х

Отсюда и из (140) и (141) следует

^(A^C^OogX^CsVx-’ODgX)4^^ Ч. Т. Д.

Доказательство теоремы 42. На основании § 74 и теоремы 43 существует такое натуральное число &, что R = kM, где М — это последовательность, состоящая из чисел 1 и р-Д-р'. Таким образом, для представления любого п^Х достаточно к слагаемых 1 или р-\-р\ т. е. ^к слагаемых 1 или р. Если п >2, то из разложения числа п— 2 получается представление п = 2+21+2р. Число 2+21 можно записать или в виде 2 2 или в виде 3 +22. Таким образом, s 2k и конечность s доказана.

АНАЛИТИЧЕСКИЙ МЕТОД ОЦЕНКИ ЧИСЛА ПРОСТЫХ ЧИСЕЛ В НАТУРАЛЬНОМ РЯДЕ И АРИФМЕТИЧЕСКОЙ

ПРОГРЕССИИ

А. О. Гельфонд

Элементарный метод А. Сельберга, дающий возможность доказать предельный закон распределения простых чисел, не может служить для сколько-нибудь хорошей оценки остаточного члена в формуле

Для величины R^ можно только получить оценку wic^,

где а — некоторая постоянная, 0<^а<^1. Аналитический же метод Адамара — Валле-Пуссена, опирающийся на аналитические свойства функции Римана

* 1

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

(1)

2

з

где а>0— постоянная, а у= у [1,2,3,4]. Это значение у— наилучшее известное в настоящее время, первое же полученное

для у значение было -^. Остаточный член в формуле (1) растет, например, медленнее, чем xln^^x для произвольного сколь угодно большого N.

Мы дадим здесь изложение метода Адамара — Валле-Пуссена в упрощенной форме, без более глубокого изучения свойств Ц^) и А (5, /J

где /(/?) — характер модуля т^Х, необходимого для получения оценки (1) при у^у или, более общо, оценки

х

^■.‘.^= ^ 1 =,^j£+°т р = е (mod т)2

(/, ^z) = 1,

при У = '2" или $ольших величинах у. Вместо уточнения оценки остаточного члена мы зато дадим доказательство оценки (2) для любой прогрессии с разностью т и, в частности, для натурального ряда. Прежде всего установим связь между функцией ф (х)

W-^/W, А (»)={ 1ПОР’ ^^(3)

где р— простое число, и функцией Эйлера — Римана ^(s). Эта связь в простейшем случае, для ф(х), имеет вид

* ' ' J т х '2к/ J (5) ^ (^ + 1)’х '

2а0

где интеграл взят в комплексной плоскости 5 по прямой Rs = o, s ^> 1 в положительном направлении.

Докажем справедливость формулы (4) в более общем случае арифметической прогрессии.

Лемма I. Если

где ^^ какой-либо характер модуля т^\ (при w=l L^s,^ = ^^\ то имеет место представление

X

(6)

где интеграл взят по прямой Rs —а от —оо до оо,

а ф (х, -^ имеет вид

ф (х, х) = 2 X W л W; ф, (х, х) = 2 X (”)А (”) (х — ”)• (7) п<^хп^х

Прежде всего заметим, что

где произведение взято по всем простым числам в силу мультипликативности z(^)> XWlW — X^) и того, что все целые числа единственным образом представляются в виде произведения простых.

Логарифмируя и разлагая в ряд каждое слагаемое, мы получаем, что

1пА($,Х):=-У1п(1-Ц^ = У У Й^.

vТ р ' р кр

Дифференцируя по s, мы окончательно получаем, что

L’ («М)_ v Vх ^ ^P—Xt X W л М /Qx p*sns(у)

по определению функции Мангольта A (zz). Полученный ряд равномерно сходится по s в любой полосе ах ^ Rs ^ а0 > 1. Вычислим теперь один вспомогательный интеграл. Пусть, действительно, х^>0. Тогда

j_c_xl_d х(Ю)

2«J s(^+l)as—1 о Х<1V '

°0’’

где интеграл взят по прямой /?^ = j0^>0 (s —j -^-lt, a = a0\ Действительно, если x ^ 1, то, пользуясь теоремой Коши и замыкая контур интегрирования в правой полуплоскости, мы

получаем, что наш интеграл равен нулю, так как в этой полуплоскости

I X5 I Хао. .,

\ 75—i 9 , $ ^ —Г •1$(^ + 1)|*

Если же х> 1, то, пользуясь теоремой о вычетах и перенося контур интегрирования на прямую 5, <—1, получаем, что

ft— \ ds = 1 — х +\ —гт ds=\,

2kz J s (s + 1)* 2л/ J s (5 -f 1)х ’

ОО°!

так как интеграл по прямой ах равен нулю по той же причине, что и интеграл по а0 в случае х^ 1. Его можно замкнуть в левой полуплоскости и воспользоваться теоремой Коши. Пользуясь свойствами интеграла (10), мы можем теперь вычислить интеграл

СГ (—V

—1 1 L' (», х) х^1_ ^ х (”) л W х I \У/ . _

2к/J £ (», х) » (s + 1)„^ 2tw Js(s4-l)“d —

ООа0

= 2 № А(л)(х — л), а0>1, (11) п х

так как почленное интегрирование ряда (9) возможно в силу равномерной его сходимости на прямой Rs = j0 > 1.

Далее, если ф (х, )() = 2 Z W Л W> TOi меняя порядок и ^?х

интегрирования и суммирования, мы будем иметь, что

XX

5ф(х, X)rfx=^ 2 х(”)Л(”)^ = 22 "^

= 2 iwxw^dt= 2 x(”)А («)(*—«)• п^хпп^х

Этим лемма I доказана.

Для того чтобы из представления (6) функции cbj (х, /) получить ее главный член и оценку остаточного члена, надо L* {s, у)„,,

иметь сведения о поведении -^—-х хоть в какои-либо обла- L ks. х)

сти, лежащей левее прямой Z?s = 11 другими словами, при s = a-^-it левее прямой а=1. Прежде всего заметим, что направо от прямой а=1 функция L^s,^ — аналитическая

функция, не имеющая нулей и особенностей. Это следует из равномерной сходимости бесконечного произведения (8) в области Rs а0 > 1, | | < г, при любых j0 и г, так как в этой области равномерно сходится ряд 2 где сУмма взята по р Р

всем простым. Этот последний факт сходимости ряда 2*5 р р есть прямое следствие тривиального неравенства рк > к, где рк — к-е простое число, р1 = 2. Для дальнейшего нам достаточно будет рассмотреть поведение L (s, /) и, в частности, CU) только в области, определяемой неравенствами

'—mm + y-S’-e2- « = « + ».02)

где у>1—некоторая фиксированная постоянная, а с, 0<^с^^— достаточно малая постоянная. Существенную роль при оценке порядка убывания остаточного члена для ф, (х, ^ играет постоянная у—она определяет порядок в показателе оценки (2), а с связано только с множителем а в том же показателе.

Лемма II. Если ^^ есть главный характер модуля т ^ 1, другими словами, ц (п) = 1, (л, т) = 1, у (л) = О, (/л, л) )> 1, то функция L (s, у) имеет полюс первого порядка в области (12) при 5=1 ив этой области, вне кружка 15 — 1 | = 6, где 6 > О — любая постоянная, выполняются неравенства

|£(s, Х)|<Д1п(р|4-3), |£'(s, Х)1<^1п2(|^|4-3). (13) где А— положительная постоянная, зависящая только от 8 и s = a-\-it.

Для доказательства этой леммы достаточно получить оценку только для £ (5), так как при т > 1

L^s, Х)= II (l-P'T’ — Iltl-P'W), (14) (р, M)=l р^т

где первый множитель в правой части есть целая функция $ и в области (12) ограничен вместе с первой производной. Действительно, в области (12)

°<П11—р"1^П (! +р-°ХП2

р\пг р\т p\tn

и, кроме того,

так как а в области (12) не меньше-^- .

Пусть сначала /?s^>l. Положим Л/=[/]4-1- Тогда

Г[х]^хС dx 1 со г^ п 1 _

NпIN

и, кроме того,

NNN

СО 100 z 1

Hx\dx_ 1. №-s — 1 еЫ_^х

'5— 1 J X5+15— 1 •5—1 J x5+1*

NN

Воспользовавшись этими двумя соотношениями для определения £($), мы получаем, что, так как [х] = х—{х},

ш=^-«-*+«уа£=

N

^s+^-N'-' + ^lZV'-’-ll-sCM.,,. (15) It О 1о 1л

N

Уже из этого соотношения видно, что £ (s) регулярна в полуплоскости /?s>0, за исключением точки s=l, где £ (s) имеет полюс первого порядка с вычетом единицы, так как все члены в правой части (15) регулярны в правой полуплоскости, 5 за исключением г .

5 — 1

Оценку | С (s) | будем вести при | /1 ^ 1 и 2 ^ а ^ 1 — — Г^ТГТТТт >^ы будем здесь и в дальнейшем

пользоваться оценками (52)—(57) из книги Троста без ссылок.

Прежде всего будем иметь, что при а^1 — М7Т+Т)’ Is"

£ 1

n *+in(|q +3)^. N mat l+3)y 2

Jn (l< 14-0

= e ln(UI + 3)O(lnW)=O[ln(p|4-3)]; ln

| W*"5" | = / ln(in+3)=O(l), l^-^^Otl).

Далее,

С{x}dx

N

dx

N

^^-’ = 0(1).

Применяя эти оценки к (15), получаем, что |Ш| = О[1п(|/|4-3)], h-1 Is

ln(m + 3),

О,

(16)

(16')

(17)

£

4 ‘

Дифференцируя (15) по s, получаем:

Innкт Nx-S sAP~s«

s) = —In TV—;г In TV —

‘(s — I)2 s — 1

00 ..00 ..

dx.

(18)

N

N

Пользуясь только что полученными оценками и к ним оценки

присоединяя

V ln п

N in(m+3)^i^=O|-ln2(|/|_|_3)j)

{ xjlnx

N

N

2|21±21n2V.2Vln(|,|+3,= O[ln (IH4-3)],

(19)

мы получаем для | ^ (s) | оценку

k'(s)| = O[ln2(|/| + 3)], 2>в>1k'(s)| = O[ln2(|/| + 3)], 2>в>1Сin(Rl + З) -Сin(Rl + З) -(20)(20)|s —1 |^8|s —1 |^80.0.

k'(s)| = O[ln2(|/| + 3)], 2>в>1

k'(s)| = O[ln2(|/| + 3)], 2>в>1

С

in(Rl + З) -

С

in(Rl + З) -

(20)

(20)

|s —1 |^8

|s —1 |^8

0.

0.

Применяя оценки (17) и (20) к соотношению (15), мы сразу получаем, что

|Л(»,Х)| = 0[1п(|/| + 3)], |Г($,х)| = О[1п2(И + 3)]а

1Н21)

2 5$ а 5= 1 — 1пТ (| z । _|_ з) > Y ^ 1 > с ^ -^ , | s — 1 | ^= 8. ,

Кроме того, мы получаем, что если у (zz) — главный характер модуля т, то в области (12) L(s, у) регулярна всюду, кроме точки ^=1, где она имеет полюс первого порядка.

Этим лемма II доказана.

Пусть теперь ^ (zz) — неглавный характер модуля т ^ 2. Полагая тогда

^=^zW. ^=[И+Ц

(22)(22)будем иметь, что

(22)

(22)

L'(s, х) = -У + "-^^х ' Wns 1к^+ 0

Пользуясь соотношениями (24) и (108) книги Троста, прежде всего будем иметь оценку | sn | < т. Отсюда следует, что

(s. Z)K^j„» + (W+ 1)’ + W lsljx’+1 ’

N

^ In n£ n3^ In n£ n3(23)(23)

^ In n

£ n3

^ In n

£ n3

(23)

(23)

00

+ (1'1+3)/»^^.

N

Эти неравенства того же типа, что и для | £ (s) | и | ^ (s) I и не требуют новых оценок для отдельных членов в правых частях. Поэтому, воспользовавшись неравенствами (16), (16') и (19), мы, так же как и выше, получаем, что

I £ (s, X) I = О [In (| /1 + 3)], | L' (s, х) | = О [In2 (| /1 + 3)Ъ с1}(24)

2 ^ а ^ 1 — JnT (| z । + 3), с < , у ^ 1 J

уже при любом /, так как в правых частях (22) стоят регулярные в полуплоскости а > О функции.

Итак, нами доказана

Лемма III. L(s, /) регулярна в полуплоскости а>0, s — s-^it при у(п) неглавном характере модуля т и в области (12) выполняются неравенства (24).

Теперь нам нужно получить оценки снизу для |A(s,/)| в области (12). Заметим прежде всего, что в книге Троста, в пп. 56 и 57 гл. VIII уже доказано необращение в нуль 7,(1, /) при неглавном характере /(/г) модуля т, другими словами, что

^0, Х)= ^~^0, x¥=Zo- (25>

Из этого следует вследствие аналитичности L (s, ^ при любом ^ что существует малая окрестность точки $=1, размеры которой зависят только от т, где L^s, у)=^0, так как при ^ главном характере в s = 1 7, ($, ^) имеет полюс.

Лемма IV. Если а, р, t и с действительны, а ^ О, ° > О, р > 1, | /1 > О, то имеет место неравенство Адамара

(26)(26)

(26)

(26)

Действительно, полагая el,xp-lt = е1^ р — действительное число, логарифмируя левую часть (26) и разлагая каждый логарифм в ряд, будем иметь, что

= ^^— (3 —|— 4 cos п^ 4" cos 2л^) == ^^— (3 —|— 4 cos п^ 4" cos 2л^) =

= ^^— (3 —|— 4 cos п^ 4" cos 2л^) =

= ^^— (3 —|— 4 cos п^ 4" cos 2л^) =

^^ <1 +cos 4)2>°.

так как логарифм модуля числа есть действительная часть его логарифма. Знак R обозначает взятие действительной части числа.

Из неравенства (26) следует

Лемма V. Если t^^^ то при любом ^ модуля т^ 1 и о> 1 имеет место неравенство

\l^g, x^v \l<a Х)Г| £(s„ х2)|>1,(27)

где s = <5-^11, st = с -^2И и у0 главный характер. Действительно, полагая в лемме IV еП = ^(р^ и перемножая левые части для всех простых р, что возможно при а> 1, мы по

лучаем неравенство (27) вследствие представления (8). Но в силу (14) и (15) при а> 1

ОО

и в силу оценки (24)

|£(а-]-2/У, х’)]<л,1п(]/| + 3), Л,>0, где Л, зависит от 8, при | о — 12/71 > S.

Пользуясь этими оценками, мы из неравенства (27) получаем неравенство

|^(^Х)1>(^) А 41" 4 (И + 3),(28)

верное при а> 1 и любом /, так как если у = /0— главный характер и / близко к нулю, то левая часть сколь угодно велика, а если у=^у0, то в окрестности 5—1, как мы уже видели, L (5, у) отлично от нуля.

Лемма VI. Существуют такие постоянные с0 и Л2, зависящие только от т, что в области (12) при с — С0 и Y = -9* функция L (5, у) при любом у модуля т^\ подчиняется неравенству

W, Х)|>W, Х)|>1а2 1пЧ I ^ 14-3) •1а2 1пЧ I ^ 14-3) •(29)(29)

W, Х)|>

W, Х)|>

1

а2 1пЧ I ^ 14-3) •

1

а2 1пЧ I ^ 14-3) •

(29)

(29)

Пусть а0<1, а, = 2 — а0, а^а0, 2>а0-|-а, s = a-]-//, s1 = g14~A />0. Тогда

^l

$ L' (s, /J ds = L К. X) — L A X)- 5

Отсюда в силу неравенств (28) и (21) следует неравенство

2-^— l)^ln-^(|Z|4-3) —(а,—а0)Л4п=(И+3) =

= 2"7л-Т(]_Оо)Т1п-4(|/|_|_з)ХХ[1—(1_О(()Т Л7 Л'2^ 1п~(|/|4-3)],

где А и А* можно считать большими единицы. Из этого неравенства видно, что если а0 удовлетворяет условию

(1-0о) 4 2 4 Л 4Л'1ПЧ1Н+З)<у’

другими словами, условию

1 — а0 = ^ In"9 (I 1 + 3), с. ^2“ПЛ-’ (Д')~\(30)

где t\ > 0 постоянная, то

\Lks, Х)1>2'^1п"’(|/|4-3) =

= АЧПЧТ7| + ЗГ’ (31)

а;.(32)(33)а;.(32)(33)где Д'— постоянная. Эта постоянная зависит от постоянной А\ которая в свою очередь зависит от 8, так как оценка | U (s, /0) | давалась вне кружка |$—1 | = 8. Поэтому оценка (31) может быть верна только вне кружка | s — 1 | = 8. Но, выбирая 8 столь малым, чтобы внутри этого кружка не было нулей L(s, /), и заменяя сх на cti^cv мы можем обеспечить существование неравенства (31) и вблизи точки ^=1, другими словами, в области (12) с заменой сх на сй и у на ~ с константой Д2 вместо Д2, где Av возможно, будет больше

а;.

(32)

(33)

а;.

(32)

(33)

Лемма VII. На кривой

где с^ определено в лемме VI, имеет место оценка

|^41<л 1п*(Н+3)»

I £ (s, X) I *111

где А9 — постоянная.

Эта лемма следует непосредственно из неравенств (29) и (24).

Теперь мы можем уже перейти к исследованию представления (6) для любого / (я) модуля т ^ 1.

В представлении (6) интеграл взят по прямой а = о1>1 в положительном направлении. По теореме Коши этот путь интегрирования можно заменить интегрированием вдоль кривой Г, даваемой уравнением (32), тоже в положительном направлении, так как в области, ограниченной кривой Г и прямой а = а1>1, подынтегральная функция удовлетворяет неравенству

l^(^x) ^(^ + i)|— L (ИК J’

при этом учитывается, что в точке $=1 полюс первого порядка с вычетом — 1,при этом учитывается, что в точке $=1 полюс первого порядка с вычетом — 1,—^ может иметь L (5, х)

при этом учитывается, что в точке $=1 полюс первого порядка с вычетом — 1,

при этом учитывается, что в точке $=1 полюс первого порядка с вычетом — 1,

если ^ есть главный

характер. В этом последнем случае L (s, /) имеет в точке 5=1, как мы видели, полюс первого порядка. Таким образом,

Ф1 (*> 1> = ТФ1 (*> 1> = Т(34)(34)мы будем иметь соотношение

Ф1 (*> 1> = Т

Ф1 (*> 1> = Т

(34)

(34)

Т 2п/ J L^s,^ s(» + l) ’Г

/ 12

7=рх’ Х = Хо.

v °. Х¥=Хо>

где /0— главный характер модуля т. В частном случае

Lks, X)=CU) и Т = 1х\

Оценим остаточный член на кривой Г. Прежде всего заметим, что на кривой Г, при / ^ О

|ds| = |d^l|ds| = |d^lIn’/^ + ^JI^ A*dt'In’/^ + ^JI^ A*dt'

|ds| = |d^l

|ds| = |d^l

In’/^ + ^JI^ A*dt'

In’/^ + ^JI^ A*dt'

где Д4— постоянная.Далее, пользуясь оценкой (33), получаем:где Д4— постоянная.Далее, пользуясь оценкой (33), получаем:J L^s, X)s($ + 1) * гJ L^s, X)s($ + 1) * г002£2—рln»(t + 3)<20 А,А4 j ^^_3)2ln-»(Z_^3) di< о002£2—рln»(t + 3)<20 А,А4 j ^^_3)2ln-»(Z_^3) di< о20Д.Л. \^-^2rf/ max0+ V20Д.Л. \^-^2rf/ max0+ VСрIn» (/ + 3) /грСрIn» (/ + 3) /грИнтеграл в правой части — постоянная, а максимум находится из решения простой задачи на минимум функцииИнтеграл в правой части — постоянная, а максимум находится из решения простой задачи на минимум функции

где Д4— постоянная.

Далее, пользуясь оценкой (33), получаем:

где Д4— постоянная.

Далее, пользуясь оценкой (33), получаем:

J L^s, X)s($ + 1) * г

J L^s, X)s($ + 1) * г

002£2—

рln»(t + 3)

<20 А,А4 j ^^_3)2ln-»(Z_^3) di< о

002£2—

рln»(t + 3)

<20 А,А4 j ^^_3)2ln-»(Z_^3) di< о

20Д.Л. \^-^2rf/ max0+ V

20Д.Л. \^-^2rf/ max0+ V

Ср

In» (/ + 3) /гр

Ср

In» (/ + 3) /гр

Интеграл в правой части — постоянная, а максимум находится из решения простой задачи на минимум функции

Интеграл в правой части — постоянная, а максимум находится из решения простой задачи на минимум функции

2 1п^ + 3*^"С»1п8Р + 3)2 1п^ + 3*^"С»1п8Р + 3)Нг+Ч^).Нг+Ч^).

2 1п^ + 3*^"С»1п8Р + 3)

2 1п^ + 3*^"С»1п8Р + 3)

Нг+Ч^).

Нг+Ч^).

где z меняется от 1 до оо. Этот минимум достигается при

2 2 z = (18c0)10ln10x,2 2 z = (18c0)10ln10x,и мы получаем неравенствои мы получаем неравенствоyin (74"3) 4~iyin (74"3) 4~iIn х о In9 (^4-3)In х о In9 (^4-3)

2 2 z = (18c0)10ln10x,

2 2 z = (18c0)10ln10x,

и мы получаем неравенство

и мы получаем неравенство

yin (74"3) 4~i

yin (74"3) 4~i

In х о In9 (^4-3)

In х о In9 (^4-3)

i г Д91——

>|[ОЧ)1° + Ч (18r0) -iojlniox^aln10^ a>0.

Отсюда уже окончательно следует неравенство 1

. 10

(35)(35)(36)(36)1 I С Г (5, X) x5+1/ л 2 ”aln

(35)

(35)

(36)

(36)

г

где Л5 — постоянная и a > 0 — постоянная.

Итак, мы пришли к теореме.

Теорема 1.

с1

^U, z)=H(z-z)^=7'+0(^' п ^’

2

( 12

т=№ 1=ь’

0. ZT^Zo-,

и ф(х, z)= 2 A(«)z(«), а a>0— постоянная.

Пусть I ^1 и т ^ 1 —целые числа, (/, т) = 1. Если tn = 1, то и 7=1. Введем в рассмотрение функции

ф (х; 7, т) =2 A (/z), ф1 (х; /, т) = f ф (7; 7, т^ dt. (37)

4nsZ(modw)2

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

Szt^^^- z)= 2 а (л) 5 z(”) 7(0=

Zп^х X

= (р (/п)2 A (zz) = (р (/zz) ф (х; 7, /zz),

n=l (mod w)

откуда

ф(х;7,/^^^(ОШ X). '

1I (38)

где (р (zzz) — функция Эйлера, у (/) — характер комплексно-сопряженный у(/) и суммы берутся по всем характерам mod//?. Пользуясь соотношениями (36), сразу получаем, что

фДх;/, 7п) = -^Ф(х,х0) + 2 Х^Ф^, Х) =

V 4X 7= Zo

= н—-у—г-—(-О (х2^-”ln'° )•(39)

2ср (т) 1'

Благодаря тому что функция ф (х; /, zzz) — неотрицательная монотонно неубывающая, можно легко перейти от оценки ф! (х; /, zzz) к оценке ф (х; /, zzz). Для этого может служить общая лемма.

Лемма VIII. Если ф(х)— неотрицательная монотонно неубывающая функция и имеет место соотношение

X

ф, (х) = ^ ф (х) dx = ах1 -|- О (х2^- ’11,7 х),(40)

2

я>0, а>0, 1^у>0, то

ф (х) = 2ах 4- О ^хе 2 П*).(41)

Доказательство. Пусть 1 > 6 ^у . Тогда из условия (40) имеем, что

X

ф, (х) — ф, (Ох) = ^ ф (/) dt = ах2 (1 — О2) 4- О (х2^~а 1ПТ*), (42) так как

In7 6х= [In х4- In О]7 = In7 х ^1 4-у^У == In7 х4* О (1).

Из этого соотношения следует, в силу положительности и монотонного неубывания ф(/), что

или, деля на х(1—0), что

ф (х) > 2ах — а (1 — 0) х — хе-а 1п7х,(43)

где Л6 > 0 — постоянная.

Совершенно так же из соотношения (42), если в нем заменить х на у, следует, что

X

j ф (О at=х2 (1 — о2) + о (х2^",п XY

откуда уже следует неравенство

Ц^хф(х)<-^(1 — 02)х24-О(х2е~«1пГх).

тт

Далее, деля на —^—х, получаем, что

ф(х)<2ах + яЦ^х4-Д7 у^г?-’1"^ ,(44)

где Л7>0 — постоянная. Из неравенств (43) и (44) уже следует, что

|ф(х)— 2ах|<у (1 —6) х +^“^У7е-”1ПХ х.

Полагая теперь

мы получаем, чтомы получаем, что- - In Xе 1

мы получаем, что

мы получаем, что

|ф(х) — 2ах|< p + 4e4-047jxe 2 *

другими словами, получаем неравенство, эквивалентное соотношению (41). Из соотношения (39) и леммы VII непосредственно следует

Теорема II. Если I и т — целые положительные числа и т^ \, (jn, 1^=1, тоt

Ф(х;/,т)=^AW = ^)x + °Ue 2“ % (45)

п ss I (mod т^

71 С*

где <р (/п) функция Эйлера, ср ^т^ = 1, tn — 1, а > О постоянная.

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

Из соотношения

<11Н=

р^ г l (mod /я)р^ г l (mod /я)p = l (mod /я)p = l (mod /я)£ 1П”

р^ г l (mod /я)

р^ г l (mod /я)

p = l (mod /я)

p = l (mod /я)

п = I (mod /я)

р%= I (mod т)

[

In xl

1^2 , так как

^21 ^п(х2)—{—... —|— тг (х?°) < 2х21п х,

7=2 p*l = l (mod /я) рЧ <с х

где п (х) число простых чисел, меньших х, следует, что

л (%;/,«)=51=2^4-O(x4nx). (46)

p=Z(mod«)Т 1п(л) '/ V J

р ^ хn = l (mod ля)

Далее, полагая ^=[x], будем иметь, что

22 ^[Ф^А «) —Ф («— 1; A^W

2 ^ я ^ х П2^ я ^х^ п

п = I (mod ля)

In N "Т" ^2 Ф ( ’ > [in л In (л 4- 1)]

2

г М N— 1 г 11 1а , 10

=4-JA+s «[А—1, L.J ч-о(^~^ *)+ср (т) [In N 1 [1пл ln(«+l)J 1 vz 1

1п2 1 J 1пх^ 2

откуда

2J^x lnzz

и при

q — Ne

£

n j— 2. щ10 пq 1

2 n?v=2 ^

■^, iC ^

In nJ In X *

2

=jm+0(D 2

t^ N

, л^=И,

£ a 10 "2

Легко видеть, что имеют место оценки

так как

ln10<7= ln^— yln'^l

Отсюда следует, что

XI л (") — С

££

х 1 Ю1« . 10 ..

т1п п1 АГ ~т 1п N Г

■<2" Ne+

££

a , 10a , 10

!п дг_in х

~Ne 2< хе 2, х > х0,

££

10— Г»--"I10

= lnW 1 — ~1п 10 ^=±

= ln’0^4-o(l).

£

/a 110\

^.Д_п/^"1ЯХ\(47

Теорема III. Если п(х; I, т^— число простых чисел

р^х и p = l (шйт), (I, т)—\. т^1, то

X, а 10 х

р dt 1( ~■ п* ^ х \

и (х; I, т^ = \ ^— -j- О ( хе к(48)

\/

где а — некоторая постоянная.

Эта теорема непосредственно следует из соотношений (46) И (47).

Мы доказали, таким образом, теорему о числе простых чисел в натуральном ряде и арифметической прогрессии с остаточным членом типа Адамара — Валле-Пуссена, в кото-

„1

ром получили аналогичную оценку с заменой у на ^ .

ЛИТЕРАТУРА

A. Brauer, On the Exact Number of Primes below a given Limit, Amer. math. Month. 53, 521—523 (1946).

R. Breus ch, Zur Verallgemeinerung des Bertrandschen Postulates, das zwischen x und 2x stets Primzahlen liegen, Math. Z. 34, 505—526 (1931).

V. Brun, Le crible d’Eratosthene et le theor^me de Goldbach., Videnskapselskapets Scrifter 1, Nr. 3 (1920). См. также Unter- suchungen fiber das Siebverfahren des Eratosthenes. Jber. DMV 33, 81—96 (1924).

P. A. С 1 e m e n t, Congruences for Sets of Primes, Amer, math Month. 56, 23—25 (1949).

L. E. D i c k s о n, History of the Theory of Numbers (Carnegie Institution, Washington, 1919).

P. Erdos, On a New Method in Elementary Number Theory which leads to an Elementary Proof of the Prime Number Theorem, Proc. nat. Acad. Sci. USA 35, 374—384 (1949).

P. E r d 6 s, Some Applications of Brun’s Method, Acta sci. math. Szeged 13, 57—63 (1949).

P. F i n s 1 e r, Uber die Primzahlen zwischen n und 2л, Speiser- Festschrift (Orell-Fussli, Zurich, 1945).

A. E. I n g h a m, The Distribution of Prime Numbers (Cambridge University Press, London, 1932). (Есть русский перевод: Ингам А. Е., Распределение простых чисел. Перев. q англ. Д. А. Райкова с приложением статьи переводчика «О методе Ландау — Икеара доказательства асимптотического закона распределения простых чисел», 1936, ОКТИ).

К- Iseki und Т. Tatuzawa, On Selberg’s Elementary Proof of the Prime Number Theorem, Proc. Japan. Acad. 27, 340—342 (1951).

H. Ishikawa, Uber die Verteilung der Primzahlen, Sci. Rep. Tokyo Bunrika Daigaku [A] 2, 27—40 (1934).

Е. Landau, Handbuch der Lehre von der Verteilung der Prim- zahlen (B. G. Teubner, Leipzig, 1909).

D. H. Lehmer, Guide to Tables in the Theory of Numbres (National Research Council, nat. Acad. Sci. Washington, 1941).

D. H. L e h m e r, A. Factorization Theorem applied to a Test for Primality, Bull. Amer. math. Soc. 45, 132—137 (1939).

D. H. Lehmer, On Lucas’s Test for the Primality of Mersenne’s Numbers, J. London math. Soc. 10, 162—165 (1935).

P. M a e n n c h e n, Zerlegung grosser Zahlen, Unterrichtsbl. Math. Naturwiss. 44, 84—92, 112—122 (1938).

T. N a g e 1 1, Introduction to Number Theory (Almquist & Wiksell, Stockholm, 1951).

O. Ore, Number Theory and its History (McGraw-Hill, New York, 1948).

H. E. Richert, Ober Zerfallungen in ungleiche Primzahlen, Math. Z. 52, 342—343 (1941).

B. R о s s e r, The /z-th Prime is greater than n log n. Proc. London. math. Soc. 45, 21—44 (1938).

B. Rosser, Explicit Bounds for some Functions of Prime Numbers, Amer. J. Math. 63, 211—232 (1941).

A. S e 1 b e r g, An Elementary Proof of the Prime Number Theorem, Ann. Math. 50, 305—313 (1949).

A. S e 1 b e r g, On an Elementary Method in the Theory of Primes, Norske Videnskab. Selskab. Forh. 19, Nr 18 (1947).

A. Sei berg, The general sieve Method and its Place in Prime Number Theory, Proc. int. Congr. Math. Cambridge, Mass. 1, 286—292 (1950).

H. N. Shapiro, On Primes in Arithmetic Progressions, II, Ann. Math. 52, 231—243 (1950).

H, N. Shapiro. On the Number of Primes less than or equal x, Proc. Amer. math. Soc. 1, 346—348 (1950).

W. Sierpinski, Sur 1’existence de nombres premiers avec une suite arbitraire de chiffres initiaux, Le Matematiche (Catania, 1951).

R. Steuerwald, Uber die Kongruenz 2n“1 ^ 1 (mod /г), Sitz- Ber. math. Naturw. KL Bayer. Akad. Wiss., Miinchen, 1947, 177.

H. S. U h 1 e r, A. Brief History of the Investigations on Mersenne Numbers and the Latest Immense Primes, Scripta math. 18, 122—131 (1952).

J. W a r g a und H. N. Shapiro, On the Representations of Large Integers as Sums of Primes, Comm, pure appL Math. $ 153—176 (1950).

Е. М. Wright, A Prime-representig Function, Amer. math. Month. 58, 616—618 (1951).

E. Z e r m e 1 о, Elementare Betrachtungen zur Theorie der Prim- zahlen, Nachr. Ges. Wiss. Gottingen [NF] Nachr. Math. 1, 43—46 (1934).

А. А. Б у x ш т а б, Асимптотическая оценка одной общей теоретико-числовой функции, Матем. сб. 2 (44) (1937), 1239—1246.

А. А. Б у х ш т а б, Новые улучшения в методе эратосфенова решета, Матем. сб. 4 (46) (1938), 375—387.

А. А. Б у х ш т а б, О разложении четных чисел на сумму двух слагаемых с ограниченным числом простых множителей, ДАН 29 (1940), 544—548.

А. А. Б у х ш т а б, Об одном аддитивном представлении целых чисел, Матем. сб. 10 (52) (1942), 87—91.

А. А. Бухштаб, Об одном соотношении для функции к (х), выражающей число простых чисел, не превосходящих х, Матем. сб. 12 (54) (1943), 152—160.

А. О. Г е л ь ф о н д, Об одном элементарном подходе к некоторым задачам из области распределения простых чисел, Вестник МГУ, № 2, 21—26 (1953).

А. О. Г е л ь ф о н д, О разбиении натурального ряда на классы группой линейных подстановок, ИАН, сер. мат., т. 18,297—306 (1954).

А. О. Г е л ь ф о н д, Об арифметическом эквиваленте аналитичности /.-ряда Дирихле на прямой Re 5=1, ИАН, сер. мат., № 20, 145—166 (1956).

Ю. В. Линник Большое решето, ДАН 30 (1941), 290—292.

А. Г. Постников и Н.П. Романов, Упрощение элементарного доказательства А. Сельберга асимптотического закона распределения простых чисел, Успехи матем. наук X, 4 (66), 75—87 (1955).

Н. П. Романов, О некоторых теоремах аддитивной теории чисел, Успехи матем. наук 7 (1940), 47—56.

В. А. Тартаковский, О некоторых суммах типа Viggo Brunn’a, ДАН 23 (1939), 122—126.

В. А. Тартаковский, Метод избирательного приближенного решета, ДАН 23 (1939), 127—130.

А. Я. X и н ч и н, О сложении последовательностей натуральных чисел, Матем. сб. 6 (48) (1939), 161—166.

И. В. Чулановский, Некоторые оценки, связанные с новым методом Selberg’a в элементарной теории чисел, ДАН 63 (1948), 491-494.

Л. Г. Ш н и р е л ь м а и, Об аддитивных свойствах чисел, Ростов н/Д, Изв. Донск. политехи, инет. 14 (2—3) (1930), 3—28.

Л. Г. Шнирельман, Uber additive Eigenschaften von Zahlen, Math. Ann. 107 (193 3), 649—690.

Л. Г. Шнирельман, On addition of sequences and sets., Матем. сб. 5 (47) (1939), 211—215.

Л. Г. Шнирельман, Простые числа, М.—Л., Гостехиздат, 194 0, 1—59.

Л. Г. Ш нирельман, О сложении последовательностей, Успехи матем. наук 7 (1940), 62—63.

ЛИТЕРАТУРА К ПРИЛОЖЕНИЮ

Н. Г. Чудаков, On zeros of Dirichlet’s /.-functions, Матем. сборн. 1 (43): 4 (1936), 591—602;

H. M. К о p о б о в, О нулях функции С (5), ДАН СССР 118, № 3 (1958), 431-434.

И. М. Виноградов, Новая оценка функции C(14-zY)> Изв, АН СССР, сер. матем., № 2, т. 22 (1958), 161—164;

Н. М. Коробов, Оценки тригонометрических сумм и их приложения, Успехи мат. наук XIII, вып. 4 (82) (1958).

Трост Эрнст

Простые числа

Редактор Л. А. Коноплянкин

Техн, редактор В. Н. КрючковаКорректор А. С. Каган

Сдано в набор 29/Х 1958 г. Подписанок печати 31/ХП 1958 г. Формат 84X108 32-Физ. печ. л. 4,25. Условн. печ. л. 6,97.

Уч.-изд. л. 7,10. Тираж 15000 экз. Т115 77.

Цена 2 р. 15 к. Заказ 2408.

Государственное издательствофизико-математической литературыМосква, В-71, Ленинский проспект, 15.

Первая Образцовая типографияимени А. А. ЖдановаМосковского городского Совнархоза.

Москва, Ж-54, Валовая, 28.

Цена 2 р. 15 к.

Л01 арифм.

>у2>0, так что (xxx2~V уху^2 больше остальных трех квадратов.

*) За 20 следующих шагов доходят до х < 20.

2) Этот параграф дает некоторые сведения об аналитической

теории простых чисел.

9 Другие доказательства дали Линник и Чудаков. Легко доступ

ное изложение имеется в книге: Т. Estermann, Introduction to mo

dern prime number theory (Cambridge Tracts № 41, Cambridge Uni

ELEMENTE DER MATHEMATIKVOM HOHEREN STANDPUNKT AUS