Текст
                    DIE GRUNDLEHREN
DER MATHEMATISCHEN WISSENSCHAFTEN
Band 148
K. CHANDRASEKHARAN
INTRODUCTION TO ANALYTIC
NUMBER THEORY
SPRINGER-VERLAG
Berlin Heidelberg New York 1968


К. ЧАНДРАСЕКХАРАН ВВЕДЕНИЕ В АНАЛИТИЧЕСКУЮ ТЕОРИЮ ЧИСЕЛ Перевод с английского С. А. СТЕПАНОВА Под редакцией А. И. ВИНОГРАДОВА ИЗДАТЕЛЬСТВО «МИР» МОСКВА 1974
УДК 511 Книга известного индийского математика, президен- президента Международного математического союза К. Чандра- секхарана посвящена систематическому изложению классических результатов аналитической теории чисел. Она не требует больших предварительных знаний и вво- вводит читателя в широкий круг основных теоретико-чис- теоретико-числовых вопросов. Книга написана с большим педагогическим мастер- мастерством, четко и сжато. Она будет полезна математикам различных специальностей, а также студентам универси- университетов и пединститутов. Редакция литературы по математическим наукам ПППЛО Г\4 q Ч — — 13-74 (g) Перевод на русский язык, «Мир», 1974
ПРЕДИСЛОВИЕ К РУССКОМУ ИЗДАНИЮ Эта книга предназначается для студентов старших курсов и призвана служить введением в ту простейшую область аналитической теории чисел, которая в основ- основном восходит к знаменитой теореме Дирихле 1837 года о бесконечности множества простых чисел в арифметиче- арифметической прогрессии. Никакого предварительного знакомства с элементарной теорией чисел не предполагается. Автор испытает чувство глубокого удовлетворения, если это русское издание, любезно подготовленное А. И. Виноградовым и С. А. Степановым, заинтересует студентов в Советском Союзе, который является роди- родиной выдающихся специалистов по теории чисел. 21 марта 1973 г. К. Чандрасекхаран
ПРЕДИСЛОВИЕ Эта книга возникла на основе курса лекций, прочи- прочитанных мною в Высшей технической школе в Цюрихе. Записи лекций, подготовленные в основном моими ас- ассистентами, были опубликованы. Настоящая книга сле- следует тому же общему плану, что и эти записи, однако и по стилю изложения (см., например, гл. III, V и VIII), и по степени подробностей они сильно различаются. Цель книги — познакомить неспециалистов с некоторы- некоторыми основными результатами теории чисел, показать, как в теории чисел используются аналитические мето- методы, и подготовить почву для последующего изучения более тонких вопросов. Книга опубликована в серии «Die Grundlehren der mathematischen Wissenschaften» благодаря интересу, проявленному к ней профессором Бено Экманом. Я считаю своим долгом выразить признательность профессору Карлу Людвигу Зигелю, который прочитал рукопись и корректуру и сделал много ценных замеча- замечаний и предложений. Профессор Рагхаван Нарасимхан неоднократно помогал мне сделать изложение более яс- ясным и доступным. Доктор Гарольд Даймонд прочитал корректуру и помог устранить некоторые неточности. Я считаю себя обязанным выразить им свою благо- благодарность. К. Ч.
ГЛАВА I ТЕОРЕМА ЕДИНСТВЕННОСТИ РАЗЛОЖЕНИЯ НА ПРОСТЫЕ СОМНОЖИТЕЛИ § 1. Простые числа. Мы предполагаем известными положительные целые числа 1, 2, 3, ..., отрицательные целые числа —1, —2, —3, ... и нуль, который мы будем считать целым числом. Под неотрицательными целыми числами подразумеваются положительные целые вме- вместе с нулем. Мы предполагаем известными также эле- элементарные арифметические операции над целыми чис- числами. Мы говорим, что целое число а делится на целое ЬФО, если существует такое целое с, что а = Ьс. При этом мы будем говорить, что Ь делит а, или b есть де- делитель а, и записывать это так: Ь\а. Мы будем также называть а целым кратным или просто кратным числа Ь. В случае когда Ь не делит а, мы будем писать bJ Легко проверить следующие свойства: b 0 &0 l& рр у если ban а>0, &>0, то если b а и с\Ь, то с\а\ если b а и сфО, то Ьс\ас\ если с а и с\Ь, то с\ (ma+nb) при всех целых пг и п. Если заданы целые числа а и 6, ЬфО, то одно- однозначно определяются такие целые числа q и г, что а = = bq-\-r и 0^г<|6|. Назовем q частным, а г остатком при делении а на Ь. Ясно, что если Ь\а, то г=0. Целое число р>\ называется простым, если все его положительные делители исчерпываются числами 1 и р. Целые числа, большие 1 и не являющиеся простыми, называются составными. В этой главе мы докажем, что каждое целое число, большее 1, можно разложить в произведение простых чисел и что такое разложение единственно с точдостью до порядка следования сомножителей. Кроме того, мы докажем, что существует бесконечно много простых чисел.
Гл. I. Теорема единственности § 2. Теорема единственности разложения на простые сомножители. Теорема 1. Каждое целое число п, большее едини- единицы, разлагается в произведение простых чисел. Доказательство. Число п является или простым, или составным. В первом случае утверждение теоремы оче- очевидно. Если п составное, то по определению существует такое целое число d, что \<d<n и d\n. Пусть m — наименьшее из таких делителей. Покажем, что m долж- должно быть простым числом. Если бы m не являлось про- простым, то можно было найти такое целое число k, что 1<&<га и k\m. Отсюда следовало бы, что 1<&< <^пг и k\n, а это противоречит выбору т. Полу- Полученное противоречие показывает, что т действительно является простым числом, и мы обозначим его через р\. Таким образом, мы можем считать, что п = р\Г, где 1<г<я. Применяя те же рассуждения к числу г, мы получим, что n = pip2s, где р2^Р\ и 1^5<г<м. Этот процесс оборвется после конечного числа шагов, так как между 1 и п имеется только конечное число целых чисел. В результате мы получим разложение п = рхр2...ри где Pi<p2^~.<Pt, A) и тем самым завершим доказательство теоремы. Заметим сразу же, что если n = ab, то а и b не могут быть одновременно больше, чем УТь. Отсюда следует, что любое составное целое п имеет простой делитель /?, не превосходящий У~п'. Объединяя в представлении A) равные простые числа и меняя, если это необходимо, нумерацию, мы мо- можем переписать равенство A) в виде где pi<p2<...<pk и аг>0 для i=l, 2, ..., k. Представ- Представление числа п в виде B) мы назовем его каноническим разложением. Теперь мы в состоянии доказать теорему единствен- единственности разложения на простые сомножители, которая на- называется также основной теоремой арифметики:
§2. Теорема единственности Теорема 2. Каноническое разложение целого числа п, большего единицы, единственно. Мы дадим три доказательства этой теоремы. Первое доказательство использует только теорему 1. Второе свя- связано с решением в целых числах линейных уравнений, а третье использует теорию последовательностей Фарея, Первое доказательство теоремы 2. Каноническое разложение простого числа, очевидно, единственно. Пусть некоторые положительные целые числа, боль- большие 1, имеют два различных канонических разложения, и пусть N— наименьшее из таких чисел, причем Каждое р отличается от каждого q, так как любое про- простое, общее для обоих представлений, при делении N на пего давало бы целое число N'<cN, которое обладает тем же свойством, что иЛ/, а это невозможно в силу вы- выбора N. Мы можем предположить, что Кроме того, поскольку рхФЦ\, мы можем считать, что pi<Cq\. Определим число P = pxq2...qm. Из условий р\\Р и pi\N следует, что p\\(N—Я), где N—P=(qx—p\)q2"-qm>\- Поэтому мы можем записать N- Р = М..Л, C) где U, i=l, 2, ..., А,— простые числа. Если q\—Pi>l, то мы можем также записать q\—р\ в виде произведе- произведения простых чисел: Тогда мы получим другое представление Af—Р в виде произведения простых чисел, а именно N—P = rlr2...rsq2...qm. D) Мы видели, что ни одно р не равно какому-либо q. В ча- частности, р\ не равно никакому q. Далее, ясно, что Pi'f (^i—Pi) у и тогда р\ не равно никакому г, так что qx—рх в разложении на простые сомножители не может содержать рь Таким образом, число Af—Р имеет два различных разложения C) и D) на простые сомножите-
10 Гл. I. Теорема единственности ли. То же самое справедливо и в случае, когда q\—р{ = = 1. Но K.N—P<.N, а это противоречит минимально- минимальности N. Следовательно, не существует целых чисел д>1, имеющих более одного канонического разложения. § 3. Второе доказательство теоремы 2. Доказатель- Доказательство основывается на решении в целых числах некото- некоторых линейных уравнений. Введем некоторые новые по- понятия. Пусть а и Ь — целые числа, не равные одновременно нулю. Их наибольший общий делитель, который обозна- обозначается через (а, 6), определяется как наибольшее поло- положительное целое число, которое делит одновременно а и Ь. Если (а, 6) = 1, то мы будем говорить, что а и Ь — взаимно простые целые числа. Мы покажем, что если (a, b) = d, то уравнение ax-\-by = d разрешимо в целых числах х и у. Отсюда следует, что если р про- простое и p\ab, то р\а или р\Ь. Из последнего факта в свою очередь вытекает теорема единственности разложения на простые сомножители. Непустое множество целых чисел S, обладающее свойством S и n^Sz$ m— называется модулем. Из определения следует, что если m, n^S, то Другими словами, если aeS, b(=S, то ax+by<=S при лю- любых целых х и у. Если модуль состоит только из нуля, мы будем называть его тривиальным модулем. Нетриви- Нетривиальный модуль содержит, очевидно, бесконечно много положительных и отрицательных целых чисел. Мы мо- можем сказать даже несколько больше: Теорема 3. Каждый нетривиальный модуль S состоит из всех целых кратных некоторого положительного це- целого числа. Доказательство. Так как S — нетривиальный мо- модуль, он содержит некоторые положительные целые чис- числа. Пусть d — наименьшее такое целое число. Тогда 5 содержит все целые кратные числа d. Для того чтобы
§ 3. Второе доказательство теоремы 2 11 показать, что ими исчерпываются все элементы S, возь- возьмем любое n^S. Мы можем представить п в виде п = = dk + c, где k и с — целые и 0^c<d. Так как d^S, то и dk^S. Далее, поскольку n^S, мы имеем п—dk^S, так что c<=S. Но c<d, ad — наименьшее положительное це- целое в модуле S. Следовательно, с = 0 и п есть целое крат- кратное числа d. Отсюда мы получаем следующую теорему: Теорема 4. Для данных целых а и b модуль S = = {ах+Ьу}, где х и у — целые числа, представляет со- собой множество всех целых кратных числа d=(a, b). Доказательство. Легко видеть, что множество S яв- является модулем. Из теоремы 3 следует, что S есть мно- множество всех целых кратных некоторого положительного числа е. Следовательно, е делит все элементы множест- множества S; в частности, е\а и е\Ь. Так как d есть наибольший общий делитель чисел а и 6, то e^d. С другой стороны, d\ (ax-{-by) при всех х, у, так что d делит каждый эле- элемент из S. В частности, d\e. Следовательно, d^.e. Та- Таким образом, e = df что и доказывает теорему. Ясно, кроме того, что справедлива следующая тео- теорема: Теорема 5. Уравнение ах-{-Ьу=п разрешимо в целых числах х и у тогда и только тогда, когда {а, Ь) \п. Следствие 1. Если (a, b) = df то уравнение ах-{-Ьу = = d разрешимо в целых числах х и у. Другими словами, наибольший общий делитель целых чисел а и b является их линейной комбинацией с целыми коэффициентами. Следствие 2. Любой общий делитель целых чисел а и b делит (а, Ь). Из этих результатов теперь легко выводится Теорема 6 (Евклид). Если а\Ьс и (а, 6) = 1, то а\с. Доказательство. Так как (а, &) = 1, то существу- существуют такие целые числа х и у, что ах-\-Ьу = \. Если мы ум- умножим последнее равенство на с, то получим асх-\-Ьсу =
12 Гл. I. Теорема единственности = с, и так как а\Ъс, то а\ (асх + bcy). Следовательно, а\с. г Следствие. Если р — простое число и р| Д piy где ка- ждое pi, i = l, 2, ..., г, также простое число, то р=р% по меньшей мере для одного L Мы можем теперь дать Второе доказательство теоремы 2. Предположим, что целое число N имеет два различных канонических разложения Тогда рх\ q\i q$2- - -q$r и, следовательно, в силу следствия теоремы 6 p\ = q\ для некоторого i, l^i^ir. Аналогично мы получаем, что каждое р равно некоторому q и каж- каждое q равно некоторому р. Таким образом, k = r и, так как оба разложения упорядочены по возрастанию сом- сомножителей, мы имеем где р\<Р2<~-<Ри. Покажем, что оц = ${ для всех i = = 1, 2, ..., k. Если бы мы имели, например, (Хг>|3г Для некоторого i, мы получили бы после деления на pft равенство И\ • • 'Hi • • -Hk —H\ • • 'Hi—l Hi+l • • 'Hk » в котором левая часть делится на р\, а правая нет, что невозможно. Аналогично невозможен и случай щ<С$г. Следовательно, аг = |3г Для всех i, и потому каноническое разложение единственно. § 4. Наибольший общий делитель и наименьшее об- общее кратное. С понятием наибольшего общего делите- делителя целых чисел а и 6, данным в § 3, тесно связано по- понятие наименьшего общего кратного. Определение. Наименьшее общее кратное {а, Ь} двух целых чисел а и Ь, где аЬфО, есть наименьшее положи-
§4- Наибольший общий делитель и наименьшее общее кратное 13 тельное целое число, которое делится одновременно на а и Ь. Соотношение между (а, Ь) и {а, Ь}, где а6>0, выра- выражается тождеством ab = (a, 6). {а, Ь). E) Для доказательства рассмотрим целое число \i = ab/ (a, b). Так как (а, Ь)\Ь, то jli есть целое кратное а. Подоб- Подобным же образом [i есть целое кратное Ь. Тогда \х будет общим кратным а и Ь. Пусть v — какое-либо другое об- общее целое кратное а и Ь. Рассмотрим число v v-(а, Ъ) "JT ~~ ab Мы знаем, что (a, b)=ax-{-by при некоторых целых х и у. В таком случае + ул: . vy Ь а \i ab Ь а Но v/a и v/й являются целыми числами и, следовательно, \/\i также будет целым числом. Таким образом, любое общее целое кратное чисел а и Ь есть целое кратное чис- числа jli. Значит, jli будет их наименьшим общим кратным и Попутно мы показали, что наименьшее общее крат- кратное а и Ь делит любое общее кратное этих чисел. Если а — положительное целое, то мы можем запи- записать, что где произведение распространяется на все простые чис- числа, а а есть неотрицательные целые числа, которые, за исключением конечного числа значений р, равны нулю. Если простое число р не делит а, то соответствующий по- показатель а есть нуль. Подобным же образом мы имеем ь=Лр*, Р>о. Легко видеть, что (а, Ь) = ПРШ1П [а'Р], [CL, Ь\ =
14 Гл. I. Теорема единственности § 5. Последовательности Фарея. Если А и k — целые числа и &>0, мы назовем h/k дробью с числителем А и знаменателем k. Дробь h/k называется несократимой, или сокращенной, если (A, ft) = l. Дробь А/& называется правильной, если O^.h/k^.1. Последовательность Фарея порядка п, где /г — поло- положительное целое, — это последовательность Fn всех не- несократимых правильных дробей h/k, у которых l^k^n, расположенных в неубывающем порядке. Например, Fs есть последовательность JL_L_LJLJL_LJLJiiL±_L 1 * 5 ' 4 ' 3 ' 5 ' 2 ' 5 ' 3 ' 4 ' 5 ' 1 ' Члены последовательности Фарея какого-либо поряд- порядка называются дробями Фарея. Заметим, что каждое ра- рациональное число т/п, такое, что 0^.т/п^1, равно не- некоторой дроби Фарея. Из теоремы единственности разложения на простые сомножители (теорема 2) следует, что несократимая дробь единственна. Другими словами, две равные меж- между собой несократимые дроби должны совпадать. Одна- Однако мы не хотим использовать теорему 2 и поэтому долж- должны допустить возможность того, что две дроби Фарея могут быть равны между собой, но не совпадают. В этом случае мы упорядочим их по возрастанию числителей. Следующая теорема фактически исключает такую воз- возможность и подготавливает почву для третьего доказа- доказательства теоремы 2: Теорема 7 (Фарей — Коши). Если l/m непосредствен- непосредственно следует за h/k в последовательности Фарея FN, то kl—hm=\. Доказательство. Непосредственной проверкой мож- можно убедиться, что результат справедлив для FN при 1^Л^5. Предположим, что результат справедлив для FN, и докажем его для FN+i. Пусть а/Ь — несократимая правильная дробь, не принадлежащая FN. Тогда b^N-\-l и дробь а/Ь должна лежать между некоторыми двумя последовательными дробями h/k и l/m в последовательности Фарея FN,
§5. Последовательности Фарея 15 скажем А. <¦— < — k Ь т где знак равенства допускается ввиду того, что единст- единственность несократимой дроби не предполагается. Опре- Определим целые числа % и [i следующим образом: %=ka—hb, ii=bl—am. Тогда Х^О, [х^О и Я+jwX), так как мы предположили, что теорема справедлива для последовательности Fn, ко- которой принадлежат дроби h/k и 1/т. Далее, по предпо- предположению индукции kl—hm=\, и тогда lkl-{-\xh=kal—ham — a(kt—hm) =a. Аналогично, Хт + \kk = b, G) и поскольку (а, 6) = 1, мы имеем (X, ц) = 1. Таким обра- образом, если h/k^a/b^l/m, (a, &) = 1, то О Л/72 + \lk Обратно, если X и |ы — целые числа, такие, что ^, jli^O, Я+|ы>0, (X, ц) = 1, и мы определим а и b равен- равенствами а=Х1+\хку b = 'km-{-ixk, то однозначно Х= =Ла—hb, [i—bl—am и (а, 6) = 1, так что дробь а/Ь не- несократима. Кроме того, из равенства kl—hm=\ следует, что h/k^a/b^llm. Таким образом, а/Ь принадлежит FM для некоторого М. Так как &>0, т>0, (X, jli) = 1, то мы видим также, что b^m+k только в трех случаях X, jli=O, 1; 1, 1; 1, О, которые приводят соответственно к значениям а, 6 = = А, k; l+h, m + k; /, m. Далее, Х=^0. Действительно, ес- если бы Х=0, то дробь a/b=(iih)/(iik) не была бы несо- несократимой, за исключением случая [х=1. В последнем же случае, согласно равенству G), мы имели бы b = k, что противоречит предположению о том, что b^N+\>k. Подобным же образом jli^O. Следовательно, b^m-\-ky только если Х=|ы=1. Мы имеем b^N+l, и если
16 Гл. I. Теорема единственности (a/b)<=FN+u то b = N+l. Далее, поскольку h/k и 1/т яв- являются последовательными членами в FN, 1+1 и потому m+k^N+l. Отсюда вытекает, что если 6 = = Af+l, то Я=1 и \х=1. Следовательно, и дробь а/6, очевидно, удовлетворяет теореме относи- относительно соседних дробей h/k и 1/т, так как по предполо- предположению индукции для FN мы имеем kl—hm=\. Таким образом, если теорема справедлива для FN, то она спра- справедлива и для Fjv+i, и поскольку теорема справедлива для Fu то она справедлива для всех Fn. Из теоремы 7 следует, что несократимая дробь един- единственна. Определение. Дробь (h-{-l)/(k-{-m) называется медиантой дробей h/k и l/tn. При доказательстве теоремы 7 мы показали неявным образом, что медианта двух дробей Фарея снова яв- является дробью Фарея, а также доказали следующий ре- результат: Теорема 8. Дроби, принадлежащие FN+\, но не при- принадлежащие FNj являются медиантами соседних дробей из FN. Из теоремы 7 вытекают также следующие утверж- утверждения: Теорема 9. Если h/k, h"/k", h'/kr — последовательные дроби некоторой последовательности Фарея, то h/f/kf/= {h+h')/{kk') Доказательство. По теореме 7 мы имеем kh"—hk"= = 1 и k"h!—h"k'=\\ вычитая одно равенство из другого, мы получаем требуемое утверждение. Теорема 10. Если h/k и l/m — две последовательные дроби в последовательности Фарея FN, то N
§ 6. Бесконечность мноэюества простых чисел 17 Доказательство. Так как h ^ h + I ^ I г ^ 7! ^ ' то медианта h/k и 1/т не принадлежит FN. Следователь- Следовательно, k+m^N. Наконец, мы докажем следующую теорему: Теорема П. Если jV>1, to в FN нет двух последова- последовательных дробей с одним и тем же знаменателем. Доказательство. Пусть k>\. Если h'/k непосредст- непосредственно следует за h/k в FN, то /i+l^ft^fe, и мы име- имели бы k k~l k ^ k Таким образом, h/(k—1) будет лежать между h/k и h'/k в последовательности FN, что противоречит наше- нашему предположению о дробях h/k и h'/k. Третье доказательство теоремы 2. Мы можем ис- использовать теперь наши знания о последовательностях Фарея для доказательства того, что уравнение ах-\-Ьу— = 1, где (а, й) = 1, разрешимо в целых числах х, у. Как мы уже видели, отсюда следует справедливость теоре- теоремы 2. Так как утверждение очевидно, если ab = 0 или а = Ь, предположим, что 6>а>0 и (а, й) = 1. Рассмотрим дробь а/Ь. Мы можем считать ее членом некоторой по- последовательности Фарея, например F&. Пусть дробь а/Ь непосредственно следует за h/k в этой последовательно- последовательности. Тогда по теореме 7 имеем ka—hb=l, так что x=k и у = —h дают решение уравнения ax + by=l. § 6. Бесконечность множества простых чисел. Мы получили три различных доказательства теоремы един- единственности разложения на простые сомножители. Дока- Докажем теперь, что простых чисел бесконечно много. Теорема 12 (Евклид). Существует бесконечно много простых чисел.
18 Гл. I. Теорема единственности Мы дадим два различных доказательства этой тео- теоремы. Первое доказательство принадлежит Евклиду, а второе — Г. Пойа. Третье доказательство, принадле- принадлежащее Эйлеру, будет дано в гл. VII, § 1. Первое доказательство теоремы 12 (Евклид). Допу- Допустим, что 2,3,5,..., р—множество всех простых чисел и р-~ наибольшее из них. Рассмотрим целое число <7=B.3-5...р) + 1. Это число не делится ни на одно простое до р включи- включительно. Но (?>1 и тогда q или само простое, большее р, или оно делится на простое число, большее р. В обоих случаях существует простое, большее р. Следовательно, простых чисел бесконечно много. Если через рп мы обозначим п-е простое число, то из сказанного следует, что Пл-Ы для некоторого т>п. Следовательно, pn+i^CpmK п <Пл + КР* + 1 прия>1. 1=1 На самом деле с помощью подобных рассуждений мы можем доказать несколько больше, а именно что причем рп< 22П~1 при я> 1. В самом деле, предположим, что Л<2, /72<22, р3<24,...,рл<22/г-1. Тогда РЛ+1<Р>Р2-Р„+ 1 <21+2+4+-+2"-1 + 1<2*\ и мы получаем требуемый результат с помощью ин- индукции. Доказательство Пойа теоремы 12 использует свой- свойства чисел Ферма. Число Ферма fn есть целое число вида
§ 6. Бесконечность мноэюества простых чисел 19 / Мы покажем, что теорема 12 являет- является следствием следующей теоремы: Теорема 13. (Пойа). Любые два различных числа Фер- Ферма взаимно просты. Доказательство. Пусть fn и fn+k(k>0) —два любых числа Ферма. Предположим, что m — такое положитель- положительное целое число, что m\fn и m\fn+k- Полагая х=22/г, мы получаем - 2 ***— 1 а*1 2k2 I 1 fn X+l так что fn\(fn+k—2). Отсюда следует, что m\(fn+k—2), и так как m\fn+k, то т\2. Но числа Ферма нечетны. Сле- Следовательно, т=\ и доказательство теоремы 13 закон- закончено. Второе доказательство теоремы 12 (Пойа). Из теоре- теоремы 13 следует, что каждое из чисел Ферма /ь f2, ..., fn де- делится на нечетное простое число, которое не делит лю- любое другое число Ферма. Следовательно, имеется по меньшей мере п нечетных простых чисел, не превосходя- превосходящих fn. Следовательно, простых чисел бесконечно много. Далее, если мы рассмотрим /о=3 при /г=0, то, по- поскольку pi = 2 и поскольку имеется по меньшей мере п нечетных простых чисел, не превосходящих fn для /г^1, мы получим, что pn+2^fn, где рп означает п-е простое. Тогда п <^0%П _L 1 причем эта оценка лучше полученной ранее. Ферма заметил, что числа /1==5, /2=17, f3=257, /4=65537 являются простыми, и предположил, что все fn также являются простыми. Однако это предположение было опровергнуто Эйлером, который показал, что f$ делится на 641. Простое доказательство последнего факта, пред- предложенное Г. Т. Беннетом, сводится к следующему: /5 = 225 + 1 = 232 + 1 = B-27L + 1.
20 Гл. I. Теорема единственности Положим 27=а и 5 = 6. Тогда /5= Bа) 4+1=24а4+1. Далее, 24=1+3& или 24=1+&(а—&3). Значит, f5=(\+ab—&4)а4+1 = A+я&)[я4+A— ab)(l+a2b2)] и, следовательно, 1+а&( = 641) делит /5. По-видимому, неизвестно, являются ли простыми ка- какие-либо другие числа Ферма, за исключением первых четырех.
ГЛАВА II СРАВНЕНИЯ § 1. Классы вычетов. Пусть a, b, m — целые числа и т>0. Мы говорим, что а сравнимо с b по модулю т, если т\ (а—Ь). Это соотношение между а, Ь и т мы бу- будем называть сравнением и обозначать символом аЕ== = &(modra). Если т\(а—&), мы говорим, что а и b не сравнимы по модулю т, и записываем это следующим образом: афЬ (mod m). Отношение сравнимости является отношением экви- эквивалентности. Действительно, оно рефлексивно, так как a=a(modm); симметрично, поскольку из a=b (mod m) следует & = a(mod#z), и транзитивно, так как из а= = b(modm) и b = c(modm) следует a=c(modm). Таким образом, отношение «=(modm)>> разбива- разбивает множество целых чисел на непересекающиеся классы эквивалентности А, В, С, ..., причем два целых числа сравнимы друг с другом по модулю т тогда и только тогда, когда они лежат в одном и том же классе. Эти классы называются классами вычетов по модулю т. Очевидно, что целые числа 0, 1, ..., т—1 лежат в раз- разных классах вычетов. Так как каждое целое число п мо- может быть записано в виде n = qm-\-r9 O^r^m—1, то каждое целое сравнимо по модулю т с одним из чисел О, 1, ..., т—1. Следовательно, имеется точно т классов вычетов по модулю т и числа 0, 1, ..., т—1 образуют множество представителей этих классов. Подобно обычным равенствам, сравнения можно складывать, вычитать и умножать. Если a=&(modm) и c=d(modm), то мы имеем a-\-c=b-\-d(mod m), а—сее= = &—d(modm) и ac=bd(modm). Действительно, если т {а—Ь) и m\(c—d)9 то т\ {{a—b)±(c—d)}. Далее, т (а—Ь)с, так что ac=bc(modт) и т\ (с—d)b, так что bc = bd(modm), откуда по свойству транзитивности ac=bd(modm). В общем случае делить сравнения нельзя. Мы имеем 2=12(modlO), но I#6(modl0).
22 Гл. II. Сравнения Пусть Л и В—два класса вычетов. Если а — произ- произвольный элемент из Л и Ъ — произвольный элемент из В, то а + b всегда лежит в одном и том же классе выче- вычетов, который мы назовем суммой А+В. В таком же смысле мы будем использовать обозначения А—В и А -В и говорить о разности и произведении двух классов вы- вычетов. Легко видеть, что классы вычетов по модулю m об- образуют относительно сложения абелеву группу. Нуле- Нулевым элементом этой группы является класс, состоящий из всех целых кратных т, а обратным к классу А явля- является класс Л', состоящий из всех элементов класса Л, взятых со знаком минус. Сравнение ах = с (mod m) эквивалентно линейному уравнению ах—ту=с, которое по теореме 5 гл. I, если (а, т) = 1, разрешимо в целых числах х, у. Решение указанного сравнения единственно, так как если axi = c(modm) и ах2= c(modm), то а{х\—x2)=0(modm), или т\а(х\—х2). Но из усло- условия (а, т) — \ следует, что т\(х\—х2), или #i = (d) Следовательно, если х0, у0 — частное решение линей- линейного уравнения ах+Ьу=п, (а, 6) = 1, то общим решением будет x=xo—bt, y=yo-\-at, где t — любое целое число. Только что полученный результат можно выразить иначе: если Л, С и X — классы вычетов по модулю т, то уравнение АХ=С имеет единственное решение X при условии, что элементы класса Л взаимно просты с т. Классы вычетов по модулю т, элементы которых взаимно просты с т, мы назовем приведенными класса- классами вычетов 1\ Они образуют абелеву группу относитель- ]) В русской литературе приведены классы вычетов принято называть классами приведенной системы вычетов. — Прим. перев.
§2. Теоремы Эйлера и Ферма 23 но умножения, единичным элементом которой будет класс, содержащий целое число 1. Каждый приведенный класс вычетов имеет обратный, так как если (а, т) = \, то существует целое а\ такое, что аа'== 1 (mod m). Рассмотрим аддитивную группу всех классов вычетов по простому модулю р. За исключением нулевого класса, все остальные классы вычетов в этом случае будут при- приведенными классами вычетов и, следовательно, образу- образуют также мультипликативную абелеву группу. Дистри- Дистрибутивный закон А• (В-\-С) =А-В-\-А-С непосредственно следует из дистрибутивного закона для целых чисел. Следовательно, справедлива следующая теорема: Теорема 1. Классы вычетов по простому модулю р об- образуют поле из р элементов. Системы вычетов. Из всех m классов вычетов по мо- модулю m мы выделили приведенные классы вычетов по модулю т. Полная система вычетов по модулю m состо- состоит из m представителей, взятых по одному из каждого класса. Следовательно, множество из m целых чисел об- образует полную систему вычетов по модулю т, если толь- только его элементы попарно не сравнимы друг с другом по модулю т. С другой стороны, полная приведенная си- система вычетов по модулю m состоит из представителей, взятых по одному из каждого приведенного класса по модулю т. Например, числа 0, 1, ..., 7 образуют полную систему вычетов (mod 8), в то время как 1, 3, 5, 7 образуют пол- полную приведенную систему вычетов (mod 8). Функция Эйлера ф. Функция Эйлера ф определяется для всех положительных целых чисел л следующим обра- образом: значение ф(я) равно количеству положительных це- целых чисел ^я, которые взаимно просты с п. Из определения следует, что значение ц>(п) равно так- также числу приведенных классов вычетов по модулю п. § 2. Теоремы Эйлера и Ферма. Если аи а2, ..., ат со- составляют полную систему вычетов по модулю т и если k взаимно просто с т, то множество ka\, ka2i ..., kam так- также будет полной системой вычетов по модулю т. Это
24 Гл. П. Сравнения сразу же следует из того, что kau ka2j ..., kam по- попарно не сравнимы по модулю т. Более общо, если (&, т) = 1 и Я — некоторое целое число, то множество kai+hy i=\, 2, ..., га, составляет полную систему вычетов по модулю т. С другой стороны, если ru r2, •••> гч>(т) есть приведен- приведенная система вычетов по модулю га и если (а, га) = 1, то числа аги аг2у ..., агф(т> также образуют приведен- приведенную систему вычетов. Следовательно, г\ • г2...гЦ}(т) = ari • аг2...агф(т) (mod m), или (а^™)—1)ггг2 .../-ф(т) =0(modm). Так как гь г2, ..., гф(Ш) взаимно просты с т, то тем самым нами доказана Теорема 2 (Эйлер). ?с/ш (а, га) = 1, то а<Р<т>= ^1 (mod т). Частный случай этой теоремы, когда пг простое, был открыт Ферма: Теорема 3 (Ферма). Если р — простое число и {а, р) = \, то аР~1 = 1 (modp). Чтобы доказать важное свойство функции Эйлера, нам потребуется следующая теорема: Теорема 4. Пусть (m, m') = l. Если а пробегает пол- полную систему вычетов по mod m и а' пробегает полную систему вычетов по mod m', то am'-\-a'm пробегает пол- полную систему вычетов по mod mm'. Доказательство. Мы имеем mm' целых чисел ат'-\- -\-а'т. Покажем, что они попарно не сравнимы по mod mm'. Пусть а[ т-\-а{т'=== а'2т-\-а2т'(mod mm'). Тогда а{т'=а2т'(mod m), откуда следует, поскольку (m, m') = l, что а\ = = а2 (mod т). Аналогично, а\ = а2 (mod m').
§2. Теоремы Эйлера и Ферма 25 Определение. Комплекснозначная функция, опреде- определенная на множестве положительных целых чисел, назы- называется арифметической функцией. Арифметическая функция / называется мультиплика- мультипликативной, если (i)/ не равна тождественно нулю; (и) из (/п, п) = \ следует, что f(mn) =f(m) -f(n). Используя теорему 4, мы можем теперь доказать следующий результат: Теорема 5. Функция Эйлера ф(/г) мультипликативна. Доказательство. Так как фA) = 1, то ф(/г) не равна тождественно нулю. Пусть (т, т') = \9 и пусть а и а' пробегают полные системы вычетов по модулям m и т/ соответственно. Тогда по теореме 4 ат'-\-а'т пробегает полную систему вычетов по mod mm'. Следовательно, ц)(тт') равна числу целых чисел вида ат'-\-а'т, удов- удовлетворяющих условию (ат'-\-а'т, тт') = \. Но послед- последнее условие эквивалентно следующим двум условиям: (ат'-\-а'т, т) = 1 и {ат'-\-а'т, т') = 1, или (ат\т) = \ и (а'т, тг) = 1, или (а, т) = \ и (а', т') = 1. Так как имеется ф(т) значений а, для которых (а, т) = = 1, и ф(тг) значений а\ для которых (аг, т') = \у то имеется ф(/п)ф(т/) значений ат'-\-а'т, которые взаим- взаимно просты с mm'. Следовательно, Из доказательства теоремы 5 вытекает следующее утверждение: Теорема 5'. Пусть (т, т') = \. Если а пробегает пол- полную приведенную систему вычетов по mod m и а' пробе- пробегает полную приведенную систему вычетов по mod m\ то am'+a'm пробегает полную приведенную систему выче- вычетов по mod mm'.
26 Гл. П. Сравнения Теорема 5 может быть использована для вычисления ). Каждое целое п>\ может быть записано в виде так что 1=1 Следовательно, чтобы вычислить ф(я), достаточно знать значения ф(ра) для всех простых чисел р. Очевидно, Ч)(р) = Р—1- Если а>1, рассмотрим полную систему вы- вычетов по модулю ра, а именно 1, 2, ..., ра. Из этих чисел точно р**—1 не будут взаимно простыми с /?а, а именно кратные р числа ру 2ру Зру ..., ра . Следовательно, Таким образом, (?) 1=1 1=1 ИЛИ Ф(я) = яПA-7). A) Р\п V H j Другое важное свойство функции ф сформулировано в следующей теореме: Теорема 6. ^ц>(ф=т. dim г Доказательство. Пусть /я = JJp"*. Делители числа т имеют вид Цр^, где О^Cг^аг-. Следовательно, по i=i теореме 5
§ 3. Число решений сравнения 2 ф(Пр?<) = I] d\m (h Рг) м (Pi Отсюда после перегруппировки членов мы получаем = П ? ф(р?0 = 1=1 1=1 1=1 § 3. Число решений сравнения. Мы уже видели в этой главе, что если (а, ап) = 1, то линейное сравнение ах= = c(modm) разрешимо и имеет единственное решение. Поставим теперь вопрос о числе решений полиномиаль- полиномиального сравнения аохп + аххп-х + ... + an = 0(mod /?), где а0, аь ..., ап — целые числа, /г>1 и р — простое число. Если х — какое-либо решение этого сравнения, то любое целое число, сравнимое с х по модулю р, также будет его решением. По этой причине, когда мы говорим о числе решений сравнения, мы имеем в виду число классов вычетов, элементы которых удовлетворяют дан- данному сравнению. Следовательно, число решений равно числу удовлетворяющих сравнению представителей пол- полной системы вычетов по mod p. Полиномиальные сравнения могут иметь решения, а могут их не иметь. Например, сравнение x2 = 3(mod7) не имеет решений.
28 Гл. П. Сравнения С другой стороны, по теореме Ферма (теорема 3) сравнение хр~1 = 1 (modp) имеет р—1 решений х=1, 2, ..., р—1. Так как хр~1 = 1 (mod/?), если р f x, то мы имеем xP = x(modp) для всех х, х?+1 = х2(mod p) и т. д. Следо- Следовательно, любая степень, большая р—1, может быть ре- редуцирована и можно считать, что п<:р. Далее мы пред- предположим, что (а0, /?) = 1. Это условие гарантирует, что степень сравнения в точности равна п. Ответ на вопрос, поставленный в начале этого пара- параграфа, дает Теорема 7 (Лагранж). Сравнение a0xn+alxn-l+...+an = 0(rnodp)J (а0, р) = 1, B) имеет не более п решений. Доказательство. Докажем теорему индукцией по п. Для п—\ утверждение теоремы справедливо, посколь- поскольку (а0, р) = 1. Предположим теперь, что теорема спра- справедлива для п—1, и докажем ее справедливость для п. Если сравнение B) не имеет решений, то доказывать нечего. Если же оно имеет решение, скажем Х\, то пцХ^ + ^х?-1 4 ... +an=0(modp). C) Вычитая из B) сравнение C), мы получим сравнение а0 [х« — D) которому, очевидно, удовлетворяет каждое решение сравнения B). Далее, мы можем переписать D) в виде (х—x где Ьь 62, •••, bn-i—целые числа, зависящие только от Х\ и а0, аь ..., ап-ь Следовательно, каждое решение сравнения B) должно удовлетворять или сравнению х—Х\ = 0 (modp),
§ 3. Число решений сравнения 29 которое дает исходное решение х = Х\, или сравнению a0^-1+bi^ri-2+...+bn-i = 0(modp), (а0,/?) = 1, которое имеет степень п—1 и по предположению индук- индукции не более п—1 решений. В таком случае сравнение B) может иметь самое большее п решений, что и требо- требовалось доказать.
ГЛАВА III АППРОКСИМАЦИЯ ИРРАЦИОНАЛЬНЫХ ЧИСЕЛ РАЦИОНАЛЬНЫМИ И ТЕОРЕМА ГУРВИЦА § 1. Аппроксимация иррациональных чисел. Пусть | — действительное иррациональное число. Так как мно- множество рациональных чисел плотно в множестве всех действительных чисел, то для данного е>0 найдется та- такое рациональное число h/k, что |g—h/k\ <Се. Наша зада- задача состоит в изучении разности |?—h/k\ как функции от k. Будем предполагать в дальнейшем, что 0<?<1, дробь hjk несократима и k>0. Теорема 1. Если I — иррациональное число и N — положительное целое число, то существует рациональное число h/k со знаменателем k^N, такое, что Доказательство. Для любого действительного числа х обозначим через [х] целую часть числа х, т. е. такое целое число га, что га^х<га+1. Из иррациональности | следует, что 0<^—[п?]<1. Пусть п принимает зна- значения 1, 2, ..., N. Тогда мы получим N различных чисел п\—[nl], каждое из которых лежит в открытом интер- интервале @, 1). Рассмотрим N подинтервалов @, —), ~~ 1). Каждый из этих подинтерва- N 7 N ) 7 '\ N лов или содержит внутри себя точно одно из чисел п\— — [п!-], или же существует подинтервал, содержащий бо- более одного из этих чисел. В первом случае интервал О, —j содержит число т\—[т%] при некотором це- цеlN 0 лом т9 таком, что l^m^N, и, следовательно, g — [т1] < — • Таким образом, 0<g — -^i < ——
§ 1. Аппроксимация иррациональных чисел 31 и тем самым мы нашли рациональное число h/k, обла- обладающее требуемым свойством. Если подинтервал @, —) не содержит ни одно из \ N I I чисел п\—[ttg], l^n^N, то существует другой подин- подинтервал, содержащий по меньшей мере два таких числа, скажем п\—[п%] и mg—[mg]. Тогда мы имеем два це- целых числа т и п, 0<Cm<:n^.N, таких, что (mE[mE] )|<f или \(n-m)l-([nl]-[ml])\<-L. Если мы положим п—m = k и [п^] — [т?]=/г, то снова получим <J_ kN где Несколько более сильный результат дает Теорема 2. Если | — иррациональное число и N — положительное целое число, то существует рациональное число h/k со знаменателем k^.N, такое, что s fL I <- 1 k | k{N+ i)# Доказательство. Теорема может быть доказана таким же способом, что и теорема 1. Пусть лго=О, хи ..., xN, л:^+1 = 1—набор различных чисел, состоящий из 0, 1 и чисел п\—[п%], м=1, 2, ..., Л/", упорядоченных по возра- возрастанию. Разности Хп+\—хп>0 при п=0, 1, ..., Af ирра- иррациональны, и их сумма равна 1. Следовательно, хотя бы для одного значения п мы будем иметь хп+\—хп<. <1/(ЛЧ-1). Тогда существует рациональное число h/k, такое, что h где
32 Гл. III. Аппроксимация иррациональных чисел Другое доказательство теоремы 2 использует после- последовательности Фарея. Если FN — последовательность Фарея порядка N, то, поскольку g иррационально, мы имеем ^ф FN при любом N. Но g лежит между двумя по- последовательными дробями а/Ь и c/d, принадлежащими FN. Пусть a/6<g<c/d. Рассмотрим медианту (а + + c)/(b + d). Из гл. I мы знаем, что a/b< (a + c)/(b + d) < <Cc/d. Следовательно, или a/6<g< (a-f c)/(b + d), или (a + c)/(b + d) <g<c/rf. Так как а/6 и c/d— последова- последовательные члены в FN, то (a + c)/(b + d)&. FN. Значит, b-\-d^N-\-\. Поэтому или г, . о о^ . a + g «_ _ bc — ad __ 1 / 1 6 6 + ^ Ь ~~ b(b+d)~ b(b + d)^ b{N + 1) ' ИЛИ с ^ ^ с а-\-с be—ad I ^ ] dF+d) d(ft+d) d(^+l) Поскольку a/6 и c/d принадлежат Т7^, они несократимы и 6 <^УУ, dz^zN. Тем самым мы получили требуемое ра- рациональное приближение h/k (равное а/Ь или c/d). Проверим теперь справедливость теоремы 2 в слу- случае, когда g рационально, скажем, g=//m, (I, m) = \ и m>N. Тогда g^ FN и мы можем следовать данному выше доказательству, за исключением случая, когда g= (a-\-c)l(b-\-d). В последнем случае мы не можем по- поставить в теореме знак строгого неравенства и, таким образом, получаем следующий результат: Теорема 3. Если g — рациональное число, N — поло- положительное целое число и % = l/m, (/, m) = l, где m>N, то существует неприводимая дробь h/k со знаменателем Такая, что 1 Так как N^k, из теоремы 1 вытекает Теорема 4. Если g — иррациональное число, то суще- существует бесконечно много рациональных чисел h/k, таких, что --*- <-• k &
§2. Суммы двух квадратов 33 Иногда мы будем выражать этот результат другими словами, говоря, что иррациональное число | аппрокси- аппроксимируется рациональными числами h/k с точностью до \/k2. Так как |—h/k можно записать в виде (? + я) — — (h + kn)/k, где п — целое число, то теоремы 1, 2, 3 и 4 будут справедливыми и без предположения 0?1 § 2. Суммы двух квадратов. Теорему 3 можно исполь- использовать для доказательства того факта, что целые числа определенного вида представимы в виде суммы двух квадратов. Теорема 5. Пусть п и А — положительные целые чис- числа и п\(А2-\-\). Тогда существуют такие целые числа s и t, что n=s2-\-t2. Доказательство. Случай п=\ тривиален. Предполо- Предположим, что я^2, и пусть N=[Vn]. Ясно, что в этом слу- случае n>N. Из условия п\ (Л2+1) следует, что (п, Л) = 1. Следовательно, А/п есть несократимая дробь со знаме- знаменателем n>N, и тогда по теореме 3 существует несокра- несократимая дробь r/s, такая, что А_ _ г_ / 1 ^ N п s ^ s(N + 1) ' ^ ^ ' т. е. Пусть As—rn = t. Тогда t является целым числом и 52+ + t2 = s2+(As—rnJ = s2(A2+l)— 2Asrn-\-r2n2. Поскольку п делит правую часть последнего равенства, мы имеем n\(s2+t2). Кроме того, 0<s^A^^ Vn, \t\<Vn, от- откуда 0<52+^2<2д. Следовательно, n=s2-\-t2, так что п действительно является суммой двух квадратов. Легко видеть, кроме того, что (s, t) = \. Действитель- Действительно, мы имеем E, t) = (s, As—/ti) = (s, rn). Но дробь r/s несократима и, следовательно, (г, s) = l. Таким образом,
34 Гл. III. Аппроксимация иррациональных чисел (s, t) = (s, n). Кроме того, n—s2+t2 и тогда 1= s*(A2+l)* Поскольку по предположению (Л2+1)/м есть целое, лю- любой общий делитель 5 и п должен делить 1. Следова- Следовательно, (s, п) = 1 = (s, t). Следствие. Пусть п является положительным целым и п\(А2 + В2), где (Л, В) = 1. Тогда существуют такие целые числа s и t, что n = s2-\-t2. Доказательство. Воспользуемся тождеством (A2+B2)(C2+D2) = (AD+BCJ+(AC—BDJ. Из гл. I нам известно, что для данных Л и В с условием (Л, В) = 1 можно найти такие целые числа Си/), что АС—BD=l. Тогда мы получим (А2+В2) (C2+D2) = (AD+BCJ+l, так что если п\(А2+В2), то n\{(AD+BCJ+l}. По тео- теореме 5 мы получаем отсюда, что n = s2-\-t2. § 3. Простые числа вида 4к±1. В гл. I мы привели доказательство Евклида бесконечности множества про- простых чисел. Каждое простое число, отличное от 2, нечет- нечетно, а любое нечетное число представляется или в виде 4k—1, или в виде 4&+1 с целым k. С помощью рассуж- рассуждений, аналогичных рассуждениям Евклида, мы пока- покажем, что каждая из этих последовательностей содержит бесконечно много простых чисел. Теорема 6. Существует бесконечно много простых чисел вида 4k—1. Доказательство. Пусть qh #2, ..., Qr — первые г про- простых чисел вида 4k—1. Положим N=4q\qi...qv—1 и за- заметим, что N есть нечетное число. Следовательно, все его делители имеют вид 4k—1 или 4k + l. Но N яе может иметь в качестве делителей только числа вида 4&+1, так как произведение двух чисел такого вида снова яв- является числом того же вида, в то время как N имеет
Теорема Гурвица 35 вид 4k—1. Следовательно, число N имеет простой дели- делитель вида 4k—1. Ясно, что N не делится на qu Ць ••-, 9г, и тогда указанный простой делитель должен быть боль- больше qr. Теорема 7. Существует бесконечно много простых чисел вида 4k-\-\. Доказательство. Предположим, напротив, что про- простых чисел вида 4& + 1 конечное число и что 5, 13, ..., р — все эти простые числа, причем р — наибольшее из них. Положим Af=B.5.13.../?J+l. Число N нечетное и, следовательно, все его делители также будут нечетными. По теореме 5 каждый простой делитель q числа N представляется в виде q—s2-\-t2. По- Поскольку q нечетное, одно из чисел s и t должно быть чет- четным, а другое нечетным. Тогда q=s2-\-t2=\ (mod4) и, следовательно, каждый простой делитель числа N дол- должен иметь вид 4k-\-\, Это приводит, однако, к противо- противоречию, так как N> 1 и не делится на любое из простых чисел 5, 13, ..., /?, которые по предположению исчерпыва- исчерпывают все простые вида 4&+1. § 4. Теорема Гурвица. Мы начнем с уточнения теоре- теоремы 4. Теорема 8. Если | — иррациональное число, то суще- существует бесконечно много несократимых дробей h/k, та- таких, что Доказательство. Пусть FN — последовательность Фа- рея порядка Л/">1. Тогда | лежит между некоторыми двумя последовательными дробями а/b и c/d этой после- последовательности, так что
36 Гл. III. Аппроксимация иррациональных чисел Мы докажем теорему, если покажем, что выполняется по крайней мере одно из неравенств t JL</J_J! z<r— (\) 6 b ^2b*' d 6^2d«' K) Предположим, что неравенства A) не выполняются. Тогда, поскольку | иррационально, Отсюда и из условия be—ad=l мы получаем (b—dJ <0. Следовательно, или с. а . 1 с «. , 1 ?-Т<2^' или Т~Е<^- Таким образом, существует рациональная дробь /i/& в F (равная а/b или c/rf), такая, что Поскольку (c/d) — (a/b) = l/(bd), в силу выбора h/k мы имеем h_ J_ < 1 ~k bd^ b~+d—\ ' и так как по теореме 10 гл. I b-{-d^N-{-l, то Так как величину N можно менять по нашему усмотре- усмотрению, мы заключаем отсюда, что имеется бесконечно мно- много таких дробей h/k. Тем самым теорема доказана. В теореме 4 мы показали, что любое иррациональное число с точностью до l/k2 аппроксимируется бесконеч- бесконечным множеством рациональных чисел h/k. В теореме 8 эта аппроксимация была улучшена до 1/2&2. Естествен- Естественным образом возникает вопрос о возможности дальней- дальнейшего улучшения последнего результата. А именно, су- существует ли число с>2, такое, что \ можно с точностью до l/ck2 аппроксимировать бесконечным множеством ра- рациональных чисел h/k? Ответ на этот вопрос дает сле- следующая теорема Гурвица:
§4- Теорема Гурвица 37 Теорема 9 (Гурвиц). Если I — иррациональное число и с^ У~Ь — любое положительное действительное чис- число, то существует бесконечно много рациональных чисел h/k, таких, что <±. Если же с>У~5, то существуют иррациональные числа |, для которых указанное неравенство выполняется толь- только для конечного множества рациональных чисел h/k. Доказательство (Хинчин). Пусть FN — последова- последовательность Фарея порядка Л/г>1 и h/k, hf/kr — соседние члены этой последовательности, такие, что h/k<X<^hf/kr. Мы можем считать, что или . или В самом деле, если YLz±k<K<Y±±lk% ТО и мы можем заменить FN на FM, M = k-{-k\ а одно из чисел h/k, h'/kr их медиантой (h-\-hf) /(k-\-kf), так как k(h+h')—h(k+k/) = (k+k')h/—(h+h')k'=l (см. теоре- теорему 7 гл. I). Таким образом, если k'/k = (o, то cd>(K5~+ 1)/2 или К"—1)/2. В любом из этих случаев мы имеем К"~1, поскольку
38 Гл. III. Аппроксимация иррациональных чисел Следовательно, так что 1 i М- 1 1 k'21 V^k2 1С 1 у О К II II У * ^ ill | 1 \ откуда Значит, один из открытых интервалов ИЛИ ' будет содержать точку \. Рассуждая так же, как в за- заключительной части доказательства теоремы 8, мы ви- видим, что существует бесконечно много таких рациональ- рациональных приближений. Этим первая часть теоремы доказана. Для доказательства второй части предположим, что с > У~5, и рассмотрим иррациональное число ? = = —(l +J/1T). Покажем, что для этого | имеется толь- только конечное число дробей h/k, удовлетворяющих нера- неравенству '-т C) Пусть с=У~5/а, где 0<а<1. Предположим, что Последнее неравенство мы можем записать в виде ра- равенства 9 k
§4- Теорема Гурвица 39 где |8| <а. Отсюда мы получаем, что или, после возведения в квадрат обеих частей последне- последнего равенства, h2 — hk — k2 = Q + j^- Поскольку h и к — целые, h2—hk—к2 не может обра- обращаться в нуль, за исключением случая h = k = O. Но кФ- фО и, следовательно, \h2—hk—k2\^l. Так как |Э|< <а<1, мы имеем 1 < или k2 < а2 . D) 5A—а) ; Таким образом, знаменатель к дроби hjk, удовлетворяю- удовлетворяющей неравенству C), должен удовлетворять неравен- неравенству D). Но а фиксировано и потому к может при- принимать лишь конечное число значений. Из C) следует, что h также может принимать только конечное число значений. Следовательно, если с >К5~, то неравенство C) справедливо лишь для конечного числа дробей h/k. Тем самым теорема 9 полностью доказана. Отметим, наконец, что теоремы 4, 8 и 9 останутся справедливыми, если опустить условие
ГЛАВА IV КВАДРАТИЧНЫЕ ВЫЧЕТЫ И ПРЕДСТАВЛЕНИЕ ЧИСЕЛ В ВИДЕ СУММЫ ЧЕТЫРЕХ КВАДРАТОВ § 1. Символ Лежандра. Теория квадратичных выче- вычетов является одним из основных разделов теории чисел. С ее помощью, например, можно доказать такие эле- элегантные результаты, как теорему Эйлера о том, что каж- каждое простое число вида 4&+1 представляется в виде сум- суммы двух квадратов, и теорему Лагранжа о том, что каж- каждое положительное целое число представляется в виде суммы четырех квадратов. Пусть р — нечетное простое число и а — целое число, причем (а, р) = \. Если существует такое целое число х, что х2 = a (mod/?), то а называется квадратичным выче- вычетом по модулю р. Если такого х не существует, то а на- называется квадратичным невычетом по модулю р. Мы иногда будем использовать запись aRp для обо- обозначения того, что а — квадратичный вычет по модулю /?, и aNp для обозначения того, что а — квадратичный невычет по модулю р. Чтобы выяснить, сколько чисел из набора 1, 2, ..., р—1 являются квадратичными вычетами по модулю /?, мы должны знать, сколько сравнений x2 = a(modp) A) разрешимо, когда а пробегает значения 1, 2, ..., р—1. Рассмотрим целые числа 2 Все они попарно не сравнимы по mod р. Действительно, если мы возьмем любые два из этих чисел, скажем г2 и 52, гфэ, то из r2 = s2(mod/?) будет следовать, что г = = s(modp) или r = —s(mod/?). Но обе эти альтер- альтернативы исключены, так как l^r, s^Z(p—1)/2. Далее, г2=(р—гJ(mod/?). Из этих двух замечаний следует, что целое число а принимает в сравнении A) в точности (р—1)/2 различных значений, когда х пробегает множе-
§2. Теорема Вильсона 41 ство 1, 2, 3, ..., р—1. Следовательно, имеется в точности (р—1)/2 квадратичных вычетов и (р—1)/2 квадратичных невычетов по модулю р. Символ Лежандра. Пусть р — нечетное простое чис- число и m — целое число, такие, что (т, р) = \. Определим символ Лежандра ( — ) следующим образом: |+1, если mRp, \—1, если mNp. Удобно расширить определение символа Лежандра, по- положив _w\ j+1, если mRp, , Р I I—1. если mNn. —) = 0, если р\т. Поскольку имеется столько же квадратичных невыче- невычетов, сколько и квадратичных вычетов, мы имеем m=0 Далее, если т\ = гп2(то&р), то § 2. Теорема Вильсона и критерий Эйлера. Следую- Следующий результат, известный под названием теоремы Виль- Вильсона, но впервые доказанный Лагранжем, выражает характеристическое свойство простых чисел: Теорема 1. Если р — простое число, то (р—1)! = = —l(modp). Доказательство. При р = 2 утверждение теоремы оче- очевидно. Пусть р>2. Из рассуждений § 1 гл. II следует, что для любого х из множества 1, 2, ..., р—1 существует, и притом единственный, элемент хг из того же самого множества, такой, что *x's==l(modp). C) Далее, х=хг тогда и только тогда, когда х=1 или х =
42 Гл. IV. Квадратичные вычеты =р—1. Действительно, сравнение я2=1 (mod/?) эквива- эквивалентно сравнению (х— 1) (*+1) = 0(modp), так что или XE=l(mod/?), откуда х=1, или х=в—l(modp), откуда х=р—1. Из C) следует тогда, что 2-3...(р—2) = l(modp), и если мы умножим это сравнение на сравнение то получим Ь2.3...(р—1) = —l(modp). D) Тем самым теорема Вильсона доказана. Предположим теперь, что число р составное. Тогда его можно представить в виде p=qr, \<Cq<ip. Следова- Следовательно, q будет входить в качестве сомножителя в произ- произведение 1-2-3...(р—1), и сравнение (р—l)! + l=0(mod<7) в этом случае не разрешимо. Тем более не будет разре шимым и сравнение (р—1) !+l = 0(mod/?). Таким обра- образом, теорема Вильсона устанавливает характеристиче- характеристическое свойство простых чисел. Пусть теперь р — нечетное простое число и (а, р) = = 1. Покажем, что если а — квадратичный вычет по мо- модулю р, то а(р-1)Р=з I (mod р). Действительно, сравнение x2=a(modp) в этом случае разрешимо и (х, р)==1, ввиду того что (а, р) = 1. Если мы возведем обе части этого сравнения в степень (р—1)/2, которая, поскольку р нечетно, будет целым числом, то получим Но по теореме Ферма (теорема 3 гл. II) мы знаем, что #p-i=i(modp). Следовательно, а&-Ъ12 =\(modр). С другой стороны, по теореме Лагранжа (теорема 7 гл. II) сравнение
§2. Теорема Вильсона 43 может иметь не более чем (р—1)/2 решений. Но в § 1 мы показали, что имеется в точности (р—1)/2 квадратич- квадратичных вычетов и каждый из них удовлетворяет послед- последнему сравнению. Следовательно, это сравнение не может иметь других решений. Таким образом, нами доказана Теорема 2 (критерий Эйлера). Пусть р — нечетное простое число и а — любое целое. Сравнение справедливо тогда и только тогда, когда а является квад- квадратичным вычетом по модулю р. Далее, если р — нечетное простое число и (х, р)—\, то по теореме Ферма Следовательно, или E) или x(P-l)/2=—l(modp), F) и так как по теореме 2 квадратичные невычеты не удов- удовлетворяют сравнению E), они должны удовлетворять сравнению F). Вспоминая определение символа Ле- жандра, мы получаем отсюда следующую теорему: Теорема 3. Если р — нечетное простое число, то р Следствие. Имеет место равенство которое означает, что произведение двух квадратичных вычетов или невычетов по модулю р является квадра- квадратичным вычетом, а произведение квадратичного вычета и квадратичного невычета по модулю р есть квадратич- квадратичный невычет по модулю р.
44 Гл. IV. Квадратичные вычеты § 3. Суммы двух квадратов. Пусть р — нечетное про- простое число, и пусть т=р—1. Так как р—1= —1 (mod/?), то мы получим по теореме 3 Hof—)=±1, (—1)(р-1)/2= ±1 и р>3. Следова- \ Р 1 тельно, откуда следует, что —1 есть квадратичный вычет по mod p для всех простых р= 1 (mod 4) и квадратичный не- невычет по mod/? для всех простых /?=3(mod4). Это при- приводит нас к следующей теореме: Теорема 4 (Эйлер). Каждое простое число вида 4&+1 можно представить в виде суммы двух квадратов. Доказательство. Если р — простое число вида 4&+1, то —1 является квадратичным вычетом по модулю /?, т. е. сравнение х2=— l(mod/?) разрешимо. Следователь- Следовательно, существует целое число Л, такое, что р\ (А2-\-1). По теореме 5 гл. III отсюда следует, что р является суммой двух квадратов. Результат о том, что для простого числа р вида 4&+1 мы имеем р\ (Л2+1) при некотором Л, может быть уточ- уточнен следующим образом: Теорема 5. Если р — простое число и /?=l(mod4), то существует такое целое число х, что x2-\-l=mp, где 0<т<р. Доказательство. Так как —1 является квадратичным вычетом по mod/?, существует целое х из набора 1, 2,...,(/?—1)/2, которое удовлетворяет сравнению Тогда x2-\-l=mp для некоторого целого т. Но х</?/2 и, следовательно, х2+1< (/?/2J+1</?2. Таким образом, x2-\-l=mp, где
§3. Суммы двух квадратов 45 Следующий результат аналогичен результату теоре- теоремы 5. Теорема 6. Если р — нечетное простое число, то су- существуют целые х и у, такие, что 1 + *2 + у2 = пгр, где 0<пг<р. Доказательство. Целые х2, 0^х^(р—1)/2, попарно не сравнимы по mod р. То же самое справедливо для це- целых —1—у2, 0^у^.(р—1)/2. Но эти два множества вместе содержат р-\-1 целых чисел, и так как имеется только р классов вычетов по mod/?, некоторый член х2 первого множества должен быть сравним с некоторым членом —1—у2 второго множества. Таким образом, х2= —1—y2(modp), или 1-\-х2-\-у2 = тр. Но О^х, у^ (р—1)/2. Следовательно, и тогда Теорема доказана. Мы видели, что каждое простое число вида 4&+1 представимо в виде суммы двух квадратов. Но другие числа также обладают этим свойством, например 10 = = 12+32. Следующая теорема дает необходимое и доста- достаточное условие представимости положительного целого числа в виде суммы двух квадратов: Теорема 7. Положительное целое число п можно представить в виде суммы двух квадратов тогда и толь- только тогда, когда все простые сомножители вида 4&+3 входят в каноническое разложение этого числа с четны- четными показателями. Докажем предварительно две леммы. Мы назовем представление п = х2-\-у2 примитивным, если (х, у) = 1, и непримитивным в противном случае.
46 Гл. IV. Квадратичные вычеты Лемма 1. Если п делится на простое число р, где р = =3(mod4), то п не имеет примитивных представлений. Доказательство. Если п имеет примитивное пред- представление, скажем п=х2+у2, (х,у) = 19 то р\ (х2-\-у2), но pJfx и р\у. Так как (р,х) = 1, то урав- уравнение mx—tp = c разрешимо в целых числах m и t при всех целых с и, в частности, при с = у. Следовательно, существует такое целое число пг, что mx=y(modp), откуда х2+ (mx) 2=x2+y2=0 (mod p). Тогда р\х2(т2+\), и так как р^х, то р\ (т2+\). Таким образом, т2=—l(modp). Другими словами, —1 есть квадратичный вычет по простому модулю р вида 4&+3, но, как было выяснено в начале § 3, это невозможно. Тем самым лемма доказана. Лемма 2. Если р — простое число, p=3(mod4), и с — нечетное целое, такое, что рс\п, но pc+l^f n, то п не может быть представлено в виде суммы двух квадратов. Доказательство. Предположим обратное, т. е. что п=х2-\-у2, где (х, y)=d. Тогда x=dX, y=dYt (X, У) = = 1, и n=d2(X2+Y2)=d2N при некотором N. Пусть рг — наивысшая степень р, которая делит d. Тогда рс~2г будет наивысшей степенью /?, делящей N. Из нечетности с следует, что с—2г>0. Таким образом, мы имеем, что N=X2+Y2, (X, Y) = l, и p\N, где р= E==3(mod4). Но это противоречит утверждению леммы 1 и доказывает лемму 2. Доказательство теоремы 7. Условия теоремы необхо- необходимы. Действительно, из леммы 2 следует, что если п представимо в виде суммы двух квадратов, то каждый простой делитель числа п вида 4&+3 должен иметь чет- четный показатель степени в каноническом разложении п. Условия теоремы являются также и достаточными. Действительно, если п — положительное целое, такое,
§4- Суммы четырех квадратов что каждое простое вида 4?+3 входит в каноническое разложение этого числа с четным показателем, то п мож- можно записать в виде п=п\п2, где п2 не имеет простых де- делителей вида 4&+3. Следовательно, простыми делителя- делителями числа п2 являются только простые числа вида 4&+1 или число 2. Но 2 представимо в виде суммы двух квад- квадратов: 12Н-12, и каждое простое вида 4& + 1 также можно представить в таком виде. Далее, из тождества 2+ ( следует, что произведение двух чисел, представимых в виде суммы двух квадратов, также имеет такое пред- представление. Таким образом, п2=а2-{-Ь2, откуда п — = (пха)*+(п1Ъ)*. § 4. Суммы четырех квадратов. В заключении этой главы мы докажем хорошо известный и элегантный ре- результат: Теорема 8 (Лагранж). Каждое положительное целое число п является суммой четырех квадратов. Доказательство. Мы имеем 12=12+02+02+02 и по- потому можем предполагать, что л>1. Из тождества = z\±zl + zl + z% G) где г2 = х1у2— zA = xly4 следует, что произведение двух целых чисел, представи- представимых суммой четырех квадратов, также йожно предста- представить в таком виде. Каждое целое число п>\ является произведением нечетных простых и, возможно, числа 2 = = 12+12+02+02. Следовательно, достаточно доказать, что каждое нечетное простое представляется в виде сум- суммы четырех квадратов.
48 Гл. IV. Квадратичные вычеты Из теоремы 6 следует, что если р — нечетное простое число, то существует целое т<Ср, такое, что тр = х{ + х\ + х\ + х\, где не каждое Х\, х2, х3, х4 делится на р. Для данного нечетного простого числа р обозначим через то наименьшее положительное целое число, такое, что ЩР = *1 + А + х\ + х\, т0 < р. (8) Если то = 1, то доказывать больше нечего. Предположим, что то>1. Покажем сначала, что т0 должно быть нечетным. Действительно, если т0 четное, то хи х2, Хг, х4 или все четные, или все нечетные, или два из них четные и два нечетные (например, Х\, х2 чет- четные, а я3, Х4 нечетные). Так как +1 2 ]+1 2 j+l 2 мы видим, что (т0р)/2 является суммой четырех целых квадратов, не все из которых делятся на р. Но это про- противоречит минимальности т0. В таком случае то^3 и мы можем записать, что Xi = bimo-\-yi (t = l, 2, 3, 4), (9) причем целые Ъ\ можно выбрать таким образом, чтобы |Уг|<ОЯо/2. Действительно, если при делении Xi на не- нечетное число то мы получим Х\ = Ъ\тъ-\-у\ > где у\ >то/2, то мы можем записать, что где —то/2<:уг<О. Далее, не все Х\, х2, хг, л:4 делятся на т0. Действи- Действительно, если бы все Х\, х2, хг, хА делились на т0, то мы имели бы то\р9 что невозможно, так как 1<то<ср. Сле- Следовательно, и мы имеем
§4- Суммы четырех квадратов 49 о < yl + у\ + yl + yl < 4 ({^оJ= < Но из (8) и (9) следует, что У\ + У\ + #1 +#1=0 (mod m0). Итак, мы имеем целые числа яг*, #г (i = l, 2, 3, 4), для которых дг? + х22 + х\ +xl = тору т0 < р, Л2 + yj + У\ + yj = mi/n0, 0 О*! < /п0. Тождество G) дает нам четыре целых числа гь г2, г3, г4, такие, что zl + zl + zl+zl=mlmlP. (Ю) Далее, 4 4 4 zi = И ^/ У/ = 2 ^/ (^j - &/"*<>) " 2 х/ (mod m0) = = 0(modm0), и, аналогично, г2~ z3— zAeee 0(mod m0). Следовательно, Zi = moti, где /; — целые числа при i = = 1, 2, 3, 4. Подставляя эти значения 2г в равенство A0), мы получаем где 0<mi<m0, что противоречит минимальности то. Следовательно, то = 1 и теорема 8 доказана.
ГЛАВА V КВАДРАТИЧНЫЙ ЗАКОН ВЗАИМНОСТИ § 1. Квадратичная взаимность. Пусть р и q — различ- различные нечетные простые числа. Тогда определены символы Лежандра 1—\ и (—)- Можно ли указать значение (—), если известно значение (— )? Квадратичный за- закон взаимности Гаусса показывает, что это действитель- действительно возможно. Теорема 1 (Гаусс). Если р и q — различные нечетные простые числа, то р—1 q—\ Так как — (р—l)-~7[(q—О есть нечетное число тог- тогда и только тогда, когда p = q=3(mod4), теорему 1 можно сформулировать следующим образом: —)= — (—), если /? = <7 = 3(mod4), я i \ р I -2-\ = (—) в противном случае. Мы выведем квадратичный закон взаимности из фор- формулы взаимности для некоторых тригонометрических сумм. § 2. Формула взаимности для обобщенных сумм Га- Гаусса. Пусть ш и п — ненулевые целые числа. Определим обобщенную сумму Гаусса следующим образом:
§2. Формула взаимности для обобщенных сумм Гаусса 51 Когда т четное, эта сумма представляет собой сумму Гаусса. Теорема 1 может быть выведена из формулы, связывающей g(m, п) и g(—пу т), которая устанавлива- устанавливается в следующей теореме: Теорема 2. Если тип — ненулевые целые числа, то 1 , ч 1f-U—\mn\) sgn {mn) \ -—g(m,n) = e4 g(-nfm), B y\n\ y\m\ где S 1 0 приг = Доказательство. В доказательстве мы будем пользо- пользоваться интегрированием в комплексной плоскости. Рассмотрим интеграл $ C) С где Ф(и) = Ф(и9Х) = Ф(и,Х9х)=-^-— . D) е2ши— 1 Здесь и — комплексная переменная, X — произвольное комплексное число, х — комплексное число с положи- положительной действительной частью, а С — прямая в комп- комплексной ^-плоскости, проходящая через точку и=1/2 и составляющая с положительным направлением дейст- действительной оси угол я/4. Покажем сначала, что интеграл сходится. Для этого мы оценим функцию Ф в любой по- полосе (конечной ширины), которая ограничена двумя прямыми, параллельными С Если мы положим ni и=с+е~, где сиг — действительные переменные величины, при- причем величина с ограничена, и т = Rex + Птт, то I nixu? -f- 2niXu I _ — я Im (ти2 + 2Хи) I — ^ И ni то2 + 2Хи = iV2 + 2е~(хс + X) г + (тс -Ь 2Х) с,
52 Гл. V. Квадратичный закон взаимности так что 1т(хи2 + 2Хи) ^Rex-r2—2\%с + Х\. \r\ — \ (тс + 2Х)с\ Следовательно, I niTU2-{-2niXu\ ^ —пг*Яе <Лв-лг2Кет + Б|г|, E) где А и В — постоянные, не зависящие от г. Далее, | вй«'«_ 11 > 11 _| еШи\ | = 11 - е~ппг\, и если в указанной полосе |м|->-оо, то г->±оо, так что при достаточно больших значениях \и\ мы будем иметь Wnitl-\\>\>o. F) Тогда из E) и F) мы имеем в указанной полосе при всех достаточно больших значениях \и\ G) Следовательно, интеграл \Q)(u)du сходится. с Покажем теперь, что g(m, n) при п>0 является зна- значением интеграла \Ф(и)с1и при подходящем выборе контура у. 7 Пусть у — параллелограмм, образованный прямой С, прямой Сп, параллельной С и пересекающей действи- действительную ось в точке я+1/2, п>0, и прямыми L\ и L2, лежащими в верхней и нижней полуплоскостях соответ- соответственно, параллельными действительной оси и отстоя- отстоящими от нее на положительном расстоянии (рис. 1). Функция Ф(и) является мероморфной функцией пе- переменного и, и, если контур у обходится в положитель- положительном направлении, мы имеем по теореме Коши о вычетах = V (8) Из G) следует, что Ф(а)->0 равномерно в полосе между параллельными прямыми С и Сп при |м|->оо. Следова-
§2. Формула взаимности для обобщенных сумм Гаусса 53 тельно, при удалении прямых L\ и L2 от действительной оси к бесконечности интеграл по сторонам L\ и L2 парал- параллелограмма у будет стремиться к нулю, и тогда k=l 2niXk Рис. 1. Из D) мы имеем, однако, Ф (и + п, X) = так что где / определена по формуле C). Следовательно, соот- соотношение (9) переходит в k=l что дает соотношение между f(X) и f(X-{-%n). Найдем теперь другое такое соотношение и сравним их между собой.
54 Гл. V. Квадратичный закон взаимности Начнем с тождества Пусть теперь С — прямая, полученная из С с помо- помощью параллельного переноса и-^и+Х/х. Тогда С Из оценки E) ясно, что этот интеграл сходится. Инте- Интегрируя, как и раньше, по параллелограмму и используя оценку E) при ^=0, мы видим, что С Со где Со — прямая, параллельная С и проходящая через начало координат. На прямой Со мы имеем и = геш/4 при действительном г. Следовательно, Co и тогда Итерируя эту формулу т раз, получаем m)-f(X)=Ix- v=o где m — положительное целое. Отсюда, заменяя X на Х-\-хп—т, мы получим второе соотношение ^]_ _ я i I — — —¦ I /т.у И4 К (и)
§2. Формула взаимности для обобщенных сумм Гаусса 55 Из A1) и A0) мы выводим, что + 2niXn = у nixk2 + 2niXk j еШхп2 + 2ШХп у еП1[Т v=l m ¦ 2]i ' v=l l (X-vJ1 T——J Положим в этом равенстве Х = т/2 и х = т/п> т>0, п>0. Тогда v=l Далее, если мы положим т = п=1, то получим отсюда /i=l, т. е. оо rni2dt =1, и, используя подстановку / -> / |/т", где т — положитель- положительное действительное число, приходим к соотношению В таком случае из A3) при х = т/п и A2') мы имеем 4 т v=i — тп) т —nivn—v2ni —
56 Гл. V. Квадратичный закон взаимности а это по определению g(m, n) означает, что -^=g(m, п) = -^=е 4 g{—n,m). A4) Тем самым при т>0, д>0 теорема доказана. Если т>0 и дг<0, то —п, /п>0 и из A4) следует, что 1 1 ?Ei(i-j-m/z) g(—n,m)= e4 -—g(n,m)= Ti= V т V—n или 1 / ч 7==g(—m,—n) = |л| Но, по определению, g(—m, —n) = g(m, n) и, следова- следовательно, 1 , ч —-A—Im/z|)sgn (m/г) \ gytn.n) = е 4 -^=^р-(—п,т), О \ 7 / -| / О \ > '"/7 так что теорема справедлива и в этом случае. Если т<0 и дг<0, то формула B) также остается справедливой, так KaKg"(—m, —n) = g(m, n), g(n, —т) = = g{—п, т) и A — \mn\)sgn(mn) не меняется при заме- замене т и п соответственно на —т и —п. Теперь доказа- доказательство теоремы 2 закончено. Следует отметить, что в доказательстве равенство не предполагалось известным и было получено в качест- качестве побочного результата. § 3. Доказательство квадратичного закона взаимно- взаимности. Квадратичный закон взаимности, сформулирован-
§3. Доказательство квадратичного закона взаимности 57 ный в теореме 1, теперь нетрудно вывести из формулы взаимности для обобщенных сумм Гаусса, которая до- доказана в теореме 2. Так как &2E=?(mod2), мы можем заменить k на k2 в определении A) суммы g(m, n) и записать g{m,n)= 2j e k=i Пусть теперь п — нечетное простое число и m — не- некоторое целое, взаимно простое с п. Тогда мы имеем g(m,n)= 1 + S e k=\ Если fe2^p(modn), то легко видеть, что nik*— (n+l) Jttp-^-U+l) e n ^e Но если &2=p(modft) и l^.k^.n—1, то p — квадратич- квадратичный вычет по модулю п и (п—&Js=Ei&2=p(mod n). Сле- Следовательно, если k пробегает целые 1, 2, ..., п—1, то k2 (взятое по модулю п) дважды пробегает множество квадратичных вычетов по модулю п. Значит, A5) где р пробегает множество квадратичных вычетов по модулю нечетного простого п. Рассмотрим теперь сумму где v пробегает множество квадратичных невычетов по модулю п. Мы имеем, очевидно, k=0
58 Гл. V. Квадратичный закон взаимности Но п-\-1 есть четное число и, следовательно, е п есть k-я степень корня м-й степени из единицы, скажем г], причем г\ф\, так как п\т. Таким образом, e V п—г р v р=о Из A5) и A6) мы получаем, что p v Рассмотрим теперь два возможных случая (-^¦) = j (а) Если m — квадратичный вычет по модулю п и р пробегает все квадратичные вычеты по тому же мо- модулю, то, согласно следствию теоремы 3 гл. IV, р/n так- также пробегает все квадратичные вычеты. Если же v про- пробегает все квадратичные невычеты, то vm также пробе- пробегает квадратичные невычеты по модулю п. Следователь- Следовательно, в силу A7) я,р(»±!) nlvti±l) (б) Если m — квадратичный невычет по модулю п, то с помощью рассуждений, аналогичных рассуждениям пункта (а), мы имеем
§ 3. Доказательство квадратичного закона взаимности 59 m*v -3L- ju'p —!-— р Таким образом, мы показали, что если д — нечетное про- простое число и (га, п) = 1, то ff(m, я) =(•?)*(!. «)• A8) С другой стороны, из теоремы 2 следует, что = уп и так как, по определению, g(—п, 1) = 1, мы имеем A~я). A9) Из A8) и A9) мы получаем важную формулу: ~Г~\П—I) . /С\Г\\ 4 g (т, п). B0) где п — нечетное простое число и (га, п) = 1. Если га= —1, то из B0) следует, что Но, согласно соотношению B), мы имеем поскольку g(—п, —1) = 1. Следовательно, До сих пор мы предполагали, что п — нечетное простое число. Пусть теперь га также будет нечетным простым.
60 Гл. V. Квадратичный закон взаимности Тогда из B0) и B) следует, что я/ V^& и, снова используя B0), мы получаем п Но, согласно B1), Следовательно, я / \ т) v и так как (— =1, то т I X rt—l m—1 ) f П 2 " 2 п Тем самым доказательство теоремы 1 завершено. § 4. Некоторые приложения. Теорема 1 касалась ве- / Р \ личины —1, где р и q— различные нечетные простые числа. Для того чтобы определить, будет ли данное чет- четное число квадратичным вычетом или невычетом по мо- модулю нечетного простого числа, мы должны научиться вычислять символ Лежандра I —). Это можно сделать, используя формулы B) и B0). Теорема 3. Если р — нечетное простое число, то B2) Другими словами, '_2^ = { +1, если p=±l (mod8), [ — 1, если р = ± 3 (mod 8).
§4- Некоторые приложения 61 Доказательство. Согласно формуле B0), мы имеем , ni / -, ч и в силу формулы B) Далее, из определения g(m9 n) следует, что nip g(-p,2)=l+e~. Таким образом, nip —Т , nip * i е 1- Пример. Вычислим, используя теоремы 1 и 3, /12703 \ \16361/" Здесь оба числа 12703 и 16361 простые. По теореме 1 мы имеем /12703 \ _ /16361 \ U6361/ U2703/ и так как 16361 =3658(mod 12703), то /16361 \ _ / 3658 \ \12703/\12703/' Далее, поскольку = — . — , то, согласно \ Р I \ Р I V Р I теоремам 3 и 1, / 3658 \ _ / 2 \ / 31 \ / 59 \ = / 31 \ / 59 \ _ \12703/ \ 12703/ \ 12703/ \ 12703/ ~" \ 12703/ \ 12703/ ~~ = Г_/12703\1 f p703\) /24W 18\_ \ \ 31 //в \ V 59 Л \ 31А 59/ 31 А 31 А 59 А 59/'
62 Гл. V. Квадратичный закон взаимности Наконец, ввиду того что — = — =1 и — =1, \ «31 / \ 31 / \ оУ / мы получаем Замечание. Как мы видели в гл. IV, если р — нечет- I т\ [ т'\ ное простое число, то — = — для всех целых \ Р 1 \ Р 1 m/ = m(modp). B — имеет одно и то же значение для всех простых р, при- принадлежащих арифметическим прогрессиям Ът±\ или Теорема 1 может быть использована для доказатель- доказательства более общего результата: если q — фиксированное нечетное простое число, то где рг такое простое, что //=p(mod4g). Действительно, так как //=/?(mod4g), то рг = = р (mod 4) и тогда — (р'— 1) = — (р— 1) (mod 2). По теореме 1 мы имеем р'—\ д—1 р—1 <7—1 Далее, так как р' = р (mod 4q), то р' = р (mod q), откуда (—)^(—). Таким образом, (—) ^ (—г) и тем са- \ Я I \ Я I V Р 1 \ Р I мым равенство B4) доказано.
ГЛАВА VI АРИФМЕТИЧЕСКИЕ ФУНКЦИИ И ЦЕЛЫЕ ТОЧКИ § 1. Общие замечания. Напомним, что арифметиче- арифметическая функция — это комплекснозначная функция, опреде- определенная на множестве положительных целых чисел. Мно- Многие из арифметических функций, которые будут нами рассмотрены, являются целозначными. Арифметическая функция f называется мультиплика- мультипликативной, если (i) f не равняется тождественно нулю и (ii) f (mn) =f(m) -f(n) при (m, n) = 1. Условие (i) можно сформулировать иначе, а именно /A) = 1. В качестве примера такой функции можно привести функцию Эйлера ф, введенную в гл. П. Мы показали, что она мультипликативна и что q(pa) = pa(l— 1/р) для любого простого р и положительного целого числа а. Многие арифметические функции ведут себя крайне нерегулярно, и поэтому часто более интересным пред- представляется изучение сумматорной функции арифметиче- арифметической функции /, а именно а не самой функцииf(n). Некоторые из рассматриваемых нами арифметических функций имеют простую геометрическую интерпретацию. С их помощью можно подсчитать число целых точек в некоторых областях, т. е. число точек n-мерного евкли- евклидова пространства, м^1, имеющих целые координаты. § 2. Функция г(п). Арифметическая функция г(п) определяется как число представлений целого п^\ в ви- виде суммы двух квадратов; другими словами, значение г(п) равно числу решений уравнения х2+у2=п в целых числах х и у. Решения, отличающиеся друг от друга зна- знаком или порядком, считаются различными. Так, гA) = 4
64 Гл. VI. Арифметические функции и целые точки ввиду того, что 1 = (±lJ+02 = 02+(zblJ. Следователь- Следовательно, г(п) не мультипликативна. Мы видели в теореме 7 гл. IV, что г(п)=0, если п — простое число вида 4&+3. С другой стороны, из тео- теоремы 6 гл. III следует, что таких простых бесконечно много. Таким образом, г(п)=0 для бесконечного мно- множества значений п, и так как г(п) ^0, то limr(tt)=0. П-*оо Можно оценить порядок роста г(п) и доказать, что г(п) =О(пе) для любого е>0, т. е. \r(n) \п-&<.К, где К — положительная постоянная, не зависящая от п. Од- Однако более интересным представляется изучение (не- (несколько измененной) сумматорной функции R(N)=fir(n), г@) = 1. Геометрически R(N) представляет собой число целых точек внутри и на границе круга x2+y2^.N. Ясно, что величина R(N) приближенно равна площади этого круга. Теорема 1. (Гаусс). R(N) = nN+O(]/N). Доказательство. Целые точки на плоскости являются вершинами квадратов единичной площади. Каждой точ- точке с целыми координатами, лежащей внутри или на гра- границе круга лг2+г/2^Л/", мы можем поставить в соответст- соответствие некоторый такой квадрат, взяв, например, за ука- указанную точку его «юго-западный» угол. Тогда R(N) будет равно сумме площадей этих квадратов. Некоторые из квадратов не полностью лежат внутри круга; с другой стороны, некоторая часть круга не по- покрывается этими квадратами (рис. 2). Однако, так как диагональ каждого квадрата равна J/2", все квадраты содержатся внутри круга /^/" так что R(N)<n(VN+V2J.
§3. Функция d(n) 65 Подобным же образом эти квадраты полностью по- покрывают меньший круг радиуса J//V — ]/2, так что R(N)>n{\/N-V2)\ W>2. \ I Рис. 2. Таким образом, п [N — 2\/Ш+ 2)<R(N)<n{N + 2\/2N + 2) и, следовательно, = nN+O(VN). § 3. Функция d(n). Арифметическая функция d(ri) определяется как число положительных делителей поло- положительного целого числа п. Теорема 2. Функция d{n) мультипликативна. Доказательство. Очевидно, d(l) = l, и если (т, п) = = 1, то каждый делитель произведения тп может быть единственным образом представлен в виде произведения делителя т и делителя п. Обратно, каждое такое про-
66 Гл. VI. Арифметические функции и целые точки изведение является делителем произведения тп. Следо- Следовательно, d(mn) = d(m)d(n). г Теорема 3. Если n=YLpai —каноническое разло- г жение числа м>1, то d(n) = Ц(аг- + 1). Доказательство. Поскольку d(n) мультипликативна, мы имеем Но положительными делителями числа раА являются только с&г+1 целых чисел 1, р., р?, ..., рЬ. Следова- Следовательно, ОД =П («/+!). i=i Функция d(ri) также допускает геометрическую ин- интерпретацию. Число положительных делителей числа п равно числу решений уравнения ху — п в положительных целых числах х, у. Следовательно, d(n) равна числу це- целых точек (х, у) «верхнего правого квадранта» (х, у)* плоскости, которые лежат на гиперболе ху = п. Порядок роста d(n). Из теоремы 3 следует, что d(n) может принимать сколь угодно большие значения. С другой стороны, d(n)=2, если п простое. Следова- Следовательно, lim d{n)=2. Теорема 4. Для каждого Д>0 существует последова- последовательность целых чисел яг-, для которых при /->оо. (log «/)Л К '
§3. Функция d(n) 67 Доказательство. Определим целое число k следую- следующим образом: й^А<^+1, если Д>0. Пусть pk+\ будет (&1) простым числом, и пусть п= B-3-5. где т — положительное целое число. По теореме 3 мы имеем Но где константа с не зависит от п. Положив ап=1, 2, 3,..., мы получим бесконечную по- последовательность положительных целых чисел п, для ко- которых d{n)>c{\ogn)h+\ и, обозначив &+1=Д+6 F>0), мы будем иметь для этой последовательности ¦>c(logn) —>oo при я—>оов {\ognf Тем самым теорема доказана. С другой стороны, справедлива Теорема 5. d(n) = o(n6) для любого 6>0. Другими словами, d(n)/n6-*0 при n-^оо. Для доказа- доказательства этой теоремы нам потребуется следующее ут- утверждение: Теорема 6. Если f — мультипликативная арифмети- арифметическая функция и /(Рт)—>0 при рт—>оо, где р — простое число и m — положительное целое (т. е. f(n)—>0, когда п пробегает множество степеней простых чисел), то /(я)—>0 при я—>оо.
68 Гл. VI. Арифметические функции и целые точки Доказательство. Так как /(рт)->0 при рт-*оо, то / удовлетворяет следующим условиям: (i) существует положительная константа А, такая, что \f(pm)\<A для всех тир-, (и) существует константа В, такая, что если рт^>В, то \f(pm) | <1; (ill) для данного е>0 существует такое N(e), что если рт>Ы(г), то \f(pm) | <е. Ясно, что Л и В не зависят от е, т и р, а Л/"(е) зави- зависит лишь от е. Пусть П = pi1 • Р22--- ргг C) — каноническое разложение числа п^>\. Поскольку f мультипликативна, мы имеем Рассмотрим все степени простых ра, и пусть С — чис- число таких степеней, которые не превосходят В. Тогда С не зависит от п и е. Для множителей f(p^ ) в разложе- разложении D), соответствующих этим степеням, мы можем применить неравенство (i); следовательно, их произве- произведение по абсолютной величине будет меньше чем Ас. Ос- Оставшиеся множители f(n) в силу (И) по абсолютной ве- величине меньше 1. Далее, имеется только конечное множество целых чи- чисел вида /эа, которые не превосходят N(s). Следователь- Следовательно, существует только конечное число целых, канониче- каноническое разложение которых состоит только из множителей вида ра, где ра ^.N(e). Пусть Р(г) —верхняя граница таких целых чисел. Если мы возьмем п>Р(е), то каноническое разложе- разложение числа п должно содержать по меньшей мере один сомножитель ра >А/"(е) и мы можем применить тогда неравенство (iii), а именно |/(раI<е.
§3. Функция d(n) 69 Следовательно, если п>Р(е), то мы имеем \f(n)\<A°-B, так что f (я)->0 при п-+-оо. Доказательство теоремы 5. Функция f(n)=d(n)/n мультипликативна и pm6 ^ pm& pm6 Так как Iog/?^log2, то отсюда для каждого б>0 Следовательно, по теореме 6 d(n) Л -*jf-—>0 при д^оо для каждого б>0; тем самым теорема 5 доказана. Можно показать, что для данного е>0 существует такое число N(e), что ( d(n)<2 при n>N(s) и, кроме того, что существует бесконечно много целых чисел я, для которых d(n)>2 Порядок роста d(n) в среднем. Рассмотрим сумма- торную функцию Так как rf(n) = J] 1 = J] 1, мы имеем Ля ху—п л=1 l<n<N xy=n ИЛИ 1Л^
70 Гл. VI. Арифметические функции и целые точки Ясно, что D(N) представляет собой число целых точек «первого» квадранта (т. е. верхнего правого квадранта), лежащих на или ниже гиперболы xy=N, при этом це- целые точки, лежащие на осях координат, исключаются, так как для них ху=0. Чтобы оценить порядок роста D(N), нам потребуется следующая теорема: Теорема 7. Пусть g — монотонно убывающая функ- функция действительного переменного t, определенная при ^0, причем g(t) >0 при fr^l. Тогда 1<п<Х 1 где п — целое положительное число, X^l и А — посто- постоянная, зависящая только от g. Доказательство, Рассмотрим замкнутый интервал [п, м+1]. Так как g — убывающая функция, то J g(t)dt<g(n). Следовательно, п+1 0<An = g(n)- J g(t)dt<g(n)-g(n + l). п Пусть М и N — произвольные положительные целые числа и M<C.N. Тогда п=М п=М и из условия g(t) >0 при /^ 1 мы получаем N S А*< g (М) для всех N > М. E) п=М оо оо В частности, ? ^4n^g(l), так что ряд ? Ап сходится. л=1 п=Л
§ 3. Функция d(n) 71 Положим оо У Л — А Тогда в силу E) мы имеем N со N ИЛИ откуда следует, что S ff(/i)= J g(t)dt + A + O{g(N+\)). п=\ 1 Положим N=[X]. Тогда последнее равенство перепи- перепишется в виде где п пробегает только целые значения. Но функция g положительная и убывающая, так что j g(f)dt<g(X)9 откуда что и требовалось доказать. Следствие 1. Существует постоянная у (постоянная Эйлера), такая, что 2 v =
72 Гл. VI. Арифметические функции и целые точки Следствие 2. Так как ТО где В — константа. Мы можем теперь доказать следующую теорему: Теорема 8. D(N)=N log N+0 (N). Доказательство. Как уже отмечалось, D (N) представ- представляет собой число целых точек в правом верхнем квадран- квадранте (х, у) -плоскости, которые лежат на или ниже гипер- гиперболы xy=N, но не лежат на координатных осях. Очевид- Очевидно, эти точки лежат левее прямой x=N и ниже прямой y=N (рис. 3). Сосчитаем число целых точек на каждой Рис. 3. из вертикальных прямых, пересекающих ось абсцисс в целых точках. Число целых точек на вертикальной прямой, ординаты которых не превосходят величины N/x, равно [N/x], так что N Х=1
§3. Функция d(n) 73 Положим [N/x]=N/x—Qx, где O^0jc<1. Тогда x=l " x=l x=l поскольку x=l , и по следствию 1 теоремы 7 = NlogN+O(N). Теорема доказана. Теорема 8 может быть значительно усилена. В каче- качестве первого шага мы докажем следующий результат: Теорема 9 (Дирихле). D(N) =NlogN+By— l)N+ + О (]/N), где у — постоянная Эйлера. Доказательство. Гипербола xy=N симметрична от- относительно прямой х=у. Следовательно, области ABGEO и CDOFG (рис. 4) содержат одно и то же число целых точек. Общее число целых точек в первом квад- квадранте, которые лежат на или ниже гиперболы (но не ле- лежат на осях координат), равно поэтому удвоенному чис- числу целых точек в области ABGEO минус число целых то-
74 Гл. VI. Арифметические функции и целые точки чек в квадрате OFGE. Таким образом, D(N) = 2 2 l-[VN]' = 2 2 2 1- Kx<VN Kx<VN l<y<N/x Kxy<N =*s m- Пусть [N/x]=N/x—QX9 0<9*<l, и [|/лГ] = |/2\Г —в, \ Тогда мы получим l<x<VN 1<x<VN = 2n 2 i-N-2 2 e. Kx<VN 1<x<VN Ho следовательно, В силу следствия 1 теоремы 7 D(A0=AnogN+BY— l)N+O(VN), что и требовалось доказать. Остаточный член О(]/Л?) в теореме 9 был улучшен Г. Вороным и доведен до O(N1/slogN). Существует ги- гипотеза, что остаточный член на самом деле есть /^/»rl/4-4-8 \ /-^ о „ U(N ). С другой стороны, известно, что остаточный член в теореме 9 не может быть доведен до O(Af1/4)- § 4. Функция о(п). Связанная с функцией d(n) арифметическая функция о(п) определяется как сумма положительных делителей числа п. В общем случае мы можем определить
§4- Функция <т(п) 75 М«) = 2Х. * = 0,1,2,..., d\n так что Go (n) = d(n) и а (п) = а\(п). Теорема 10. Арифметическая функция Gk{n) мульти- мультипликативна. Доказательство. Рассуждения, аналогичные рассуж- рассуждениям теоремы 2, показывают, что если (ш, м) = 1, то d*\mn Отсюда следует мультипликативность о(п). Подобным же образом доказывается и мультипликативность ои(п). г Теорема 11. Пусть п= JJ Рьг — каноническое разло- жение числа п>1. Тогда Доказательство. Поскольку функция Gk(ri) мульти- мультипликативна, мы имеем <yk(n) = П ok(p?) = П A + рЧ+ рТ +... +pf) = i=l i=\ и, в частности, при & = 1 1 G) С функцией a(n) связана старая проблема совершен- совершенных чисел. Положительное число Af называется совер-
76 Гл. VI. Арифметические функции и целые точки шенным, если g(N)=2N, т. е. N равно сумме всех его положительных делителей, меньших N. Например, 6 и 28 являются совершенными числами. Целые числа вида 2п—1 называются числами Мер- сенна, а простые числа такого вида называются просты- простыми числами Мерсенна. Связь между простыми числами Мерсенна и совер- совершенными числами устанавливается следующей теоремой: Теорема 12- Если 2n+1—1 является простым числом, то 2nBn+!—1) есть совершенное число. Доказательство. Пусть Af=2nBn+1—1)=2пр, где р простое. Тогда, согласно G), g(N) = Bп+1—1) (р+1) = B"+l—lJn+1 = 2N. Следовательно, N — совершенное число. Эйлер заметил, что этот результат можно частично обратить, а именно, справедлива следующая теорема: Теорема 13 (Эйлер). Каждое четное совершенное число имеет вид 2пр, где p = 2n+l—1 есть простое число Мерсенна. Доказательство. Пусть N=2nNf — совершенное чис- число, где п^ 1, и Nr — нечетное число. Тогда В силу мультипликативности а мы имеем a(N)=aBn)o(N'), и так как, согласно G), aBn) =2n+1—1, то B*+l—l)a(N')=2n+lN'. Следовательно, Bn+1—l)\N\ Если мы положим N' = = Bn+l—l)N", то a(N')=2n+lN", где N"<Nf. Но N'+ +N" = 2n+lN" = o(N'). Таким образом, и N\ и N" де- делят N' и их сумма равна a(N'). Значит, число N' не мо- может иметь других делителей и потому оно является про- простым. Но N'=Bn+l—l)N". Следовательно, N' = 2n+l—l, N"=1. Тем самым теорема 13 доказана. Неизвестно, будет ли бесконечным множество четных совершенных чисел (т. е. неизвестно, будет ли бесконеч-
§5. Функция Мёбиуса fi(n) ным множество простых вида 2п—1). Неизвестно также, существуют ли нечетные совершенные числа. Простые числа Мерсенна — это простые числа вида 2П—1. Легко видеть, что если п>1, а — положительное целое число и ап—1 является простым числом, то а=2 и п также должно быть простым числом. Действительно, если а>2, то (а—1)|(ап—1). Если же а = 2 и n = kl, 1<?</,то B*—1)|B*—1). § 5. Функция Мёбиуса \i(n). Функция Мёбиуса \i(n)—это арифметическая функция, которая опреде- определяется следующим образом: (i) ix(l) = l; ь (ii) \х(п) = (—1)*, если п есть произведение k различ- различных простых чисел; (ш) \х(п)=0 в противном случае, т. е. если п делится на квадрат целого числа, отличного от единицы. Из определения сразу же вытекает Теорема 14. Функция Мёбиуса \х(п) мультиплика- мультипликативна. Теорема 15. Справедливо соотношение A>вС4ИП = 1> d\n 1 0, если п > 1. m Доказательство. Пусть п = П pai — каноническое t=i l разложение числа м>1. Делители d числа м, для кото- которых \i(d) =7^=0, имеют вид Тогда d\n и, следовательно,
78 Гл. VI. Арифметические функции и целые точки Заметим, что функцию Мёбиуса можно определить, ис- используя теорему 15, и вывести из нее свойства (i), (ii), (iii). Наиболее важные приложения этой функции основа- основаны на так называемых формулах обращения Мёбиуса. Теорема 16 (первая формула обращения Мёбиуса). Пусть f — арифметическая функция и d\n Тогда d\n Доказательство. Мы имеем d\n d\n = 2 dd'\n d'\n и, следовательно, по теореме 15 ? d\n Справедливо и обратное утверждение: Теорема 17. Если d\n d\n ТО d\n
§5. Функция Мёбиуса ц{п) 79 Доказательство. Мы имеем по теореме 15 dm dm dm &Л— \d w i»» .. i n x ' d'\n d\n_ В качестве приложения теоремы 16 рассмотрим соот- соотношение d\n которое было доказано в теореме 6 гл. II. Из теоремы 16 следует, что dm dm Другое приложение этой теоремы связано с функцией Мангольдта Л, которая определяется следующим об- образом: а \ f logp, если п = рт, р простое, т > О, { 0 , если n=j=pm. Теорема 18. ? A(d) = log n. dm г Доказательство. Пусть п = Д р.а* — каноническое t=i разложение числа /г>1. Тогда по определению Л мы имеем г ai г 2 A(d) = Ц Ц Л(р?) = Ц at. logp,- = logn. Тем самым теорема доказана.
80 Гл. VI. Арифметические функции и целые точки Объединяя первую формулу обращения Мёбиуса и теорему 18, получаем din и так как по теореме 15 ]?jx(d) = O ПРИ п>\ и log 1=0, d\n то отсюда следует, что Sd. (9) din Теорема 19 (вторая формула обращения Мёбиуса). Пусть функция f определена при х^1 и Тогда при и обратно. [х] Сумма Yi интерпретируется как 2 , а сумма, не со- п<х п=1 держащая членов, полагается равной нулю. Доказательство. Из определения функции g мы име- имеем при \ - S mt{-h\ Группируя в последней сумме члены, для которых l, получаем »'Ш= 2'(т () 1<г<х п\г Итак, первая часть теоремы доказана.
§ 6. Функция Эйлера (р(п) 81 Чтобы доказать обратное утверждение, положим при Тогда и так же, как выше, последняя сумма может быть за- записана в виде У sl- п\г § 6. Функция Эйлера ф(^г). Вернемся к функции Эй- Эйлера ф. Мы знаем, что у(п)<сп при п>\. С другой сто- стороны, если п = рт, где р — простое число, /?>1/е, 0<8<1, и m^l, то [см. гл. II] Из этих неравенств следует Теорема 20. fim ^- = 1. Другой результат о порядке роста ф(п) дает Теорема 21. Для каждого 6>0 мы имеем Доказательство. Результат очевиден, если 6>1. Пусть 8^1 и „1-6 Тогда f мультипликативна, и в силу теоремы 6 достаточ-
82 Гл. VI. Арифметические функции и целые точки но показать, что f(pm)-+O при рт-+оо. В самом деле, для каждого 6>0 мы имеем При рт-+-ОО. Из теоремы 20 или теоремы 21 следует, что утверж- утверждение ср(га) = О (гаЛ) неверно, если Д<1. Порядок роста у(п) в среднем. Изучим поведение сумматорной функции для функции ф, а именно l<n<t Заметим, что значение Ф(Л^) равно числу членов в по- последовательности Фарея порядка N. Теорема 22 (Мертенс). Ф (t) =-^+0 (t log t). Доказательство. Мы имеем l<n<t l<m<n l<m<n<t (т,п)=1 (т,п)=1 и, следовательно, Ф@ равна числу целых точек с вза- взаимно простыми координатами, которые лежат в прямо- прямоугольном треугольнике 0<#^л;^. Рассмотрим квадрат 0<л;^, 0<#^. Прямая х = у делит этот квадрат на два прямоугольных треугольника, каждый из которых содержит одно и то же число целых точек с взаимно простыми координатами. Один из этих треугольников является данным треугольником 0<*/^ ^х^^. Заметим, что на прямой х = у лежит единствен- единственная точка х = у=1 с взаимно простыми координатами. Обозначим через x?(t) число целых точек с взаимно простыми координатами в упомянутом выше квадрате. Тогда
§ 6. Функция Эйлера (f(n) 83 так как точка х=у = 1 содержится в обоих треуголь- треугольниках. Общее число целых точек в квадрате равно [t]2, так что Ш2= ? 1. 0<m<t 0 Отсюда мы получаем m2= s ? I. (id 0<m<t 0<n<t (mfn)=d Далее, (m, n) —d тогда и только тогда, когда (mid, n/d) = l. Следовательно, существует взаимно одно- однозначное соответствие между целыми точками с координа- координатами т, я, где 0<.m^.t, 0<.n^.ty (m, n)==d9 и парами целых чисел т\ п', такими, что 0<m<|, 0</i<l, (mfn) = l. Но по определению Ч1* имеется в точности Wtf/d) та- таких пар т\ п'. Таким образом, равенство A1) может быть переписано в виде и, применяя к равенству A2) вторую формулу обраще- обращения Мёбиуса, мы получаем при t\ Пусть t/d=[t/d]+Q, где 0<6<1. Тогда -«• S
84 Гл. VI. Арифметические функции и целые точки так как ||x(ft)|^l. В силу следствия 1 теоремы 7 мы знаем, что 2Л0( 2 ^) = 2t'O и О( 2 0 = ^ @- Следовательно, A3) Чтобы оценить сумму в формуле A3), заметим, что d2 d=[t]+l d2 J [t] Тогда из A3) следует, что ^ A4) Ряд V *-^- можно вычислить следующим образом. По- ~~ * V1 1 V1 ii(tn) ^ скольку оба ряда /_,— и У. ~2~ сходятся абсолютно, т=1 то, перемножив их, мы получим со со SI vi \i(m) у cv где Но \~т = ~с" и ci = 1, ^п = 0 при /г>1 по теореме 15.
§ 6. Функция Эйлера (f(n) 85 Следовательно, П и, подставляя это значение в A4), мы получим Отсюда и из A0) следует, что <D@ = i?+O(<log0, <15) как и утверждалось. Соотношение между ф и а. Интересно отметить, что из результатов о поведении функции ф следуют резуль- результаты о поведении функции а, и наоборот. Это вытекает из следующей теоремы: Теорема 23. Существует положительная константа С, такая, что ; 1 при всех п>2. A6) п2 Доказательство. Пусть n = YL ра - Тогда, изменив р\п очевидным образом обозначения, мы имеем, согласно G), Pin P~l pin l~i Поскольку ф(п, = яПA-|). Pin мы имеем а(п)ф(п) = д^ l—)<lm П Pin
86 Гл. VI. Арифметические функции и целые точки Тем самым доказано второе неравенство в A6). С другой стороны, р\п \ У I р\п причем 1 —1//?2<1 и произведение в правой части рас- распространяется на все простые числа р. Тем самым дока- доказано и первое неравенство в A6).
ГЛАВА VII ТЕОРЕМА ЧЕБЫШЕВА О РАСПРЕДЕЛЕНИИ ПРОСТЫХ ЧИСЕЛ § 1. Функции Чебышева. В гл. I мы установили, что существует бесконечно много простых чисел. Следова- Следовательно, если мы обозначим через п(х) количество про- простых чисел, не превосходящих х, то я(л;)-^оо при х-+<х>. Асимптотический закон распределения простых чисел, ко- который мы докажем в гл. XI, даст нам много больше, а именно lim l ; = 1. В этой главе мы докажем несколько интересных проме- промежуточных результатов. Начнем с результата Эйлера о том, что сумма 5J1//7, где суммирование распространя- распространяется на все простые числа, расходится, откуда следует, что простых чисел бесконечно много. Теорема 1 (Эйлер). Пусть р пробегает множество всех простых чисел. Тогда с\)мма^\\р и произведение П A — Up) расходятся. Доказательство. Докажем сначала, что произведе- произведение П A—I//?)" расходится, и выведем отсюда утвержде- утверждение о расходимости ряда J] VP- Пусть GГ } р<х ч J р<х Для действительного числа и, 0<?/<1, и положитель- положительного целого m мы имеем —L->J-7" =1+й+ ... + !**. 1 — и 1 — и Положим и=1/р, где р — простое число. Тогда из по- последнего неравенства следует, что для всех простых
Гл. VII. Теорема Чебышёва Выберем теперь т так, чтобы выполнялось неравенство 2. Тогда f р<х Действительно, каждое целое число я, 1<я^|ХЬ име- имеет в качестве простых сомножителей только простые чис- числа р^х, а неравенство 2т^х гарантирует, что после разложения левой части последнего неравенства в сум- сумму каждое слагаемое правой части встретится среди слагаемых левой части. Таким образом, [х] /1=1 1 и, следовательно, произведение ДA — 1/р)~1 расходится. Чтобы доказать расходимость ряда ^]—, рассмотрим разложение р )=»+?+?+¦¦¦. -'<•<>• Для ы>0 мы имеем Геометрический ряд в правой части последнего неравен- неравенства сходится при |м| <1, так что Положим теперь и=1/р и просуммируем неравенства по всем р^л:. Мы получим р<х
§ 1. Функции Чебышёва 89 S(x) > \ogP(x)-±> log log* —i так что Следовательно, ряд Zjl/p расходится, и теорема 1 полно- полностью доказана. Функции О и i|). Функции Чебышёва О и i|) определя- определяются следующим образом: &(х) = I] \°?Р> х>0, р — простое число, A) р<х И ty(x)= 2 logp, л:>0. B) рт<х Сумма B) распространяется на все пары р, т, где р — простое, am — положительные целые числа, такие, что рт^х. Это означает, что если рт — наибольшая сте- степень р, не превосходящая х, то log/? в сумме B) засчи- тывается точно т раз. Например, ¦ф A0) =3 log 2+2 log 3+log 5+log 7. В § 5 гл. VI мы ввели функцию Мангольдта [ logp, если п = рту где т—положительное Л (я) = \ целое число, 1 0, если n=f=pm. Из определения -ф непосредственно следует, что г|)(л:) = ^]Л(п). C) п<х Далее, из A) и B) вытекает, что е®{х) равно произведе- 1 ibf x) нию всех простых р^х и при x^l e есть наименьшее р р общее кратное всех положительных целых чисел Если рт^х, то р^х1/т , и обратно. Тогда из B) следует, что г|) (х) = О (х) +0 (х1/2) +0 (*1/3) +..., D) причем этот ряд конечен, так как ®(х) =0 для х<2. Ес- Если рт^х<:рт+\ х^>1, то log p в формуле C) для $(х) встречается точно т раз и m= [log #/log /?]. Следователь-
90 Гл. VII. Теорема Чебышёва но, мы получаем четвертое выражение для ty(x), именно Установим теперь связь между функциями *(*) <>(*) дс/log л: ' х ' Теорема 2. Пусть Доказательство. Из D) следует, что $(х Далее, из E) вытекает, что так что г|)(л:)^ я (л:) log л:. Следовательно, Ф W <г|) W ^ я (л:) log a:. Если теперь мы разделим эти неравенства на х и устре- устремим х к бесконечности, то получим F) Выберем действительное число а, 0<а<1, и пусть 1. Тогда
§2. Теорема Чебышёва 91 и так как log p>\og хау то *(*)>alog* J 1. л;а<р<л; Таким образом, О (х) > a log л: (я (х) — я (**)). Но, очевидно, я(ха) <#а, так что д(л:) > ап(х) log л: — аха log ж, или ФМ . , v log х log л: л: v ' х xl~a Далее, 0<а<1, откуда (log x/xl-a)->0 при *->оо. Сле- Следовательно, для любого действительного а, 0<а<1. Поэтому Z,2^^i, и, сравнивая это неравенство с F), мы получаем L\ =1/2 = ?3. Доказательство того, что /1 = /2 = /3> приводится таким же образом. Из теоремы 2 следует, что если одна из трех функций *(*) »(*) имеет предел при х->оо} то другие две функции также имеют пределы при x->oo и все эти три предела совпада- совпадают. Таким образом, для того чтобы доказать асимпто- асимптотический закон распределения простых чисел, достаточ- достаточно доказать, что liim|)(*)/*=l. § 2. Теорема Чебышёва. Мы используем теорему 2 для доказательства следующей теоремы: Теорема 3 (Чебышев). Существуют постоянные аи А, М, такие, что для всех достаточно больших х
92 Гл. VII. Теорема Чебышёва log* ^ l '^ log*1 Доказательство. Пусть Если мы покажем, что L^41og2 и /^Iog2, то теорема будет доказана. По теореме 2 оба эти неравенства экви- эквивалентны следующим неравенствам: ^P < 4 log 2, G) I = lim ФМ ^ log 2. (8) Доказательство неравенства G). Биномиальный коэффициент ~U/ ~~ 1-2.3...л обладает следующими свойствами: (I)ЛЛ есть целое чис- число, которое является наибольшим членом в биномиаль- биномиальном разложении выражения A + 1Jп, содержащем B/г+1) членов, так что N<22n, 22n<Bn+l)N; (9) (ii)N делится на произведение всех таких простых р, что п<Ср^.2п, так как эти простые входят в числитель Af и не входят в знаменатель. Поэтому, согласно свойству (ii), мы имеем N^ Д р и, следовательно, п<Р<2п /г<р<2/г Но из (9) мы получаем, что log Л^<2я log 2. Значит, OBai)— О (л) <2n log 2. A0) Если мы положим в неравенстве A0) я=1, 2, 22, ...,2m~I и сложим полученные неравенства, то получим
§2. Теорема Чебышёва 93 или, поскольку 0A) =0, OBm)<2m+llog2. (И) Пусть теперь х>1 и т — положительное целое, та- такое, что 2m-1^#<2m. Так как функция $(х) неубываю- неубывающая, из (И) следует, что О(х) <OBm) <2m+1 log 2<4x log 2. Следовательно, d(x)/x<4 Iog2, откуда вытекает, что L = lim —^- <С д;->оэ X Тем самым неравенство G) доказано. Доказательство неравенства (8). Доказательство второй части теоремы Чебышёва проводится другим спо- способом. Оно основано на важной формуле для показате- показателя, с которым простое число р входит в каноническое разложение т. Мы говорим, что простое число р входит в канониче- каноническое разложение целого п с показателем k, если ph\n и pk+l\ nl\ Лемма. Показатель, с которым простое число р вхо- входит в ml, равен причем последний ряд конечен, так как [х]=0 для 01 Среди чисел 1, 2,..., m имеется точно [пг/р] кратных /7, а именно !) Мы будем говорить также, что простое р входит в п с показа- показателем k. — Прим. перев.
94 Гл. VII. Теорема Чебышёва рЛр [j]p, A2) точно [т/р2] кратных р2, а именно \ A3) и т. д. Число целых чисел между 1 и т, которые делятся на рг, но не делятся на рг+\ в точности равно [tn/pr] — — [m/pr+l]. Следовательно, простое число р входит в ml с показателем лемма доказана. Для того чтобы доказать неравенство (8), рассмотрим целое число лг /2/Л B/1I Пусть р — простое число, р^2п. Тогда р входит в числи- числитель N с показателем а в знаменатель — с показателем Таким образом, р входит в N с показателем и, следовательно, Поскольку -? = -^ =0 при рг>2пу или, что то же самое, при
§2. Теорема Чебышёва 95 r>\bSLl L bgp J мы имеем Кроме того, для любого действительного числа у , или 2[у]^2у<2[у]+2 Отсюда следует, что —1 < [2у]—2[у] <2, откуда [2у]-2[у]=0, или [2у]-2[у] = 1. A6) Следовательно, используя соотношение A5), мы полу- получаем, что vp^Mp и тогда р<2п р<2п С другой стороны, из E) и A5) мы имеем p<2nl gP J p<2n так что р<2п откуда в силу A7) Далее, из (9) следует, что Следовательно, для любого положительного целого чис- числа п мы имеем —logBn+l). A8) Пусть теперь х>2 — действительное число, и пусть
96 Гл. VII. Теорема Чебышёва п= [я/2]^1. Тогда ft> (х/2) — 1, 2п^х1 и из A8) мы по- получаем или X Следовательно, и теорема 3 доказана. Из теоремы 3 сразу же следует, что простых чисел бесконечно много и что ряд J^l/p, распространенный на все простые числа, расходится. Действительно, пусть рп означает п-е простое число. Тогда п(рп) =п9 и так как для достаточно больших х, то для достаточно больших значений п. Следовательно, log pn<21og и, так что арп<п log pn<2n log n оо для достаточно больших п. Сравнивая ряд 2 \/рп с рас- оо ходящимся рядом S I/ft log п, мы видим, что ряд /1=2 оо 5] 1/рп также расходится. § 3. Постулат Бертрана. Следующая теорема была сформулирована Бертраном и впервые доказана Чебы- шевым.
§ 3. Постулат Бертрана 97 Теорема 4 (постулат Бертрана). Если п — положи- положительное целое, то существует простое число р, такое, что Доказательство Чебышева этой теоремы основано на соображениях, подобных тем, которые были использо- использованы при доказательстве теоремы 3. Этот результат сна- сначала был доказан для больших значений п, а для малых значений п проверялся с помощью таблицы простых чисел. Мы приводим здесь доказательство, предложенное С. С. Пиллаи, которое довольно просто, поскольку не использует формулу Стирлинга для Г(п) и сводит число проверок к минимуму. При доказательстве теоремы Чебышева мы использо- использовали для биномиального коэффициента N = 1 ?) неравен- неравенство (9), а именно <iV<2 2/1+1 и вывели из него неравенство A1), а именно log 2. (И) Для доказательства того, что неравенство A1) выполня- выполняется не только для степеней числа 2, но также для всех положительных целых чисел п9 т. е. ®(n)<2n\og2, л>1, A9) нам потребуется более точная оценка -±—<ЛГ<~, n>2. B0) 2Vn V2n Доказательство оценки B0). Положим р = 1-3-5...B/1 — 1) 2-4-6...Bл) Поскольку р _ 1-3-5...B/1—1) 2-4-6...Bп) = Bп)! ~~ 2-4-6...Bл) ' 2-4-6... B/г) ~~ 22л(/г!J '
98 Гл. VII. Теорема Чебышёва мы имеем 22п P = N. Очевидно, что справедливо неравен- неравенство которое может быть переписано в виде 1 > (hi) (^1) (tl) (Pn—l)Bn+l) \ 22 / \ 42 / \ б2 / *\ BпJ или в виде • = — N\ Отсюда следует второе неравенство в оценке B0). Подобным же образом мы имеем неравенство 5»А 72)"Л Bп-1J/' которое может быть записано в виде 52 )\ 72 J-\ B/г- или в виде 24/г 1> 4/гР2 Отсюда следует первое неравенство в оценке B0). Та- Таким образом, оценка B0) доказана. Доказательство неравенства A9). Неравенство оче- очевидно для п—\ и п = 2. Предполагая неравенство спра- справедливым для некоторого п^2, мы выведем отсюда, что OBft—l)<2Bft—1)log 2, откуда будет следовать соот- соотношение ЪBп) = Ц2п— 1) <4м log 2. Рассмотрим целое число N_=l_Bn\_(^i)[ п _ B/i — 1)8 _Bп— 1) 2 ~~ 2 \п)~ (п\у'2п ~~ п\{п— 1)! ~U— 1 / Оно делится на все простые р, такие, что п<:р^2п—1, а следовательно, и на их произведение. Значит, N \ тт У> П Р п<р<2п—1
§3. Постулат Бертрана 99 или, после логарифмирования, logf >вBп-1)-в(п). Но из B0) мы имеем log N < 2п log 2 — \- log 2п. Объединяя оба эти неравенства, получаем ОBд— 1) — ®(п)<Bп — I)log2 — ^-Iog2tt. Но по предположению О(п) <i2n log 2. Следовательно, tt — I)log2 — ^Iog2n, откуда следует, поскольку п^2, что /i— I)log2, т. е. мы пришли к искомому неравенству. Таким обра- образом, если A9) доказано для некоторого положительного целого числа п^2, то оно будет выполняться также и для 2п—1, а следовательно, и для 2п. Другими сло- словами, если ®(п) <с2п log 2 для каждого целого числа из интервала вида то это неравенство справедливо также для всех целых п из интервала гг+1 Отсюда по индукции следует, что неравенство A9) спра- справедливо для всех ^\ Неравенства A9) и B0) потребуются нам при дока- доказательстве теоремы 4. Доказательство теоремы 4 (С. С. Пиллаи). Для того чтобы доказать теорему 4, мы докажем неравенство 1&Bп) — О(п) >0 для всех п^26 и проверим это неравен- неравенство для 1^26
100 Гл. VII. Теорема Чебышёва Рассмотрим снова биномиальный коэффициент (см. A7)) г>Л Тогда logyV=S vplogp. B1) р<2п В последней сумме интервал суммирования по р мы ра- разобьем на четыре интервала: (i) n<p^2n; (ii) |/2д<р< (ii) ^-<р<п; (iv) «3 В соответствии с этим указанная сумма разобьется на четыре суммы ?1р Ц2> Из, ^4. В ^]x мы имеем п/р<1 и 1^2п//?<2, так что [п/р] = = 0, [2/г/р] = 1 и [2ft/p2] = 0. Следовательно, vp = l, и мы получаем = 2 logp=*BM)-«'(n). B2) В Xj2 мы имеем 1^п/р<сЗ/2, так что [м/р]^1 и [2п/р] = 2. Кроме того, [2п/р2]=0 при п^З и, следо- следовательно, Ц2=0, п^>3. B3) В 2з мы имеем п^Ъ и njp2<i2nlp2<i\, так что vp = = [2п/р]—2[д/р] = 0или 1 (см. A6)). Следовательно, 2з< 2 У2п<р<2«/3 Но ^)= Ц Iogp>log2 2 P<Y2n
§3. Постулат Бертрана 101 и поэтому Ц(^)-яA^Iо§2. B4) В 5j4 мы используем неравенство Чебышева (см. A7)) и получаем Afplogp< Таким образом, (^?) B5) Объединяя соотношения B1) —B5), мы приходим при Ъ к неравенству /i) - * (л) + Ц^\ - n{V2n) (log 2 - log 2/i), которое можно переписать в виде log N - д/^\ - яA/2д) log /г. B6) Покажем теперь, что 1&Bп) — '&(п) >0 для всех достаточ- достаточно больших п. Для этого нам потребуются три неравен- неравенства: (b) logN >2/zlog2-logBl/^); (c) jt(/i) < у, если /г>8. Неравенства (а) и (Ь) являются следствиями нера- неравенств A9) и B0) соответственно, а неравенство (с) следует из того, что каждое четное число, большее 2, яв- является составным. Из (а), (Ь), (с) и B6) мы получаем при
102 Гл. VII. Теорема Чебышёва ft Bп) — ft(п) > 2п log 2 — log B УК) — _4п з или, что то же самое, )g2 - УЩ±\0&п. B7) Остается показать, что -^-logn>0 B8) для всех достаточно больших п. Легко видеть, что нера- неравенство B8) выполняется при п = 26. Докажем справед- справедливость этого неравенства для п>-26. Для этого перепи- перепишем B8) в виде 1 }_l >>0 B9) 2 log 2 Iog2 УАп~ } и заметим, что при х^26 (мы заменили п действительным переменным х) функции 3 \ogx и _ ЗУ2 \ogVbc_ и 2 log 2 log 2 имеют положительные производные. Значит, в указанной области эти функции возрастают, и так как их сумма по- положительна при х = 26, то она будет оставаться положи- положительной и при х>-26. Следовательно, -0B/1)— O(/i)>0, п^2\ C0) т. е. постулат Бертрана справедлив при /2^26 = 64. Далее, в последовательности 2, 3, 5, 7, 13, 23, 43, 67 C1) каждое простое число, за исключением первого, будет меньше удвоенного предыдущего. Следовательно, каж- каждому положительному целому числу д^бб соответству- соответствует по меньшей мере одно простое число р, такое, что
§4- Тождество Эйлера 103 . Таким образом, теорема 4 полностью дока- доказана. § 4. Тождество Эйлера. Тождество -p-r1. C2) л=1 П р где 5>1 —действительное число и р пробегает все про- простые числа, является частным случаем следующего ре- результата: Теорема 5. Пусть f — мультипликативная арифмети- арифметическая функция и ряд J] f(n) абсолютно сходится. Тог- да имеет место тождество я=1 р причем произвебение в правой части также сходится аб- абсолютно. Далее, если f вполне мультипликативна, т. е. f(mn) = = f(m)f(n) для всех положительных целых чисел т, п} то оо ?/<«) = ПО-/(/>)) • C4) я=1 Р Доказательство. Из мультипликативности функции / мы имеем /A) = 1. Положим р<х Так как Р(х) является произведением конечного чис- числа абсолютно сходящихся рядов, то, перемножив эти ря- ряды, мы получим где п' пробегает все положительные целые числа, кото- которые не имеют простых делителей, больших х. Положим оо S = ?/(«). я=1
104 Гл. VII. Теорема Чебышёва Тогда P(x)-S = -%f(n"), где п" пробегает все положительные целые числа, имею- имеющие по меньшей мере один простой делитель, боль- больший х. Очевидно, п">х, так что n>x Далее, 2 |/(^)|-^0 при x->oo, так как по предположе- п>х оо нию ряд J] \f(n)\ сходится. Следовательно, limP(*) = = S и тем самым тождество C3) доказано. Произведение в правой части равенства C3) сходит- сходится абсолютно, поскольку 2 \f(p) + Нр2) + ...|<2 (If(p)l + IfHi +•..)< оо <2|f(rc)|<oo. C5) Рассмотрим теперь случай, когда / вполне мульти- мультипликативна. Из C5) мы видим, что ряд где суммирование ведется по всем простым /?, сходится. Но тогда f(pn) — (f(p))n и, следовательно, ряд тоже сходится. Члены последнего ряда образуют геомет- геометрическую прогрессию, откуда \f(p)\<.l. Значит, л=1 и теорема 5 доказана.
§4- Тождество Эйлера 105 Тождество Эйлера следует теперь из C4), если мы положим f(n) = n-s, 5>1. Пусть где 5>>1 действительное. Тогда v r J ^mpmsl P rn,p r где р пробегает все простые числа, а т пробегает все по- положительные целые числа. Почленное дифференцирова- дифференцирование даст нам ""' p~s Следовательно, при действительном iM=V^ C6) где А(п) — функция Мангольдта, определенная в § 5 гл. VI. Заметим, что почленное дифференцирование до- допустимо, поскольку оба ряда ^] log (l —p~s) и V-—Ц? р р равномерно сходятся при s^l+6>l. Правая часть равенства C6) представляет собой ряд оо Дирихле вида 2 ann~s, коэффициенты ап которого яв- /2=1 ляются значениями функции Мангольдта Л (п). Исполь- Используя равенство C6), мы покажем, что если какая-либо из функций x/logx ' х ' х имеет предел при х->оо, то этот предел должен быть ра- равен 1. Из теоремы 2 мы уже знаем, что если какая-либо
106 Гл. VII. Теорема Чебышёва из этих трех функций имеет предел при х->оо, то две другие функции также будут иметь пределы и все эти три предела равны между собой. Рассмотрим функцию ty(x)/x и воспользуемся соотно- соотношением В дальнейшем нам потребуется тождество ^-dx (s действительное, s>l), которое можно получить из формулы суммирования Абеля. Теорема 6 (Абель). Пусть 0^Я1^Я2^... — последова- последовательность действительных чисел, такая, что ^п-^оо при п->оо, и пусть (ап)у п—1, 2,..., — последовательность комплексных чисел. Пусть, далее, Л(х) = ^ ап и у(х) — комплекснозначная функция, определенная при Тогда 1)- Ф(я„)). C7) Если ф имеет непрерывную производную на интервале @, оо) и х^Ки то C7) может быть записано в виде ? = А(х) ф (дг) - j Л@ ф'@ Л. C8) Если, кроме того, А(х)ср(х)-+-0 при х-^оо, то '{t)dt C9) при условии, что ряд в левой части и интеграл в правой части сходятся.
4- Тождество Эйлера 107 Доказательство. Положим A(Xq)=O. Тогда мы имеем /2=1 /2=1 = A(\k)<i>(Xk) - J А(кп){<р(Кп+1) - ф(Л,я)); /2=1 тем самым равенство C7) доказано. Пусть k — наи- наибольшее целое число, такое, что Xk^x. Так как ф имеет непрерывную производную q/, то сумма в правой части C7) равна п=1 л+1 п) J <p'(t)dt, а так как Л (f_) — ступенчатая функция, постоянная в ин- интервале Xh^t<Zkk+i, то первый член в правой части C7) равен Л (К) Ф (К) = Л (х)ф) - J А (О Ф' (О Л. Таким образом, я) = А (х) ф) - | А (О Ф' @ dt и равенство C8) также доказано. Наконец, мы получим равенство C9), если в C8) устремим х к бесконечности. Теорема 6 тем самым доказана. Положим Яп=п, ап=А(п) и q>(x) = x~s (s действи- действительное, 5>1). Тогда A(x) = ty(x) и А(х)ц(х) -^0 при *-*-оо, поскольку Ц(х) ^n(x)\ogx<?x logх (см. доказа- доказательство теоремы 2), так что A(x)<p(x)=O(xl~s\ogx) = = оA). Следовательно, мы получаем из C6) и C9) при действительном s>l
108 Гл. VII. Теорема Чебышёва Теперь мы можем доказать следующую теорему: Теорема 7. hm ./ ; < 1 < lim ; Доказательство. Покажем, что lim 2i2- < 1< lim и затем воспользуемся теоремой 2. Пусть f(s) = — для действительного s>>1, и пусть х V = Hm (s— l)fE), U = Ш (s— l)f(s). Очевидно, /^L и /'^Z/. Докажем сначала, что ^Z/^L, а затем, что V = L'=\. Вместе эти неравенства дадут утверждение теоремы 7. Пусть 5>L. Тогда ty(x)/x<:B для всех л:^хо= =xoE), и мы можем предположить, что хо>1. Из фор- формулы D0) мы имеем при 1 1 так что *0 s — Последнее неравенство можно переписать в виде (s—l)f(s)<s(s—l)K+sB, где
§4- Тоэюдество Эйлера 109 Пусть 5->1+0. Тогда мы получаем, что L'^B, и так как это неравенство выполняется для любого B>L, то L'L. Аналогично можно доказать, что 1^.1' и потому Покажем теперь, что lim (-(s- lim (S- s-1 + 0 Отсюда будет следовать, что (s—l)f(s)—>1 при 5->1+0, а значит, и равенство /'=//= 1. Функция x~s при s>l является убывающей функци- функцией переменного х, так что X* 1 л==1 1 Таким образом, откуда следует, что (s—I)^(s)->1 при s->l+0. С другой стороны, при s>l и х^е функция также является убывающей по х, так что ^ откуда после подстановки л:8" = еУ мы получаем Таким образом, при 5->1+0. Следовательно, //=L/=1, откуда
110 Гл. VII. Теорема Чебышёва Объединив этот результат с теоремой 2, мы получаем утверждение теоремы 7. Из теоремы 7 вытекает, что если предел функции я **' при х-^оо существует, то этот предел должен xllogx быть равен 1. § 5. Некоторые формулы Мертенса. Теорема 8. При х->оо мы имеем \№L = \ogx + O A), 2 ^?~ = 1о§ х + ° A)> D1) р<Х р<Х где С — некоторая константа. D2) D3) Доказательство. Мы используем слабую форму фор- формулы Стирлинга, а именно log(m\) = m log m-\- О(т) D4) при т-^оо. Из теорем 2 и 3 мы знаем, что при т-^оо ц(т)=0(т). D5) Далее, по лемме, полученной в ходе доказательства тео- теоремы 3, мы имеем р<т ИЛИ log(m!) = 2 [^1 logP = 2 [т1Л(")' <46) pT<mLH J n<mL гдеЛ(п) —функция Мангольдта [см. C)],
§5. Некоторые формулы Мертенса 111 Чтобы доказать D1), положим в формуле D6) т \ т " где 0^еп<1. Тогда, используя D5), мы имеем log(m!)= Y^A(n) + O(m) П п<т и, применяя D4), Заменяя теперь целое число т действительным перемен- переменным х, мы получаем первую из формул D1). Вторая фор- формула следует из неравенства р<х p<x <O°- <L ntn-I) < р(р -1) Используя D5), мы можем вывести из D1) формулу D2). Действительно, if@= ]S Мп)у и тогда при J 1 n<t Наконец, формула D3) может быть выведена из D1), если использовать формулу суммирования Абеля. Пусть (рп) — последовательность простых чисел, занумерован- занумерованных в порядке их возрастания, и пусть =%ап, где ап=
112 Гл. VII. Теорема Чебышёва = 2 ьа, где Ьп=±. Тогда по теореме 6 мы имеем при R/v\ — V пп — A№ _l_ Г Л <"> dU ~ \ogpn log л: ^ w(logw)^ Далее, в силу второй из формул D1) мы имеем А(х) = = logx+?(x), где \Е(х)\<.К для всех х^2 при неко- некоторой постоянной К. Следовательно, w log и J u(logu) Так как |?(jc)|</(, то интеграл f 71 ч2 du сходится, и тогда В(х) = log log a: + A — log log 2 - где ; \ogx J «(logwJ так что при |?*(X)|<_^L. log л: Таким образом, формула D3) доказана.
ГЛАВА VIII ТЕОРЕМЫ ВЕЙЛЯ О РАВНОМЕРНОМ РАСПРЕДЕЛЕНИИ И ТЕОРЕМА КРОНЕКЕРА § 1. Введение. Мы видели в гл. III, что для любого заданного иррационального числа | найдется бесконечно много рациональных чисел p/q, таких, что |g—р1я\< <1/<72. Из этого результата следует теорема Дирихле о том, что каждому иррациональному числу | отвечает бесконечно много пар целых чисел р и q, таких, что q\ отличается от р на сколь угодно малую величину. Дей- Действительно, для данного е, 0<е<1, рассмотрим целое число 1 + [1/е]. Поскольку существует бесконечно много рациональных чисел p/q, таких, что \q%—р|<1/<7, то существует бесконечно много дробей p/q со знаменате- знаменателями q^l + \l/s], для которых \ql—p|<cl/<7<e. Теорему Дирихле можно обобщить следующим обра- образом. Если заданы иррациональное число 0, произвольное действительное число а и положительные действитель- действительные числа N и s, то существуют целые числа пир, та- такие, что п> N и \пв — р — а| < е. Если а=0, то этот результат сводится к упомянутой вы- выше теореме Дирихле. Если 0<а<1 и е — сколь угодно малое положительное число, то последнее неравенство означает, что дробная часть я8, а именно {nQ}=nQ— — [nQ], сколь угодно близка к а. Другими словами, чис- числа ({/18}), п=1, 2, 3, ..., всюду плотны в интервале [0, 1]. Это обобщение теоремы Дирихле является частным случаем глубокого результата Г. Вейля о равномерном распределении, который будет доказан в этой главе. Для рассмотрения вопросов, связанных с дробными частями действительных чисел, введем новые понятия. Два действительных числа Х\ и х2 называются сравни- сравнимыми по модулю 1, если их разность является целым числом. Отношение сравнимости по модулю 1 будет, оче- очевидно, отношением эквивалентности, которое разбивает все действительные числа на классы эквивалентности,
114 Гл. VIII. Теоремы Вейля и Кронекера состоящие из действительных чисел с одной и той же дробной частью. Отображение x->e2nix индуцирует вза- взаимно однозначное соответствие между этими классами эквивалентности и точками единичной окружности. § 2. Равномерное распределение в единичном интер- интервале. Пусть S — конечное множество действительных чи- чисел оц, (Х2, ..., cxq, содержащихся в интервале [0, 1), т. е. Для любых действительных чисел а и &, таких, чт«. 0^а<6^1, через ф(а, Ь) обозначим количество чисе^ а, содержащихся в интервале [а, Ь)у т. е. количество чи- чисел (Xj, для которых Величина D = sup \b p \a,b) A) называется отклонением множества S. Ясно, что ^1. Если мы обозначим интервал [а, Ь) через /, его длину через |/| и ф(а, Ь) обозначим через ф(/), то A) запишется в виде D^sup MI _|/| . A/ /c[o,i) Q Для бесконечной последовательности действительных чисел ai, a2, ... из интервала [0, 1) через Dn обозначим отклонение первых п членов этой последовательности. Мы назовем последовательность (aj) равномерно рас- распределенной, если Z)n->0 при д->оо. Пусть фп(#, Ь)=ц)пA) —число тех aj, для которых a^.a,j<.b при 1^/^д. Из определения следует, что ес- если последовательность (aj) равномерно распределена в интервале [0, 1), то Фп(Д.6)_»,(&_д) B) при д->оо для каждой пары действительных чисел а и Ь, таких, что 0^а<6^1. Справедливо и обратное утверж-
§2. Равномерное распределение в единичном интервале 115 дение: если B) выполняется для каждого такого интер- интервала [а, Ь), то последовательность (ccj) равномерно рас- распределена. Действительно, разобьем интервал [0, 1) на конечное число подинтервалов (/&), каждый из которых имеет длину б, 0<6<1. Для любого данного интервала [с, d), где 0^c<d^l, обозначим через г число интервалов Ik длины б, лежащих внутри [с, d). Их общая длина равна гб, и мы имеем гб>(с/—с)—26. Далее, если через г' мы обозначим число интервалов Ik, пересекающихся с [су d), то r'8<(d—с)+28. Поскольку B) выполняется для каждого интервала [а, Ь), то оно должно выполняться, в частности, для ин- интервала Ik длины б. Таким образом, для заданного е>0 существует число А^(е), такое, что для всех д>Л^(е) и всех k. Выберем е = б2. Тогда мы по- получим для всех n>N'{§). Следовательно, гвA-в)<-±- 2 ф*D)< IkC[c,d) < для всех ^г>Л//(б), откуда Так как d — с<1, то для любого интервала [с, d)C[0,1)
116 Гл. VIII. Теоремы Вейля и Кронекера при д>Л^/(б) и при б, не зависящем от этого интервала. Таким образом, Dn->0 при п-+оо. Итак, доказана Теорема 1. Бесконечная последовательность действи- действительных чисел (a*), t=l, 2, ..., таких, что 0^аг<1, рав- равномерно распределена тогда и только тогда, когда при п-+оо для каждой пары действительных чисел а и Ь, где 0^а<&^1. Здесь фп(#, Ь) есть число тех c&j, кото- которые удовлетворяют неравенству a^aj<& при 1^/^тг. Заметим, что равномерно распределенная последо- последовательность (а%) всюду плотна в единичном интервале [О, 1). § 3. Равномерное распределение по модулю 1. Беско- Бесконечная последовательность действительных чисел (а*), не обязательно содержащаяся в единичном интервале, называется равномерно распределенной по модулю 1, ес- если соответствующая последовательность дробных частей ({аг}) равномерно распределена в том смысле, как это было определено в § 2. Таким образом, если Dn есть от- отклонение, как и в § 2, первых п членов последовательно- последовательности ({аг}), то Dn->0 при п-+оо. Мы покажем, что это условие имеет другую эквивалентную формулировку в терминах нового понятия — отклонения по модулю 1. Пусть дано множество S действительных чисел cti, аг, ..., clq, и пусть Т — это множество действительных чисел (а& + ?), где l^^^Q, a t пробегает все целые чис- числа. Для любой пары действительных чисел а и 6, таких, что 6^sa, обозначим через ф*(а, Ь) число элементов множества Г, содержащихся в интервале [a, b). Тогда Ф*(я, Ь) C) для любого целого числа t. Далее, <р*(я, 6)=ф(а, 6), если 0<а<6<1, D) гдеф(а, Ь) определена для ({a/*}), l^&^Q, так же, как в § 2.
§ 3. Равномерное распределение по модулю 1 117 Отклонением по модулю 1 множества S мы назовем величину D* = sup Q E) В последнем выражении а пробегает все действительные числа, но в силу C) мы можем предполагать, что 0^ 1 Если D — отклонение дробных частей чисел множест- множества S, то из A), D) и E) очевидным образом следует, что D^.D*. С другой стороны, мы имеем D*^2D. Дейст- Действительно, так как любой интервал [а, Ь), где 0^а<1 и Ъ—а^1, может быть представлен в виде объединения не более двух непересекающихся интервалов, каждый из которых имеет вид [а\ У), где или 0^а'<&'^1, или 1<а'<&'<2, то ф*(а, Ь) = ?Ф*(а', У), Ь-а = % {b'-а'), где каждая из сумм состоит не более чем из двух членов, и тогда, согласно A), C) и D), - а) <2D. Следовательно, Таким образом, для данного множества S действи- действительных чисел (aj), 1^/^Q, мы определили, во-первых, отклонение D множества их дробных частей ({о^}) и, во-вторых, отклонение Z)* множества S по модулю 1 и по- показали, что ?><D*<2D. F) Пусть (ai) — бесконечная последовательность дейст- действительных чисел, не обязательно содержащаяся в единич- единичном интервале. Обозначим через Dn отклонение первых п членов соответствующей последовательности дробных ча- частей ({щ}), а через D* — отклонение по модулю 1 первых п членов этой последовательности. Из F) следует, что если Dn->0 при п->оо, то и ?>*->0 при п->оо, и обратно. Таким образом, нами доказана
118 Гл. VIII. Теоремы Вейля и Кронекера Теорема 2. Бесконечная последовательность действи- действительных чисел (а%) равномерно распределена по модулю 1 тогда и только тогда, когда D*n ->0 при п-+оо9 где D* — отклонение по модулю 1 первых п членов этой последова- последовательности. § 4. Теоремы Вейля. Теорема 3. Пусть (aj) — бесконечная последователь- последовательность действительных чисел, такая, что 0^aj<l при /= = 1, 2, .... Для того чтобы последовательность (osj) бы- была равномерно распределена, необходимо и достаточно, чтобы выполнялось соотношение G) для любой интегрируемой по Риману на отрезке функции f. Доказательство. Мы можем считать функцию f дей- действительнозначной— в противном случае можно отдель- отдельно рассмотреть ее действительную и мнимую части. Достаточность условия G) доказать нетрудно. Для любого данного интервала [а, 6), где 0^а<6^1, возь- возьмем в качестве f характеристическую функцию [а, Ь)\ [(#) = 1 при a^x<ib и f(#)=0 в противном случае. Тогда 4/K)=^ (8) 1 и f f{x)dx=b—a. Тогда из G) следует, что цт М^> = Ь_а, (9) и, значит, по теореме 1 последовательность (aj) являет- является равномерно распределенной. Обратно, если (aj) равномерно распределена, то име- имеет место соотношение (9), и тогда G) выполняется для
§4- Теоремы Вейля 119 характеристической функции / любого интервала [а, Ь), содержащегося в интервале [0, 1], а в силу линейности G) выполняется для любой ступенчатой функции на [О, 1]. Если функция / интегрируема по Риману на от- отрезке [0, 1], то для данного е>0 можно найти две та- такие ступенчатые функции /i и /2, что f\^f^f2 и 1 ИЫ*)—fi(x))dx<.s. Так как соотношение G) выпол- о няется для fu то мы имеем так что при достаточно большом п /i=l о Далее из неравенства f^f\ для достаточно большого п следует, что j-?/K)> U(x)dx-2s. /i=l О Аналогично, для достаточно большого п /i=l Таким образом, для достаточно больших значений п мы имеем <2е, /i=i и этим соотношение G) доказано для каждой интегри- интегрируемой по Риману на отрезке [0, 1] функции. Теорема 4. Пусть (|3j) — бесконечная последователь- последовательность действительных чисел, не обязательно содержа-
120 Гл. VIII. Теоремы Вейля и Кронекера щаяся в единичном интервале. Для того чтобы последо- последовательность (Cj) была равномерно распределена по мо- модулю 1, необходимо и достаточно, чтобы выполнялось со- соотношение п LJ2m'm^ = o (Ю) для каждого целого пгФО, где i2 =—1. Доказательство. Пусть (Pj) равномерно распреде- распределена по модулю 1, и пусть (Xj обозначает дробную часть |3j. Тогда последовательность (c&j) равномерно распреде- распределена в единичном интервале. Если мы возьмем f(x) = = e2mmx f где m целое и тфО, то из теоремы 3 вытекает соотношение = \ e2nimxdx = а так как аи отличается от $h на целое число, это озна- означает, что справедливо соотношение A0). Обратно, если A0) выполняется для каждого целого О то «— П a=i Покажем, что в этом случае условие G) будет выпол- выполняться для каждой интегрируемой по Риману на отрез- отрезке [0, 1] функции. Очевидно, G) имеет место для f(x) = = 1 и по нашему предположению для f(x)=e<2nimx, где т — целое число, отличное от нуля. Тогда оно будет вы- выполняться также для любого тригонометрического поли- полинома вида a0+(alcos2nx+bisin2nx)+... +(а где а\ и bi—константы. Далее, любая непрерывная пе- периодическая функция f с периодом 1 может быть ап- аппроксимирована тригонометрическим полиномом такого
§4- Теоремы Вейля 121 рода. Это означает, что для данного s>0 существует тригонометрический полином f&, такой, что \f-fs 1<е. Пусть fx=fe—e и /2=fe + e, так что fi^f</2 1 и J (/г(#) — fi(#))d# = 28. Так же, как при доказательст- о ве теоремы 3, мы получаем отсюда, что условие G) вы- выполняется для любой непрерывной периодической функ- функции с периодом 1. Ограничимся теперь основным интер- интервалом [0, 1]. Для любой ступенчатой функции / на от- отрезке [0, 1] можно найти две непрерывные периодиче- периодические функции f\ и /2, такие, что Следовательно, G) выполняется для любой ступенчатой функции /, определенной на отрезке [0, 1], а тогда, как было показано выше, оно будет выполняться для любой интегрируемой по Риману на отрезке [0, 1] функции. Теорема 4 доказана. В качестве приложения теоремы 4 докажем следую- следующий результат: Теорема 5. Если | — любое иррациональное число, то бесконечная последовательность (я|), п=19 2, ..., рае- номерно распределена по модулю 1. Доказательство. Пусть m — целое число, отличное от нуля, и пусть т|=т). Покажем, что Число г\ действительное и, поскольку g иррационально, не целое. Тогда мы имеем у, 2nihi\ Л=1
122 Гл. VIII. Теоремы Вейля и Кронекера так что и из теоремы 4 теперь следует, что последовательность (ng), п = 1, 2, ..., равномерно распределена по модулю 1. Следствие. Если | — иррациональное число, то после- последовательность дробных частей ({п^}), п = 1, 2, ..., всюду плотна в единичном интервале. Понятие равномерного распределения можно распро- распространить на пространства высших размерностей. Пусть (Р№) — бесконечная последовательность точек р-мерно- го евклидова пространства, где /?^1, и пусть (XjU ХЭ2, -.., Xjp) —КООрДИНаТЫ ТОЧКИ Р(Д ПуСТЬ ujr обозначает дробную часть х$г, а именно {Xjr}9 так что 0^ajr<Cl для l^r^p. Если через {PW} мы обозначим ректор дробных частей ({хц}, {Xj2}, ..., {¦%>}), то точка {РЩ будет лежать в единичном кубе 0^*j<l, 1^/^р. Обозначим, наконец, через V прямоугольник, лежащий в единичном кубе и являющийся декартовым произведе- произведением р интервалов, а через |F|—его меру (Лебега), равную произведению длин соответствующих интерва- интервалов. Мы говорим, что бесконечная последовательность (Р<#) равномерно распределена по модулю 1 тогда и только тогда, когда соответствующая последователь- последовательность ({РЩ) равномерно распределена в единичном ку- кубе, т. е. тогда и только тогда, когда для каждого прямоугольника V, содержащегося в еди- единичном кубе, где q>n{V) означает число точек среди пер- первых п членов последовательности ({РЩ), содержащих- содержащихся в У. В одномерном случае это эквивалентно утверж- утверждению, что sup V При П->оо. -\v\ • о
§ 5. Теорема Кронекера 123 Теорема 5'. Последовательность {PW} равномерно распределена в единичном кубе тогда и только тогда, когда п Пш _!_ V e2nilmiahi+m2ah2+ ¦¦¦+mpahp] = о П Ь для каждого набора целых чисел (mh m2, ..., тр)ф ф@,0,...,0). Доказательство этой теоремы аналогично доказатель- доказательству в случае одной переменной. Отметим только, что «ступенчатая функция» может быть аппроксимирована, например, дважды непрерывно дифференцируемыми функциями, которые имеют равномерно сходящиеся ря- ряды Фурье. В качестве следствия мы получаем отсюда обобще- обобщение теоремы 5: Теорема 6. Пусть gb g2, ..., ?р — действительные чис- числа, такие, что ?ь g2, • •> ?р, 1 линейно независимы над кольцом целых чисел (т. е. не существует линейного со- р отношения вида ^1&з=1, где I и lj — целые числа и A\, /г, ..., /р, /) Ф @, 0, ..., О, 0). Тогда последовательность ng=(n|b ng2, •••, nip), n=l, 2, ..., равномерно распреде- распределена по модулю 1. § 5. Теорема Кронекера. Из теоремы 6 следует, что пос- последовательность ({nl})9 где {nl} = ({nli}9 {я?2},..., {nlv}), всюду плотна в единичном кубе. Этот результат, пред- представляющий собой содержание теоремы Кронекера, яв- является обобщением на пространства высших размерно- размерностей теоремы, упомянутой в § 1, и может быть сформу- сформулирован следующим образом: Теорема 7. Пусть 0Ь 02, ..., 6л, 1 — действительные числа, линейно независимые над кольцом целых чисел, а\, а2, ..., а& — произвольные действительные числа и N, г — положительные действительные числа. Тогда суще-
124 Гл. VIII. Теоремы Вейля и Кронекера ствуют целые числа п и ри р2, ..., ph9 такие, что tl>N U | tlQm—pm—am | < 8 для всех m=l, 2, ..., k. Приведем теперь другой вариант этой теоремы: Теорема 8. Пусть 0Ь 62, ..., Qk— действительные чис- числа, линейно независимые над кольцом целых чисел, а\, «2, •-., oih — произвольные действительные числа и Т} е — положительные действительные числа. Тогда суще- существуют действительное число t и целые числа ри р2, •••, pk, такие, что t>T U | tQm—pm—am | < 8 для всех гп=\, 2, ..., k. Покажем, что теорема 7 эквивалентна теореме 8. Предположим, сначала, что справедлива теорема 8, и вы- выведем из нее теорему 7. Чтобы доказать теорему 7 в приведенной выше фор- формулировке, достаточно доказать ее для 0<8т^1, где X^im^Lk. Действительно, если 1, 9i, ..., 9& линейно неза- независимы над кольцом целых чисел, то числа 1, 6^, ..., 8^, где 6j =6j—qj и (qj) —подходящие целые числа, также будут линейно независимы. Кроме того, из неравенства \nQ'm—p'm—аш|<? при целом р'т следует неравенство \nQm-рт—ат\ <е, где pm = Pm+nqm. Предположим по- поэтому, что 0<<0Ш^1 при X^m^Lk, 0<Се<с1 и что 6ь 8г, ...,8ft, 1 линейно независимы над кольцом целых чисел. Тогда по теореме 8 с k+X вместо k, Af-fl вместо Т и е/2 вместо s, примененной к наборам 6ь 8г, • •., 6л, 1 и ось ос2, .... а&, О, существуют такие целые числа р\, Рь •-, Pk+\ и действи- действительное число t, t>N-{-l, которые удовлетворяют нера- неравенствам \tem—pm—am\ <е/2, /п=1, 2, ..., k, и \t—pk+l\<&l2.
§ 5. Теорема Кронекера 125 Так как t>N-{-l и e<Cl, из последнего неравенства сле- следует, что pk+i>t—e/2>N9 а так как О<0т^1, то \pk+lQm—рт—ат\ < \tQm-рт,—От ^ | tQm—pm—am при всех m=l, 2, ..., k. Отсюда следует справедливость теоремы 7, если положить п=рь,+1. Обратно, будем считать справедливой теорему 7 и докажем теорему 8. Если k=l, то теорема 8 очевидна. Предположим, что k>\. Далее, достаточно доказать теорему для 9т>0, т=1, 2, ..., k. Пусть 9ь 02, ..., 0^ ли- линейно независимы над кольцом целых чисел. Тогда числа 1 Pg> Щ— 1 1 будут также линейно независимы. Из теоремы 7 с N= = TQki примененной к наборам чисел Вх 02 0/г_ e* и следует существование целых чисел р\, р2у .., pk-i и я, ~т, таких, что Се, т= 1,2,...,k— 1. Положим теперь t = n/Qk. Тогда />>Г и Кроме того, очевидно, что |/0/t—п\ <Се, и мы получаем утверждение теоремы 8 для наборов чисел 01, 02, ..., Qk И Oti, C62, ••-, CCk—Ь 0. Аналогичным способом мы можем доказать теорему 8 для наборов 0Ь 02, ..., Qk и 0, 0, ..., 0, а*. Отсюда мы можем заключить, что теорема 8 справедли- справедлива для наборов чисел 0i, 02, ..., Qk и аь а2, ..., aft.
126 Гл. VIII. Теоремы Вейля и Кронекера Действительно, если разность между tQm и ат сколь угодно мало отличается от некоторого целого числа, а разность между t'Qm и рт также сколь угодно мало от- отличается от целого числа, то разность между (t-\-t')Qm и ccm+pm обладает тем же свойством. Таким образом, эквивалентность теорем 7 и 8 доказана. Дадим теперь доказательство теоремы 8, предложен- предложенное Бором. Доказательство теоремы 8. Если с — действительное число, Г>0 и /2 = —1, то lim^( г-- Т J A, если с = 0. Таким образом, если cv —действительные числа и V г х@= SVCv • с«^с« ПРИ т^п> 00 v=l ТО Г lim — J %(t)e~Cvttdt = bv. A2) Пусть m=l где tf — действительное переменное и Очевидно, Если теорема 8 справедлива, то для некоторого достаточ- достаточно большого t каждое число tQm—am сколь угодно мало будет отличаться от некоторого целого и тогда ср(/) сколь угодно мало будет отличаться от k-\-\. Действительно, если xm=tQm—am, то для данного s>0 найдется 6>0,
§ 5. Теорема Кронекера 127 такое, что если \хт—рт\ <Сб для некоторого целого числа рп>то\еШх>»-1\<г. Обратно, если ф(/) сколь угодно мало отличается от k-\-\ для некоторого достаточно большого t, то каждый член в сумме A3) должен как угодно мало отличаться от 1, поскольку ни один из этих членов по абсолютной величине не превосходит 1, и тогда теорема 8 должна быть справедливой. Мы можем доказать это следующим образом. Если существует такое т), 0<11<1, что (p(t)^z ^ft+1—т), и если z = e2niXm = x + iy9 то \у\^2г\1^. В са- самом деле, k + 1 -т, <Ф@ < (k- 1) + 11 + еЫХт\ или еШХт\>2 — ц при т = Отсюда мы получаем, что \1+г\*=A+хJ+у*=A+хJ+A-х*)= ^B—riJ>4—4т|, так что l^x^l—2т). Далее, Значит, \у\ ^2г]1/2, и потому \г—11 <4г]1/2, Следовательно, теорема 8 будет доказана, если мы по- покажем что limcp(/)>&+ 1. A4) Пусть г|)=г|)(хь х2, ..., xk) = l+xl+x2+...+xk и р — положительное целое число. Тогда V= S <*n1,....nkx*x»:..x»k9 A5) где коэффициенты ап nk обладают следующими свой- свойствами: (i) a,n1 nk положительны; (ii) ^]^n ,...,nk = =a|)p(l, 1, ..., l) = (^-fl)p; (iii) их количество не пре- превосходит {p-\-\)k.
128 Гл. VIII. Теоремы Вейля и Кронекера Рассмотрим теперь m=l Если в разложении A5) мы возьмем e2m^el~aj) вместо х}, то Fp{t) будет суммой вида A1), где роль cv играют числа 2л(я101 + ... + яь0ь). Так как Qj линейно независи- независимы, то числа cv различны. Роль bv в (И) будут играть числа ап± rt/fe, умноженные на e-2ni(niai+-+nkak).Следо- e-2ni(niai+-+nkak).Следовательно, A6) Поскольку ф(/)^&+1, для доказательства неравенст- неравенства A4) достаточно будет показать, что неравенство A7) не может иметь места. Неравенство A7) означает, что для всех достаточно больших t и, следовательно, что т т Шп - f Однако откуда так что каждый коэффициент в разложении A5) будет удовлетворять неравенству
§ 5. Теорема Кронекера 129 Поскольку имеется самое большее (p+l)k таких коэф- коэффициентов, мы имеем Но так как |x=V(ft+l)<l и \ip(p+ l)fe->0 при то отсюда следует, что неравенство A7) не может иметь места. В таком случае справедливо неравенство A4), а тем самым и теорема 8.
ГЛАВА IX ТЕОРЕМА МИНКОВСКОГО О ЦЕЛЫХ ТОЧКАХ В ВЫПУКЛЫХ МНОЖЕСТВАХ § 1. Выпуклые множества. В гл. VI мы столкнулись с задачами о числе целых точек в некоторых областях на плоскости. Пусть Rn, n^\, есть n-мерное евклидово пространство. Точку пространства мы назовем целой, ес- если все ее координаты — целые числа. В этой главе мы докажем теорему Минковского о том, что каждое вы- выпуклое симметричное относительно начала координат множество в пространстве Rny объем которого больше 2П, содержит по крайней мере одну целую точку, отлич- отличную от начала координат. Определения. Пусть S — множество точек простран- пространства Rn. Для действительного числа X через XS мы обо- обозначим множество, получающееся из S растяжением в X раз, т. е. XS = [Xx\xeeS]. Мы говорим, что множество S выпукло, если из ус- условия x^S, y^S следует, что Xx + \iy^S для всех дейст- действительных X и \i, таких, что А,^0, ц^О, А,-г^=1. Если множество S выпукло, то XS также выпукло. Мы говорим, что множество S симметрично относи- относительно начала координат, или просто симметрично, если из условия xg5 следует, что —x^S. Если S симмет- симметрично, то множество XS также симметрично. Пусть g— целая точка пространства Rn. Тогда мно- множество Sg, состоящее из точек x^Rny таких, что х—g^S, мы назовем трансляцией множества S на вектор g. Если множество S измеримо по Лебегу и V(S) — его мера, то F(S) = F(Sg) для любой целой точки g. Выпуклые симметричные множества, (а) Пусть мно- множество S выпукло и симметрично, и пусть x^S. Тогда Xx(=S для каждого действительного числа X, такого, что Действительно, если x^S, то из симметричности мно-
§2. Теорема Минковского 131 жества S следует, что —x^S, а тогда при \К\ ^1 из ус- условия выпуклости S мы имеем (Ь) Пусть множество S выпукло и симметрично, и пусть xeS, #&S. Тогда Xx+py^S для всех действи- действительных К и \i, таких, что |А,| + |м,|^1. Если К=0 или |i = 0, то свойство (Ь) сводится к свой- свойству (а). Предположим поэтому, что КфО и |i^0, и по- положим 8i = sgn^, 82 = sgn|i. Тогда из свойства (а) и условия |К +1\х| ^ 1 мы имеем х' = е' (| А, | + | ц, |) л: <^ S, '(|Я| + |)yeS. Положим Тогда р>0, а>0 и p+a=l, а так как S выпукло, то px' + ay'^S. Но px' + ay' = Xx+\iy, и тем самым мы полу- получаем свойство (Ь). § 2. Теорема Минковского. Теорема 1 (Минковский). Пусть S — ограниченное измеримое выпуклое симметричное множество точек про- пространства Rn, и пусть его мера V удовлетворяет нера- неравенству У>2П. Тогда S содержит по крайней мере одну целую точку, отличную от начала координат. Мы дадим доказательство этой теоремы, предложен- предложенное К- Л. Зигелем и основанное на формуле для меры ограниченного измеримого выпуклого симметричного множества, не содержащего целых точек, отличных от начала координат. Предположение об ограниченности множества S в теореме 1 не является необходимым (см. теорему 3 и примечания к гл. IX). Доказательство теоремы 1 (Зигель). Пусть S — огра- ограниченное измеримое выпуклое симметричное множество в Rn и V — его мера. Обозначим через L2(S) множество функций, интегрируемых с квадратом на S. Пусть cp^L2(S), и пусть ф(я)=0 при ^S
132 Гл. IX. Теорема Минковского Мы будем употреблять, как обычно, запись k=(ku k2, ..., kn), х=(хи х2, ..., хп), k-x=klxl+k2x2+... ...-\-knxn и dx=dxidx2...dxn. Рассмотрим функцию /(*) = 2<pB*-2*), A) k где k пробегает множество всех целых точек пространст- пространства Rn. Для любого данного х эта сумма конечна, так как Ф равна нулю вне S и S ограничено. Поскольку k пробе- пробегает все целые точки, эта сумма остается неизменной при подстановке kv—> kv-{-\. Следовательно, f(x) является периодической функцией по каждому переменному Х\, *2, .-., хп с периодом 1. Формула Парсеваля для ряда Фурье функции / дает ?12. B) Е I где Е есть n-мерный куб со стороной 1, / — целые точки в Rn и ai— коэффициенты Фурье функции /: [ §(x)e-2"ilxdx. C) Е Из A) мы имеем *=12фBх ~2k) e~2nilx dx =S IфBх ~2k) е~2Шх dx> E k k E где k пробегает все целые точки пространства Rn. Поло- Положим х—k=t. Если х пробегает точки единичного куба ?", a k пробегает все целые точки, то t пробегает все точки пространства Rn. Следовательно, al= j <pBt)e-2nllik+t)dt = Rn Если мы положим 2t=x, то, поскольку функция ф равна нулю вне множества S, получим ilx. D)
§2. Теорема Минковского 133 С другой стороны, из A) мы получаем Е k k S Тогда, применяя B), D) и E), имеем )dx = е-""* dx dx. E) F) Далее, если ц)(х—2k)q)(x) / ', TO и х — 2k<=S. По- Поскольку S симметрично и выпукло, —x + —Bk — х) = =k<=S. Следовательно, если S не содержит целых точек, отличных от начала координат, то мы должны иметь ц)(х—2k)q)(x) =0 при fe=7^0, и тогда F) сводится к соот- соотношению -mix dx G) S I ]S Возьмем теперь ф(л:) = 1 при x^S. Тогда |ф(л:)|2^л: = V и равенство G) дает s Так как —I пробегает те же самые точки, что и Z, мы мо- можем переписать последнее равенство в виде (8) что даст нам формулу Зигеля для меры V ограниченного измеримого выпуклого симметричного множества S про- пространства Rny не содержащего целой точки, отличной от начала координат. Из этой формулы следует, что
134 Гл. IX. Теорема Минковского откуда непосредственно вытекает утверждение теоремы. Если мы хотим доказать только теорему 1, а не фор- формулу (8), можно использовать вместо равенства Парсе- валя неравенство Шварца Е По формуле D) имеем s и если S не содержит целых точек, отличных от начала координат, то, согласно E), §\f\2dx=2~nV. Е Следовательно, У^2П. Теорема 1 неверна для ограниченных измеримых вы- выпуклых симметричных множеств меры V=2n. Действи- Действительно, рассмотрим множество |я<|<1, l^t^n. Оно ог- ограничено, измеримо, выпукло, симметрично и имеет меру V=2n, но не содержит ни одной целой точки, отличной от начала координат. Однако если S замкнуто, то справедлива Теорема 2. Замкнутое ограниченное выпуклое сим- симметричное множество S пространства Rn, имеющее меру V(S) ^2n, содержит по меньшей мере одну целую точку, отличную от начала координат. Доказательство. Для данного е, 0<е<1, рассмот- рассмотрим множество S'= (l + eM. Так как S измеримо, то S' также измеримо, и если через V(S) и V(S') обозначены соответствующие меры, то V(S') = (l+e)n V(S) ^2n(l+e)n >2n. Следовательно, по теореме 1 множество S' содержит це- целую точку /g, отличную от начала координат. Множест- Множество S ограничено, и таким же будет множество S\ а тог- тогда для /g имеется только конечное число возможностей. Поэтому существует целая точка /0> отличная от начала
§ 2. Теорема Минковского 135 координат, такая, что /0^(l+e)S для каждого е, 0<е< <1, т. е. /0/(l+e)&S. Если е->0, то k^S, поскольку S замкнуто. Этим теорема 2 доказана. Из теоремы 2 следует Теорема 2'. Если S — ограниченное выпуклое сим- симметричное множество, имеющее меру V(S)^2n, то его замыкание содержит по меньшей мере одну целую точ- точку, отличную от начала координат. Доказательство. Для данного ограниченного выпук- выпуклого симметричного множества S рассмотрим его замы- замыкание S. Множество S так же, как и множество S, огра- ограничено выпукло и симметрично, _? также замкнуто, и его мера V(S) ^ V(S) ^2n. Значит, S удовлетворяет услови- условиям теоремы 2 и, следовательно, содержит по меньшей ме- мере одну целую точку, отличную от начала координат. Чтобы дать другое доказательство теоремы Минков- Минковского, мы докажем сначала следующую лемму: Лемма (Г. Д. Биркгоф). Если S — измеримое множе- множество пространства Rn, имеющее меру V(S) >1, то суще- существуют две различные точки x^S и y^S, такие, что х—у есть целая точка. Доказательство. Пусть g = (g\, g2,...,gn) — какая-ли- какая-либо целая точка. Рассмотрим куб [Xi\gi^Xi<Cgi + \], i = l, 2,..., п, и обозначим через Sg пересечение множе- множества S с этим кубом: Пусть Stg—трансляция множества Sg на вектор —g (см. § 1). Тогда S?g содержится в единичном кубе 0^xt.<l, l^i^n. Если Vg есть мера множества S?g, то Vg будет также мерой множества Sg я^Уё = У>1. g Отсюда, так как единичный куб имеет меру 1, следует существование по крайней мере двух множеств Stg и S^g'y где g и gf — различные целые точки, имеющие не-
136 Гл. IX. Теорема Минковского пустое пересечение. Другими словами, существуют две точки *eS* и y^Sgf, такие, что х—g=y—g'. Следова- Следовательно, мы нашли две такие точки x<=S и y^S, что х—y=g—g' есть целая точка. (Она не обязана, конечно, принадлежать множеству S.) Лемма тем самым дока- доказана, С помощью этой леммы мы докажем следующее ут- утверждение: Теорема 3 (Минковский). Если измеримое выпуклое симметричное множество S имеет меру V>2n (возмож- (возможно, У=оо), то оно содержит по крайней мере одну це- целую точку, отличную от начала координат. Доказательство. Рассмотрим множество —S, мера A \п —) У>1. По доказанной выше лемме 1 1 существуют две различные точки x<=—S и y<=—S, та- такие, что их разность х—y = g будет целой точкой. Так же как и S, множество —S является выпуклым и симмет- симметричным. Поэтому из свойства (Ь), сформулированного в § 1, следует, что ~^Х — -^У = ^G7S' a тогда gEES и g отлична от начала координат, поскольку х и у раз- различны. Теорема доказана. Последняя теорема может быть использована для изучения однородных линейных форм. Пусть gi = aii*i+ai2*2+...+flin*n, i=l, 2, ..., п, (9) суть п однородных линейных форм от п неизвестных Хи ••-, Хп с действительными коэффициентами пц, и пусть А — определитель матрицы (#ij)« Предположим снача- сначала, что А=^=0. Эти формы определяют линейное преобразование ^-пространства в g-пространство, и если множество S вы- выпукло и симметрично в ^-пространстве, то его образ Т в g-пространстве также будет выпуклым и симметрич- симметричным, поскольку выпуклость и симметричность инвариант-
§ 3. Прилоэюения 137 ны относительно линейных преобразований. Но мера ме- меняется при линейных преобразованиях, а именно если Л то JJi^2...^n, (Ю) так что мера множества Т получается из меры множест- множества S умножением на множитель |А|. Рассмотрим линейное преобразование L пространст- пространства Rn в себя: (хи х2,..., хп)-+A\, ?2, ...,Ы- Образ целых точек при этом преобразовании называется решеткой Л пространства Rn, связанной с L. Определитель преоб- преобразования L называется определителем решетки А. Применение теоремы 3 к ^-пространству дает следую- следующий результат: Теорема 4. Пусть Л — решетка пространства Rn с определителем А=т^=0 и Р — измеримое выпуклое сим- симметричное множество, мера которого V>2n\ A| (возмож- (возможно, У=оо). Тогда Р содержит по крайней мере одну точ- точку решетки А, отличную от начала координат. Далее из теоремы 2 следует Теорема 4'. Пусть А — решетка пространства Rn с определителем Д=т^0 и Р — замкнутое ограниченное выпуклое симметричное множество, имеющее меру V^ ^2П|А|. Тогда Р содержит по крайней мере одну точку решетки А, отличную от начала координат. § 3. Приложения. (А) Рассмотрим в ^-пространстве замкнутое множество S, определенное неравенствами t=l, 2 л. A1) Очевидно, что множество S симметрично. Оно будет так- также выпуклым. Действительно, если x^S, y^S и z = fkx-\- +\ху, где Я^О, м^О, Х+\х=1, то *i-x;i + ... + ciinXn\ + \i\any\ + ••• + сцпуп\ ^ max (| ацхх + ... + ainxn \, | апух + ... + ainyn \
138 Гл. IX. Теорема Минковского Кроме того, S ограничено. Действительно, если (aij) — матрица, обратная к матрице (#ij), то из равенств п п 1% = 2 uijXj следует, что х{ = ? a^-gj и тогда | х{ | ^]. По формуле A0) мера множества S равна 2п | A\~lCiC2...cn. Соответствующее множество в g-прост- ранстве является параллелепипедом и имеет меру 2nclc2...cn. Применяя теорему 4', получаем такой результат: Теорема 5. Пусть gi, §2,---, ?п — однородные линейные формы от п переменных Х\, х2,..., хп с действительными ко- коэффициентами и определителем А^О. Если с\, с2, ..., сп — положительные действительные числа, такие, что с\С2...Сп^ |А|, то существуют целые числа х\, х2) ..., хп, не равные одновременно нулю, для которых |gi | ^сь |g2| ^ |5| Мы можем, в частности, взять сг- = |Д|1//г, t = l, 2,..., п, и получить одни и те же оценки для всех п нера- неравенств A1). Мы предполагали до сих пор, что А=^=0. Если Д=0, то легко видеть, что множество S в ^-пространстве, опре- определяемое неравенствами A1), имеет бесконечный объем, если Сг>0 для каждого J, и заключение теоремы 5 оста- остается справедливым. Рассмотрим теперь вместо A1) систему, в которой число неравенств меньше числа неизвестных, а именно: \Ь\ = \ацХ\+ ...+ainXn\^:Ci, t=l,2, ..., m, га<я. A2) Тогда множество, определяемое данной системой в ^-про- ^-пространстве, не будет ограниченным, но в силу теоремы 3 заключение теоремы 5 остается в силе, т. е. существуют целые числа хи х2,..., хп, не равные одновременно нулю, которые удовлетворяют m неравенствам A2). Заметим, что случай m<in сводится к предшествую- предшествующему случаю m = n, Д = 0. Для этого достаточно, напри- например, записать неравенство A2) при i — m точно п—т-\-\ раз.
§ 3. Прилоэюения 139 (В) В качестве второго приложения рассмотрим мно- множество Т в g-пространстве, определенное неравенством 1Ы + Ы +...+ 1Ы <с. Оно, очевидно, симметрично. Множество Т будет также выпуклым. Действительно, если |=(|ь—, ?n)e7\ |'= (;ЦГ = 1, то k=l Заметим, что при п — 2 множество Т является квадратом, а при п=3 множество Т является октаэдром. Объем Т может быть вычислен следующим образом. Множество Т состоит из 2п конгруэнтных частей, по одной из каж- каждого октанта, и та часть, которая лежит в октанте gi>0, ?2>0,..., gn>0, имеет объем 1 1—ii l-b—.—^-i 0 0 0 Следовательно, Т имеет объем V=Bc)n/n\. Если cn~^n\ |Д|, то из теоремы А' вытекает Теорема 6. Существуют целые числа хи х2, ..., хп, не равные одновременно нулю, такие, что Так как |?х?8.. .у1//г <^(\h l+ ... + |gn|), то отсюда следует Теорема 6Г. Существуют целые числа хи х2,..., хПу не равные одновременно нулю, такие, что its ? I < "НА)
140 Гл. IX. Теорема Минковского (С) В качестве третьего приложения рассмотрим в ^-пространстве множество Р, определенное неравен- неравенством Это множество симметрично и выпукло. Симметричность множества Р очевидна, а выпуклость следует из нера- неравенства 2 (Чк+vt'kf = я2 21\ + 2v 2 и'к + и2 2 rk < k=\ k=\ 2 \ r k=l Далее, объем множества Р равен „л-л/2 Следовательно, если с^2(\A\/snI/nt мы можем приме- применить теорему 4' и получить следующий результат: Теорема 7. Существуют целые числа хи х2,..., хп, не равные одновременно нулю, такие, что Эта теорема может быть распространена на общие положительно определенные квадратичные формы п Q(xl9...,xn)= 2 arsxrxs r,s=l с действительными коэффициентами ars=aSr. Мы говорим, что форма Q является положительно определенной, если Q(xi,..., #п)>0 для всех х\, х2,..., хп, отличных от 0, 0,..., 0. Определитель D матрицы (ars) называется определителем формы Q, причем D>0, если Q положи- положительно определена. Любая положительно определенная форма Q может быть приведена к виду
§3. Приложения 141 где Ik — линейные формы от Х\, х2,..., хп с действительны- действительными коэффициентами и определителем \ D. Теорема 7 может быть, следовательно, сформулиро- сформулирована таким образом: Теорема 8. Пусть Q — положительно определенная квадратичная форма от п переменных с определите- определителем D. Тогда существуют целые числа Х\, х2, ..., хп, не все равные нулю, такие, что n = nn/2/T(n/2+l).
ГЛАВА X ТЕОРЕМА ДИРИХЛЕ О ПРОСТЫХ ЧИСЛАХ В АРИФМЕТИЧЕСКОЙ ПРОГРЕССИИ § 1. Введение. С помощью элементарных рассужде- рассуждений мы показали, что простых чисел бесконечно много и что каждая арифметическая прогрессия вида 4&+1 и 4& + 3, k=l, 2, 3,..., содержит бесконечно много простых чисел (гл. III, § 3). Мы докажем теперь теорему Дирих- Дирихле о том, что существует бесконечно много простых чисел в любой арифметической прогрессии a+mk, где а и т — целые числа, /п>0, (а, т) = 1 и k пробегает все положи- положительные целые числа. Мы доказали в гл. VII, что ряд %1/р, где р пробегает все простые числа, расходится. Можно изменить предло- предложенное там доказательство и получить этот результат следующим образом. Для действительного s>l справед- справедливо тождество Эйлера и для 0<Cx<i\ мы имеем log( „ti так что при 0<х^ 1/2 log (^) < 2*. Тогда для любого простого р и действительного 5>1 мы получаем неравенство
§ 1. Введение 143 Следовательно, при 5>1 Если мы предположим, что ряд 2~ сходится, то полу- 1 1 р Р чим 22~т < 22~- Мы знаем, однако, что ?A+е) ->оо р р р р j при 8-^+0. Следовательно, ряд 2~ должен расхо- р р диться. В то время как расходимость ряда 2~ связана с по- Р Р 1 ведением ?(s)=2 — E>1)> расходимость ряда 2 ~~> к» где а и т целые, /п>0, (а, т) = 1, связана с поведением ряда Дирихле вида 2 ~Тэ где 5 и коэффициенты ап суть п=\П комплексные числа. Чтобы подготовиться к изучению этого вопроса, рассмотрим функцию ?(s) комплексного переменного 5. Пусть s=o+it, где а и t — действительные величины и i2 = — 1. Предположим сначала, что сг>1. Для дейст- действительного положительного х положим xs=esloex, где log* есть вещественный натуральный логарифм. Тогда мы имеем 1 так что ряд 2 ~т абсолютно сходится при а>1 и рав- /г=1 номерно сходится в любой полуплоскости а^1+б>1, где он определяет регулярную аналитическую функцию. Из абсолютной сходимости ряда при сг>1 и из тео- теоремы 5 гл. VII следует, что тождество
144 Гл. X. Теорема Дирихле остается справедливым для комплексных s с действитель- действительной частью с»>1. Из абсолютной сходимости ряда ][]l/ps при а>' сле" р дует, что произведение ДA — l/ps)~l при а>1 также схо- р дится абсолютно. Таким образом, в полуплоскости а>>1 функция ?(s) может быть представлена абсолютно схо- сходящимся произведением, все сомножители которого от- отличны от нуля. Следовательно, ?E)^0 при а]>1. Функция ?(s), определенная при а^>1 соотношением n=X является аналитической функцией в полуплоскости а>>0, за исключением точки 5=1, где она имеет простой полюс с вычетом 1. Для того чтобы доказать это, воспользуем- воспользуемся формулой суммирования Абеля, доказанной в теоре- теореме 6 гл. VII, с Хп = п, y(x)=x~s и ап = 1. Тогда А(х) = = [*], целой части х, и X V _L = J^l + s f-^Lrfu. *-J П Xs J iis~Tl n<x 1 " Мы имеем при а>1, что [x]/xs-*0, когда х-^оо, и что ряд 2 l/nS сходится. Положим теперь [и]=и—{и}. Тог- Тогда мы получим представление ИЛИ 0) Очевидно, 0^{а}<;1 и, следовательно, интеграл в A) сходится равномерно в каждой полуплоскости а^б>>0 и представляет собой регулярную функцию от s для а>>0. Следовательно, ?E) является мероморфной функ-
§2. Характеры 145 цией при сг>0 и имеет простой полюс в точке 5 = 1 с вы- вычетом 1. Функция ?(s) называется дзета-функцией Ри- мана. § 2. Характеры. Характером % конечной абелевой группы G называется не равная тождественно нулю комплекснозначная функция, определенная на этой груп- группе и обладающая тем свойством, что если Леб и BgG, то %(АВ)=Х(А)Х(В). Обозначим через Е единичный элемент в группе G и че- через А~1 обратный элемент для Леб. Характеры груп- группы G обладают следующими свойствами: A)%(А)фО для каждого /4gG. Действительно, если бы х(А)=0 для некоторого Леб, то %(А)%(А-1) = = Х(ЛЛ-1)=Х(?)=О, а тогда Х(С) =х(Е)х(С) =0 для каждого C^G, что противоречит определению характе- характера %. Заметим, кроме того, что %(Е) = 1. (ii) Если G имеет порядок /г, то Ah = E для каждого б. Следовательно, %(A)h = %(Ah) =%(Е) = 1, т. е. %(Л) есть корень степени h из единицы. Характер зсь обладаю- обладающий свойством %i (у4) = 1 для каждого A^G, называется главным характером группы G. (ill) Абелева группа порядка h имеет точно h харак- характеров. Докажем сначала это свойство для циклических групп. Группа G называется циклической, если она со- состоит из степеней Л, Л2,.,., АГ=Е одного элемента Л, ко- который называется образующим элементом группы G. По- Порядок г группы G есть наименьшее положительное целое число г, такое, что АГ=Е. Пусть % — характер циклической группы G. Тогда (а) % полностью определяется величиной %(Л), так как %(Ап) = (%(А))п, (Ь) из равенства АГ = Е следует, что (x(A))r=li т. е. х(А) является корнем степени г из еди- единицы; (с) если р — корень степени г из единицы, то мы можем определить характер % соотношением %(А)=р (т. е. %(Ап)=рп), поскольку если Аа1-Аа* =Ла% то ах-{- -{-а2 = а3(mod r), откуда paip°2=pa\ Так как существует
146 Гл. X. Теорема Дирихле только г различных корней степени г из единицы, из ус- условий (а) и (Ь) следует, что имеется самое большее г различных характеров группы G. С другой стороны, из (с) следует, что имеется по меньшей мере г таких ха- характеров. Следовательно, циклическая группа порядка г имеет точно г характеров. Для того чтобы доказать свойство (iii) для произ- произвольной абелевой группы G, мы используем следующий результат: каждая конечная (мультипликативная) абе- абелева группа G является прямым произведением цикличе- циклических групп. Предположим, что G=GiX-.-X^fe> где Gj, 1^/^й, — циклические группы. Обозначим через г,- по- порядок группы Gj и через Aj ее образующий элемент. Тог- Тогда для порядка h группы G имеет место равенство h = = Г\Гъ-. fk и каждый элемент A^G может быть единст- единственным образом представлен в виде А =А^А^...А^ , O^fy^rj—1, /=1, 2,..., k. Если х — характер группы G, то Пусть pj — корень степени г,- из единицы. Тогда имеется один и только один характер х группы G, такой, что X(i4j)=pj, /=1, 2,...,&, а так как pj принимает в точно- точности rj различных значений, то G имеет точно h различ- различных характеров, где h = rxr2... rk. (iv) Пусть G — конечная мультипликативная абелева группа порядка h. Из свойства (i) следует, что х(?) = 1 для каждого характера % группы G. Покажем теперь, что для любого заданного A^G, АфЕ, существует ха- характер х, такой, что %(А) ф\. Мы снова воспользуемся представлением G в виде прямого произведения циклических групп. Как и в (iii), пусть А=Аь*А*\..А*к. Ввиду того что АфЕ, не все U рав- равны нулю. Пусть, например, 1\фО. Возьмем %(А2) = = %(Лг) =.» = xDfe) = 1 и хИО =р, где 9 = eiW\ i*=-L Тогда ч(А)=р**Ф\ при 0</i<rb (v) Характеры конечной мультипликативной абеле- абелевой группы G образуют конечную мультипликативную
§ 3. Суммы характеров 147 абелеву группу G. Под «произведением» двух характе- характеров %' и х" группы G мы будем понимать характер х> определяемый следующим свойством: %(А) = % (А)%"(А) для каждого элемента A^G. Мы имеем х(АВ)=х'(АВ)х''(АВ)=х'(А)х'(В)х''{А)х''(В) = %'%" так что %'%" действительно является характером. Главный характер xi группы G является единичным элементом G. Характер %~1, обратный к характеру х» определяется соотношением х (А)=%(А-1), так что 1(А) А))К Так как ггх(АВ)=Х((АВ)^) = -1) = %-1 (А)%-1(В), то х" действительно бу- будет характером. Характер х, рассмотренный в (iv), порождает цикли- циклическую подгруппу группы G порядка г\. Аналогичным образом можно доказать существование в группе G под- подгрупп порядков г2,..., Гъ,. Рассуждения, подобные тем, ко- которые были использованы при доказательстве сущест- существования точно h различных характеров группы G, где h — ее порядок, показывают, что G является прямым произведением этих циклических подгрупп порядков П, Г2,.--, f*. Следовательно, группы G и G изоморфны. Этот изоморфизм зависит от разложения G в произве- произведение циклических сомножителей (вообще говоря, это разложение не единственно) и от выбора образующих элементов этих сомножителей. § 3. Суммы характеров. Соотношения ортогонально- ортогональности. Пусть G — конечная мультипликативная абелева группа порядка h. Рассмотрим сумму А где А пробегает все элементы G, и сумму где х пробегает вее элементы группы характеров G.
148 Гл. X. Теорема Дирихле Если В — фиксированный элемент группы G и А про- пробегает все элементы G, то АВ также пробегает все эле- элементы группы G. Следовательно, A A откуда следует, что (%(В) — 1)S = O. Следовательно, или S = 0, или S=^=0 и %(В) = 1 для каждого элемента B^G. Во втором случае % = %\ есть главный характер и сумма S равна порядку h группы G. Таким образом, 5=2хИ)={*'еСЛИХ = Х1' B) если x^Xi Если мы умножим сумму Т на некоторый характер %' группы G, то аналогичным образом получим х/И)-г = 2хИ)х/04) = Следовательно, или Г = 0, или %'04) = 1 для каждого ха- характера %'^G. Во втором случае, согласно свойству (iv) из § 2, мы имеем А=Е, и тогда T = h. Таким образом, = ?> C) 0, если A=f=E. } Пусть m — положительное целое число. Мы знаем, что ф(т) приведенных классов вычетов по модулю m об- образуют мультипликативную абелеву группу порядка А = ф(т) (гл. II, § 1). Мы можем, следовательно, рас- рассмотреть характеры этой группы. Но определение харак- характера для приведенных классов вычетов по модулю m можно перенести на множество целых чисел следующим образом. Положим %(а)=%(А), если а^Л, где А — приведенный класс вычетов по модулю пг. Тог- Тогда, очевидно, %(й)—%(Ь), если a = b(mod m), и %{ab) = = %(а)%F)> если (a, m) = (b, m) — l. Поскольку % (А) Ф0 для каждого приведенного класса вычетов Ai то %(а) 0 если (а, т) = 1,
Суммы характеров 149 Это определение применимо только к целым чис- числам а, которые взаимно просты с т. Мы можем распрост- распространить его на все целые числа, положив %(а) = 0, если (а, т)>\. Следовательно, характер по модулю m есть арифме- арифметическая функция %, обладающая следующими свойст- свойствами: %(а)=%(Ь), если a = b (modm), x{ab) =%{а)%(Ь) для всех целых а и 6, %(а) = 0, если (а, пг) > 1, х(а)фО, если (а, т) = \. Имеется точно ц>(т) характеров по модулю т, где ф(т) —количество положительных целых чисел, не пре- превосходящих т и взаимно простых с т. Они образуют (мультипликативную) абелеву группу, изоморфную группе приведенных классов вычетов по mod т. Единич- Единичным элементом этой группы будет главный характер хи т. е. такой характер, что хЛа) = '» если (а, пг) = \. Далее, мы имеем следующие соотношения ортогональности: «(modm) 1 0, еСЛИ хЧ=Хъ ф(т), если n=l (modm), ^ О, если п ф 1 (modm). Примеры. (I) Пусть т = 4. Тогда имеются два приве- приведенных класса вычетов, а именно класс ?, состоящий из целых чисел, сравнимых с I(mod4), и класс Л, состоя- состоящий из целых чисел, сравнимых с 3(mod4). Классы А и Е образуют циклическую группу порядка 2. Существу- Существуют два характера xi и %2, где Xi(E) =xi(A) = 1, главный характер,
150 Гл. X. Теорема Дирихле По определению характера, перенесенному на все це- целые числа, мы имеем 0, если п четное, 1, если п нечетное, и @, если п четное, 1, если п=\ (mod4), —1, если я = 3 (mod 4). Далее, (II) Пусть m=5. Тогда приведенные классы вычетов суть ?, Л, Л2, Л3, где Л — класс всех целых чисел, срав- сравнимых с 2 (mod 5). Класс Л2 представляет собой класс целых чисел, сравнимых с 4 (mod 5), и Л3 — класс целых чисел, сравнимых с 3(mod 5). Класс Е состоит из целых чисел, сравнимых с I(mod5). Четыре характера опре- определяются теперь следующим образом: § 4. Ряды Дирихле. Теорема Ландау. Рядом Дирих- сю ле называется ряд вида У] CLnn~s, где 5 — комплексное число и коэффициенты ап •— также комплексные числа. Рядом Дирихле называется также ряд более общего вида 2 Ь или 2 °- п1 п1 Ь 2 где 0<^i<X2<... и Яп-^оо при
§4- Ряды Дирихле 151 Многие ряды Дирихле, встречающиеся в теории чи- чисел, имеют вид ^anft-s, и мы рассмотрим некоторые эле- элементарные свойства таких рядов. Обычно мы будем писать s = o-\-it} где out действи- действительны и i2 = — 1. оо Теорема 1. Если ряд ^an/ns сходится при s = sOi п=\ то он равномерно сходится в области |arg(s—s0) | ^я/2—6<я/2. Доказательство. Ввиду того что tl=l и сходимость ряда ^ ann~s при s = s0 эквивалентна схо- схоп=\ димости ряда ^ ЬПу где hn = ann~s\ мы можем предпо- ложить, не уменьшая общности, что 50 = 0. оо Пусть ряд 2 ап сходится. Тогда lim rn = 0, где гп = оо = 2 av • Пусть, далее, М и N — положительные це- v=rz-|-l лые числа и M<iN. Тогда N N N S^n_ = у гп_х — гп у / гп _ jj_ ns Lj ns Zj l (л 4. iy* ns n=M n=M n=Mx , rM-\ ^ Ms (N + \)s • При о>0 мы имеем л+1 /г-f-l (/I + ^ Ji/J L o\n° (n +
152 Гл. X. Теорема Дирихле Для заданного е>0 мы имеем |гп|<е при где п0 не зависит от 5. Следовательно, при М N 2j ns ln=M Если а>0 и 1 ? Л N v 1 \s\ G a n ( >/ n s 1 M° го(е (N- 1, МЫ 8|S| a 1 \ , 8 bi)aj ' м получаем 1 8 M° M° г ° (N+lf оценку / 2e|s| a U ln=M Чтобы доказать равномерную сходимость, заметим, что \s\ ^ I ^ 1 1 a cos [arg s| ^ cos (я/2 — 0) sin G ' т. е. для каждого 5, удовлетворяющего условию | arg s\ ^ /2/, мы имеем N J 2е (cosec 9), Л^ > М > /го(е); теорема 1 доказана. Отсюда следует, что если ряд ]Г] -^- сходится при П п=1 П п1 ^о, то он будет сходиться при всех s = o + it с о>о0. Таким образом, справедлива оо Теорема 2. Если ряд ^ ~т сходится при s = 50, то оя /г=1 П сходится в полуплоскости а>(То ^ равномерно сходится в каждом компактном множестве, содержащемся в этой полуплоскости. Из равномерной сходимости следует также Теорема 3. Пусть ряд S ~^" сходится при s = s0 и п=1П оо оо 2"^"=/(so)- Пусть, далее, f(s)= S ~т в полуплоскос- 1 /7 1
§4- Ряды Дирихле 153 ти 0>0о- Тогда f(s)-+f(s0) при s-+s0 вдоль любого пу- пути, лежащего в области |arg(s—so)| ^я/2—8<я/2. Теорема 2 показывает, что область сходимости ряда Дирихле представляет собой полуплоскость. Действи- Действительно, если точки действительной оси разделить на два класса U и L, такие, что U= \а 2j —7 сходится , L= \a 2js расходится , то каждое число класса U будет больше любого числа класса L и такое разбиение на классы определяет дей- действительное число 0о, такое, что ряд сходится при 0>0О и расходится при 0<0О. В случае 0=0О вопрос о сходи- сходимости остается открытым. Если класс U пуст, то поло- положим 0О= +оо, если же L пуст, то положим 0О= —оо. Число 0О называется абсциссой сходимости, прямая 0 = 00 — ПрЯМОй СХОдиМОСТи, а ПОЛУПЛОСКОСТЬ 0>0О — полуплоскостью сходимости ряда Дирихле J] an/ns. п=1 со Ряд J] n\/ns всюду расходится @О=+оо), в то время /г—1 со как ряд XI l/(n\ns) всюду сходится (<То = —оо). /г=1 Теорема 1 вместе с теоремой Вейерштрасса о равно- равномерно сходящихся последовательностях аналитических функций дает нам следующий результат: Теорема 4. Ряд Дирихле ]Г] -^ в полуплоскости его п=\ П сходимости представляет собой регулярную аналитиче- аналитическую функцию от s, последовательные производные ко- которой получаются почленным дифференцированием это- этого ряда. В этих теоремах ничего не говорится о сходимости или регулярности суммы ряда на прямой сходимости.
154 Гл. X. Теорема Дирихле В отличие от степенных рядов, которые всегда имеют на границе круга сходимости особенность, ряды Дирихле не обязательно имеют особенность на прямой сходимости. Точно так же из сходимости или расходимости ряда Ди- Дирихле в фиксированной точке на прямой сходимости мы не можем делать выводы о регулярности или нере- нерегулярности суммы этого ряда в указанной точке. Мы вернемся к этому вопросу несколько позже. оо Абсолютная сходимость. Ряд ^ an/ns сходится абсо- оо лютно, если сходится ряд ^] |#п|/яа. Абсциссой абсолют- л=1 оо ной сходимости а ряда J] anlns называется абсцисса сходимости ряда ^] \an\/ns. 1 Очевидно, Ъ^во, так как абсолютная сходимость влечет за собой сходимость ряда. Если а>ао, то сущест- существует полоса в комплексной s-плоскости, в которой ряд сходится, но не абсолютно. Эта полоса Оо<Со<Со назы- называется полосой условной сходимости. Рассмотрим для примера ряд сходящийся при действительных s>0, поскольку это зна- знакопеременный ряд с убывающими членами. Он, очевид- очевидно, расходится при действительных 5<0 и, следователь- следовательно, ао=О. Далее, этот ряд абсолютно сходится при а>1 и абсолютно расходится при а<1. Следовательно, а=1, и полоса условной сходимости имеет ширину 1. Интересно отметить, что при а>0 имеет место равен- равенство
§4- Ряды Дирихле 155 где ?(s) есть дзета-функция Римана. В самом деле, ряд в левой части F) абсолютно сходится при а>1, и после соответствующей перестановки его членов мы получаем при а>1 Но ряд Yi (—l)n~V^s сходится при а>0 и функция g(s) A—21-s) регулярна при а>0, так как простой по- полюс ?(s) при 5=1 уничтожится нулем функции 1—21-3. Следовательно, по аналитическому продолжению мы по- получаем, что равенство F) остается справедливым при а>0. Мы показали, что полоса условной сходимости ряда F) имеет ширину 1. Можно доказать, что ширина поло- полосы условной сходимости любого ряда Дирихле Yiun/ns не может быть больше 1, так что если ряд Дирихле схо- сходится для данного s0, то он будет абсолютно сходиться при всех 5, у которых действительная часть будет боль- больше действительной части s0 на величину 1+е при любом 8>0. оо Теорема 5. Для любого ряда Дирихле ^]an/ns мы имеем о—сго^ 1. Доказательство. Если ряд J] an/ns сходится, то оо lim|an|/tta =0 и, следовательно, ряд Yi\an\/n1+°+e cxo- дится для любого 8>0. Как показывают следующие примеры, эта теорема не выполняется для рядов Дирихле более общего вида 2 #nA7s, где (кп) не является множеством положитель-
156 Гл. X. Теорема Дирихле ных целых чисел. В самом деле, ряд сходится при а>0, но нигде не сходится абсолютно; ряд у (-1)" сходится при всех 5, но нигде не сходится абсолютно. Вернемся теперь к вопросу о регулярности суммы ря- ряда Дирихле Yj ~y на прямой сходимости. В случае когда коэффициенты (ап) неотрицательны, имеет место Теорема 6 (Ландау). Если ап^0 для всех п~^\ и сто конечно, то точка пересечения действительной оси с пря- прямой сходимости является особой точкой суммы f(s) ря- ряда Дирихле S —j. Доказательство. Так как ап^0, то o=gq. Без огра- ограничения общности мы можем считать, что сго=О. Нам нужно показать, что точка 5 = 0 является особой точкой функции /. Если бы f была регулярна при 5 = 0, то ряд Тейлора функции / в точке 5=1 имел бы радиус сходи- сходимости р>1. Следовательно, должно существовать дейст- действительное 5<с0, для которого ряд v=0 сходится. Но при а>0 оо » . v VI —S log П /1=1 и по теореме 4 п
§4- Ряды Дирихле 157 так что n=\ Ряд Тейлора функции f в точке s = l имеет поэтому вид ап(-1оёп? _ у A -s)v у an(logn)v v! n v\ Zj v=0 n=\ v=0 n=\ Поскольку все члены этого двойного ряда неотрицатель- неотрицательны при 5<сО, можно изменить порядок суммирования. Тогда мы получим, что ряд ап у (\-s)v(logn)v п=\ v=0 сходится для некоторого 5<;0. Однако (\—S)V (\Qgn)V _ „(l-s)logw v=0 S(\S) (\Qgn) _ „( Следовательно, ряд ^ann~s сходится для некоторого л=1 5<0, что невозможно, так как ао^О. Таким образом, точка s = 0 должна быть особой точкой функции f(s). Умножение рядов Дирихле. Формальным произведе- произведением двух рядов Дирихле ^cth/ks и ^ bm/ms называется оо ряд Yicn/ns, где сп = J]akbm• Если оба эти ряда сходятся оо абсолютно для некоторого данного 5, то ряд YiCn/ns так- же абсолютно сходится и называется в этом случае про- произведением данных рядов. Пусть а>(То и k=l m=l
158 Гл. X. Теорема Дирихле Тогда по теореме 5 функция h(s), где h(s)=f(s)-g(s), представляется в полуплоскости а>ао+1 произведени- произведением рядов Дирихле функций f(s) и g(s). Представление функции рядом Дирихле единственно, как показывает следующая Теорема 7. Если ряды 2 -т п 2 ~~г сходятся в об- полуплоскости и их суммы совпадают в непустом от- открытом множестве, содержащемся в этой полуплоско- полуплоскости^ то ап = Ьп при всех п^\. Доказательство. Рассмотрим ряд Дирихле S tlS Он сходится в некоторой полуплоскости а>ао, где опре- определяет регулярную аналитическую функцию. Эта функ- функция тождественно равна нулю в некотором непустом от- открытом множестве, содержащемся в этой полуплоскости, и, следовательно, тождественно равна нулю во всей этой полуплоскости а>(То. Пусть М будет первым значением индекса п, при ко- котором апфЪп, и пусть сп = ап—Ьп. Тогда при а>ао мы имеем у ?п = у is. n=\ n= ИЛИ fM_ = _ Следовательно, при а>ао+1 lc i.< V \с 1.Ш л=Л1+1 х ' Пусть теперь а-^оо. Тогда из равномерной сходимости последнего ряда при а>ао+2 следует, что см = 0. Но это
§5. Теорема Дирихле 159 противоречит определению М. Следовательно, сп = 0 для всех \ § 5. Теорема Дирихле. Применим теперь результа- результаты, полученные нами в § 3 о характерах и в § 4 о рядах Дирихле, к рядам вида где % — характер по модулю т. Имеется у(т) таких рядов, где ср — функция Эйлера. Так как \%(п) | ^1, ряд G) сходится при а>1, что вид- видно из сравнения этого ряда с рядом ^\lns. Обозначим его сумму через L(s, %). Для различных характеров % мы получаем разные функции L(s, %). Они называются L-функциями Дирихле. При изучении свойств этих функ- функций удобно различать случаи, когда % — главный харак- характер %i и когда %ф%\. (i) Если %ф%и то ряд G) сходится в полуплоскости а>0. Покажем сначала, что частичные суммы ^]%(п) ог- п<х раничены. Разобьем целые числа от 1 до [х] на классы вычетов по mod m и запишем [x]=mq + ry O^r^m—l. Тогда [х] т 2т mq mq+r 2x(«) = S]x(n) = B+ 2 +...+ 1 )%(п)+ 2 п<х п=1 * 1 m-J-1 m(q—1) + 1^ mq-\-l В силу соотношения ортогональности D) мы имеем mq-\-r п<х mq-\-l откуда ЕхИ < 2 1х(лIО<т. Так как пг° при а>0 монотонно убывает и стремится к йулю при м->-оо, то ряд Yi%(n)/nS сходится Для дейсТ-
160 Гл. X. Теорема Дирихле вительных 5 = а>0, а следовательно, и для всех 5 в по- полуплоскости а>0, если %Ф%\. Если же а<0, то этот ряд, очевидно, расходится. Его абсцисса сходимости ао=О, а абсцисса абсолютной сходимости а = 1. По теореме 4 функция L(s, %)> %Ф%1, является регулярной аналити- аналитической функцией от 5 при а>0. (ii) Если % = %ь мы воспользуемся снова тождеством Эйлера t»-2 7-" где /? пробегает все простые числа. Поскольку каждый характер % является вполне мультипликативной арифме- арифметической функцией, то по теореме 5 гл. VII мы имеем для всех % тождество Отсюда следует, что L(s9 %)ФО при а>1. Если xi — главный характер по mod m, то П,если(а,т)=1, I 0, если (а,т) > 1. Используя (8), получаем Цел) = П (J -р-'Г1 =П 0 -р-^)-1 П ( Р|т р р\т ИЛИ n р\т Мы видели, что ?(s) —мероморфная функция в полу- полуплоскости а>0, имеющая в качестве единственной осо- особенности простой полюс при 5=1 с вычетом 1. Следова- Следовательно, L(s, Xi) является регулярной функцией при а>0, за исключением точки 5=1, где она имеет простой по- полюс с вычетом ДО— Р~г) = ^Ж^ tCM* гл' П' р\т
§5. Теорема Дирихле 161 Для доказательства теоремы Дирихле нам потребует- потребуется Лемма. Если %ф%и то L(l,x) =#=0. Доказательство. Достаточно показать, что произве- произведение где х пробегает все характеры по mod/?, не является регулярной функцией при а>0. Действительно, если ?(!>%) =0 по меньшей мере для одного характера %ф%\, то простой полюс функции L(s, xi) при s = l в произве- произведении P(s) уничтожится нулем функции L(s, у) при s= 1 и P(s) в таком случае будет регулярной функцией при а>0. Для а>1 мы имеем \%(p)p~s\^€p~°<l и можем оп- определить Тогда функция logL(s, %) однозначно определяется в по- полуплоскости а> 1 равенством где р пробегает все простые числа, a k — все положи- положительные целые числа. Этот двойной ряд абсолютно схо- сходится при а>1. Далее, мы имеем Просуммируем теперь log L(s, %) по всем характерам %(mod m). Тогда мы получим 7 X X РЛ Так как имеется только конечное число характеров %, мы можем изменить порядок суммирования и получить
162 Гл. X. Теорема Дирихле Поскольку ф(^), если а= 1 (mod m), 0, если а ф 1 (mod m), если n=pk= 1 (modm), в противном случае, мы имеем Если мы положим то где коэффициенты (ап) неотрицательны. Мы знаем, что этот ряд сходится при а>1. Для того чтобы найти его абсциссу сходимости, рассмотрим простые р, такие, что /J'T т. По теореме Эйлера (теорема 2 гл. II) мы имеем ph=l(modm), где Л=ф(т). Если мы рассмотрим ряд A1) для действительных s и возьмем только члены с k=h, то получим Q(s)>2j Zhi==ljzn~ р\т р\т р\т Поскольку ряд ^]— расходится и сумма J] — конечна, р\т Р отсюда следует, что ряд A1) расходится при s=l/h. Следовательно, если а — абсцисса сходимости ряда Ди- Дирихле Q(s), то a^l/ft. Далее, мы имеем P(S) = e^=l+Q(S) + ^+... . A2) Произведение двух сходящихся рядов Дирихле с неотри- неотрицательными коэффициентами будет снова рядом Дирих- Дирихле с неотрицательными коэффициентами, который схо- сходится в пересечении двух полуплоскостей сходимости ис- исходных рядов. Следовательно, одновременно с Q(s) все
§ 5. Теорема Дирихле 163 степени Qn(s) сходятся абсолютно, так что ряд A2) для P(s) может быть записан в виде ряда Дирихле с неот- неотрицательными коэффициентами. Таким образом, если ряд Дирихле функции Q(s) схо- сходится, то ряд Дирихле функции P(s) также сходится. Об- Обратно, поскольку эти ряды имеют неотрицательные ко- коэффициенты, из сходимости ряда Дирихле функции P(s) для некоторого действительного s следует сходимость ряда Дирихле функции Q(s) для того же s. Следовательно, ряд Дирихле функции P(s) одно- однозначно определен и имеет ту же самую абсциссу сходи- сходимости ао=а, что и ряд Дирихле функции Q(s). По тео- теореме 6 точка s = a является особой точкой для P(s), и мы знаем, что а^1/Л>0. Значит, функция P(s) не бу- будет регулярной во всей полуплоскости а>0. Лемма до- доказана. Теперь мы можем доказать основную теорему этой главы: Теорема 8 (Дирихле). Если т — положительное це- целое число и (а, т) = 1, то существует бесконечно много простых p = a(modm). Доказательство. Достаточно доказать, что ряд 5] 1/р, где р пробегает все простые числа, сравнимые с a(modm), расходится. Для доказательства этого утвер- утверждения мы воспользуемся функцией L(s, %). При а>1 мы имеем, согласно A0), оо I \ V V 5С(Р ) « 1 ИХ) р R==i Выделим члены с k=\. Тогда мы получим log L (s, зс) = Уд (Р) P~s + R(s> ЭС). A3) где ряд р - V V иЛ kpks сходится при а>1/2.
164 Гл. X. Теорема Дирихле Поскольку (а, т) = 1, найдется целое число 6, такое, что ab = l(modm). Умножим обе части равенства A3) на %(Ь) и просуммируем его по всем характерам x(modm). Тогда мы получим при а>1 2 Х(Ь) log l (s, х) = S S хФр) p~s + 2 %(Ь) R (s, %). Так как функция R(s,%) регулярна при а>1/2, функция R*(s) — "Ei%(b)R(s,%) также будет регулярна при а>1/2. Далее, V (h — №' если bp= I (mod/и), \ Х ~~ {0, если Ьр ф 1 (mod m). Если ab^l(modm), то сравнение bpE=l (mod m) экви- эквивалентно сравнению p = a(modm). Поэтому + /?*(*)• A4) Пусть теперь 5-^1+0 вдоль действительной оси. Тогда левая часть A4) стремится к бесконечности. Действи- Действительно, L(s, %i)-> оо при 5-^1+0; функция L(s, %), Хт^Хь регулярна при а>0; L(l, x)#0 при x^Xi по доказанной выше лемме и logL(s, %), %ф%\, определен- определенный по формуле A0), имеет конечный предел при s-> —^1 +0, поскольку \ogL(stx) =-\^^du + logL(c,x) при s=o> I, c>o, если мы заметим, что L(u, %)ф0 при ^ %% a Z/(s, x) регулярна при а>0, %ф%\. Далее, функция R*(s) регулярна при а>1/2. Следовательно, ^ p~s-^oo при s-^ p=a(mod) m Значит, ряд Yi l/P расходится.
ГЛАВА XI АСИМПТОТИЧЕСКИЙ ЗАКОН РАСПРЕДЕЛЕНИЯ ПРОСТЫХ ЧИСЕЛ § 1. Необращение в нуль функции ?>(l-\-it). Мы пока- показали в предыдущей главе, что L-функции Дирихле об- обладают тем свойством, что L(l, %)фО при %ф%\, и ис- использовали это для доказательства бесконечности мно- множества простых в каждой арифметической прогрессии вида a+mk, где т>0, (а, т) = 1 и k = 1, 2, ... . Покажем теперь, что дзета-функция Римана облада- обладает тем свойством, что ?,A-]-И)Ф0 при t^O, и использу- используем это свойство для доказательства асимптотического закона распределения простых чисел. Асимптотический закон распределения простых чи- чисел обычно записывается в виде Я(*)~-JL-. A) log л: где п(х) обозначает количество простых чисел, не пре- превосходящих х, а символ ~ означает, что n(x)/(x/logx)-+- ->-1 при %->-оо. В гл. VII мы показали, что сотношение A) эквива- эквивалентно соотношению Нга^М = 1, B) где а|) — функция Чебышева. Мы будем доказывать асимптотический закон распределения простых чисел именно в этой форме. Нам потребуется соотношение которое мы вывели в § 4 гл. VII для действительных s>l в качестве следствия из формулы суммирования Абеля. В силу аналитического продолжения формула C) будет справедлива для всех комплексных s с дейст-
166 Гл. XI. Асимптотический закон вительной частью а>1. (Мы пишем, как обычно, s = = o-\-it, где a, t действительные и i2 = — 1.) Положим в равенстве C) и=ех. Тогда мы получим оо Ш )e-xsdx, <т>1, D) откуда мы выведем в дальнейшем, что г|)(ех)~ех, или г|)(л:) ~х при л:->-оо. Мы уже видели, что ?>(s) является аналитической функцией в полуплоскости а>0, за исключением точки s = l, где она имеет простой полюс с вычетом 1, и что ?(s)=t^0 при а>1. Докажем теперь, что t,(s)=^O на пря- прямой а = 1. Теорема (Адамар, Валле-Пуссен). Если t=^0, to Доказательство. При сг>1 и, логарифмируя это равенство, мы получаем, как и в гл. X, mpms m,p где m пробегает все положительные целые числа, ар — все простые числа. Следовательно, Далее, ряд J]—ш = Л % является рядом Дирихле с т,ртР п=2П коэффициентами —, если п = рт, О, если n=j=pm. Поэтому
§2. Теорема Винера-Икеары 167 где сп^0, и так как то п=2 Поскольку с„>0 и 3 + 4cos9 + cos26 = 2(l +coseJ>0 F) для всех действительных Э, то it)\=3 log|?(a)| + 41og|S(a+ ft)| + = S ^fC + 4cos(/logn) + cosB/logA2))>0. n=2 П Значит, так что C^O 4 ! G) a— 1 Покажем теперь, что предположение ?A+#)=0 при /zz=/0^0 приводит к противоречию. Действительно, если мы в G) положим t=t0, то при а-М+0 правая часть будет стремиться к бесконечности, а левая часть будет стремиться к пределу \tf(l+it0) |4|?A +2it0) |. Но этот предел конечен, поскольку ?(s)—аналитическая функ- функция при а>0, 5=^=1. Следовательно, ?>A + Но)ФО и тео- теорема доказана. § 2. Теорема Винера— Икеары. Мы выведем асимпто- асимптотический закон распределения простых чисел из следую- следующей теоремы: Теорема 2 (Винер — Икеара). Пусть А(х) —неотри- —неотрицательная неубывающая функция от х, определенная
168 Гл. XI. Асимптотический закон при 0^л:<оо, и пусть интеграл оо J A(x)e~xsdxt s = g + it, о сходится при а>1 к функции f(s). Пусть, далее, f(s) является аналитической функцией при а^1, за исклю- исключением точки s—1, где она имеет простой полюс с вы- вычетом 1. Тогда \\ше~хА(х) =1. Доказательство. Разобьем доказательство теоремы на две части. Положив , (8) мы докажем сначала, что для любого Затем мы выведем из (9), что ИтВ(х) = 1. A0) Первая часть. Так как при а>1 оо оо f(s) = f A (x) e~xs dx, —I— = (* e~{s~1)x dx, J s — 1 J о о TO oo f(s) — = ^(B(x) — l)e~is-1)xdx (<r> 1). s о Положим Тогда, в силу предположений о функции f(s), g(s) будет аналитической при
§2. Теорема Винера-Икеары 169 Для Я>0 мы имеем 9.7. 1 2Х оо ¦J (i-^)^(j(sW-i)e-<e+")A:^)^. (И) Покажем, что в A1) можно изменить порядок интегри- интегрирования. Так как А(х) является неубывающей и неот- неотрицательной функцией, то при действительных s и f(s) = ]А (u) e-usdu > A(x) ]e~usdu = Wlfl, т. е. А(х) ^sf(s)exs. Далее, поскольку f(s) —аналитиче- —аналитическая функция при а>1, то A(x)=O(exs) для каждого s>l, а тогда A(x)=o(e:x;s) для каждого s>l. Следова- Следовательно, В(х)е-6х=А(х)е-A+6)х — оA) для каждого 5>0, откуда следует, что интеграл ]{B{x)-\)e~{E+it)xdx о сходится равномерно в интервале —2rk^t^2rk. Значит, в A1) можно поменять порядок интегрирования, и мы получим -2Х Функция g"(s) является аналитической при а^1, и поэтому ge(t)-^ g(l-]-it) равномерно в интервале
170 Гл. XI. Асимптотический закон при е->0. Далее, m 7 0 J 8-0 J Чу — хJ J Цу — хJ и, следовательно, предел е-о существует. Кроме того, поскольку подинтегральная функция неотрицательна и монотонно возрастает при 8->-0, мы имеем 8-о (/ ) Таким образом, мы получаем из A2) sin2X(y — х) p Sin~A(*/ — Пусть теперь y->-oo. Тогда по лемме Римана—Лебега !) левая часть стремится к нулю, в то время как второй член правой части дает г» sin Х(у — х) 1 г г» sin v 1 у-*оо J Х(у — х) г/~*сю J V2 О -оо Следовательно, lim Г By ^-) S1" v dv = n- у-*оо J \ A J V* —оо тем самым соотношение (9) доказано. !) См. Ахиезер Н. И., Лекции по теории аппроксимации, «Наука», М., 1965, п. 60. — Прим. перев.
§2. Теорема Винера-Икеары 171 Вторая часть. Докажем равенство A0) в два этапа, а именно IImfi(*xi A3) A4) Для данных положительных чисел а и X пусть #>># Д. То- Тогда, согласно (9), мы имеем Г-— С г»/ v\sin2Vi ^ так как подинтегральная функция неотрицательна. Да- Далее, функция А(и)=В{и)еи является неубывающей. Значит, при —. а откуда следует, что Следовательно, ИЛИ 2а а . Далее, для фиксированных а и К мы имеем Ш в(у — -) = Ш В(у).
172 Гл. XI. Асимптотический закон Поэтому 2а для всех а>0, А,>0. Пусть теперь а->оо и А,->оо таким образом, что аД->0. Тогда lim B(y) f или я lim В (у) < я. у-+оо Итак, неравенство A3) доказано. Используем теперь неравенство A3) для того, чтобы доказать A4). Из A3) следует, что |?(л;)|^с при под- подходящей константе с, так что для фиксированных поло- положительных а и X и для достаточно больших у мы имеем лу С о / lAsin2^ Как и раньше, при —a^.v^a мы имеем так что ? / iA sin2 J д(у-х)- —а Из (9), A5) и A6) мы получаем
§ 3. Асимптотический закон 173 т. е. -а оо 2а Пусть теперь а->оо и А,->оо таким образом, что аД->0. Тогда я <jtlim B(y)t и тем самым A4), а следовательно, и теорема 2 дока- доказаны. § 3. Асимптотический закон распределения простых чисел. Если г|з — функция Чебышева (см. гл. VII), по- положим А(х) =ty(ex) и заметим, что функция г|з неубы- неубывающая и \р(ех)^О. Соотношение D) позволяет прове- проверить другие предположения теоремы 2, ибо функция ?(s) является аналитической при а>0, за исключением точ- точки s=l, где она имеет простой полюс, и, согласно теоре- теореме 1, t,(s) не обращается в нуль в полуплоскости а^1. Следовательно, по теореме 2 ty(ex) ~ex, или ty(x) ~x при %->оо, и тем самым асимптотический закон распределе- распределения простых чисел доказан. Таким образом, асимптотический закон распределе- распределения простых чисел следует из теоремы Винера — Икеа- ры, если мы предположим, что ?A+#) фО для гфО. Об- Обратно, если мы предположим, что справедлив асимпто- асимптотический закон распределения простых чисел, то легко вывести, что 1A + И)Ф0 при гфЪ. Действительно, пусть Тогда O(s) регулярна при а>0, за исключением про- простых полюсов, которые она имеет в точках, являющих-
174 Гл. XI. Асимптотический закон ся нулями ?>(s). Асимптотический закон распределения простых чисел означает, что ур(х) =х-{-о(х) при #->оо. Следовательно, для любого данного е>0 существует число хо(г), такое, что при х^хо(г) >1 \ур(х)—х\<ех. Тогда при а>1 мы имеем и так как то где К=К(х0) =/С(е). Таким образом, (а—1 Пусть теперь а-И+0. Тогда для любого фиксированно- фиксированного * lim(<r—1)Ф(<т+#)=0. 1+0 Если \-\-it при /=7^0 будет нулем функции ?(s), то пре- предел выражения (а—\)Ф{о-\-И) при а->1+0 будет равен вычету функции O(s) в простом полюсе s=\-\-it и, сле- следовательно, будет отличен от нуля. Но это противоречит A7) и, следовательно, Ц1+й)=^=0 при t*?0. Таким образом, утверждение, что ?A+#) фО при гфО, «эквивалентно» асимптотическому закону распре- распределения простых чисел. Другим эквивалентным утверж- утверждением является утверждение, что /?n~/ilog/i, где рп оз- означает п-е простое число, если простые числа располо- расположены в естественном порядке.
§3. Асимптотический закон 175 тт » П(х) log X 1 Действительно, если ———-—->1 при #->оо, то log я (х) + log log х — log х -> О и, следовательно, 1, log л: Тогда откуда следует, что /7n^-nlogn, если взять х=рп. Обратно, если х определить неравенствами /^ <Рп+\ и если pn—n\ogn, то pn+i^ (n+l)log(n+l) ~n\ogn, так что ^^nlogn, или x~ylogy, где = я(л:) =л, т. е. log ^ ^ log r/ и, следовательно,
СПИСОК ЛИТЕРАТУРЫ 1. Dickson L. E., History of the theory of numbers, Carnegie In- Institution, Washington, I A919), II A920), HI A923), reprinted Chel- Chelsea, New York, 1952. 2. Hardy G. H. and Wright E. M., An introduction to the theory of numbers, Oxford University Press, 1938, 2nd edition, 1945. 3. Ingham A. E., The distribution of prime numbers, Cambridge Uni- University Press, 1932, reprinted Stechert-Hafner, New York, 1964. (Рус- (Русский перевод: Ингам А. Е., Распределение простых чисел, ОНТИ, 1936.) 4. Landau E., Handbuch der Lehre von der Verteilung der Primzahlen, 2 volumes, Teubner, Leipzig, 1909, reprinted Chelsea, New York, 1953. 5. Uspensky J. V. and Heaslet M. A., Elementary number theory, McGraw-Hill, New York, 1939. 6. Виноградов И. М., Основы теории чисел, «Наука», М., 1965,
ПРИМЕЧАНИЯ Примечания к главе I В качестве основных источников см. [2], гл. 1 —3 и [5], гл. 1—6. § 2. Теорема 2 была установлена Гауссом (Gauss С. F., Disquisi- tiones Arithmeticae, 1801, § 16; см. также Gauss С. F., Werke, I, 1863, S. 15). Относительно первого доказательства теоремы 2 можно сослаться на работу Цермело (Zermelo E., Gottinger Nachrichten (new series), 1 A934), 43—44). Согласно Цермело, его доказательство датируется 1912 г. См. также Hasse Н., /. fur Math., 159 A928), 3—6, и Linde- mann F. A., Quarterly J. Math. (Oxford), 4 A933), 319—320. § 3. Относительно второго доказательства теоремы 2 см. Hecke E., Vorlesungen uber die Theorie der algebraischen Zahlen, 1923, ch. 1. To, что мы называем модулем в множестве целых чисел, есть просто подгруппа аддитивной группы целых чисел. Относительно теоремы 6 см. Евклид, Начала, ГИТТЛ, М.—Л., 1948—1950, книга 7, предл. 30. § 5. Имя Фарея связано с последовательностями Фарея благо- благодаря Коши, который обратил внимание на предложенную в 1816 г. Фареем (без доказательства) теорему 7 и опубликовал свое доказа- доказательство. См. Cauchy A., Oeuvres, 2е serie, Paris, t. 6, p. 146. Теоре- Теоремы 7 и 9, по-видимому, впервые установил и доказал в 1802 г. Ха- рош (Haros С); см. [1], I, стр. 156. Представляет интерес следующее замечание К- Л. Зигеля к доказательству теоремы 7: «Пусть kl—hm = = 1, k^>0, т^>0. Однородная линейная подстановка % = ka—hb, \i = =—ma-\-lb целых переменных а и b имеет обратную a = Xl-\-h\i, b = mK+k\i. Следовательно, условия h/k^a/b^l/m, 6>0, (a, ft) = l, удовлетворяются тогда и только тогда, когда Х^О, pi^O, ^+M<>0, (к, мО = 1, и тогда b^m+k точно в трех случаях А,, |х = 0,1; 1,1; 1,0. В этом рассуждении не используется понятие последовательности Фарея Fn». § 6. Относительно теоремы 12 см. Евклид, Начала, ГИТТЛ, 1948—1950, книга 9, предл. 20. Доказательство Пойа теоремы 13 см. в книге Полна Г. и Сеге Г., Задачи и теоремы из анализа, ГИТТЛ, М., 1956, II, стр. 149, 366. Замечание о том, чтобы положить fo = 3, принадлежит К. Л. Зигелю. Доказательство, предложенное Беннетом, результата Эйлера о том, что /5 делится на 641, дано в книге [2], стр. 15. Другое доказательство дано Крайчиком (Kpaitchik, Theorie des nombres, Paris, 1926, II, p. 221).
178 Примечания Примечания к главе II В качестве основных источников см. [2], гл. 5, [5], гл. 6, 7 и [6], гл. 1,2. § 1. Теория сравнений была развита Гауссом в его Disquisitio- nes Arithmeticae, loc. cit., хотя Ферма и Эйлеру, возможно, были из- известны некоторые основные результаты. § 2. Относительно формулировки теоремы 3, данной Ферма в 1640 г., см. Fermat P., Oeuvres, Paris, II, 209. Эйлер доказал теорему 2 в 1760 г.; см. Euler L., Opera Omnia, Leipzig-Berlin-Zurich A), II, 531. См. также книгу Диксона [1], I, гл. 3. § 3. Относительно теоремы 7 см. Lagrange J. L., Oeuvres, Paris, 1868, II, p. 667—669. Примечания к главе III § 2. Относительно доказательств теорем 5 и 7 см., например, Rademacher H., Lectures on elementary number theory, Blaisdell, New York, 1964, p. 33—35. § 3. Относительно теоремы 6 см. Lucas, Theorie des nombres, 1891, I, p. 353—354. § 4. Теорема 9 принадлежит Гурвицу (Hurwitz A., Math. Anna- len, 39 A891), 279—284). Приведенное здесь доказательство дано А. Хинчиным (Math. Annalen, 111 A935), 631—537). На это доказа- доказательство внимание автора обратил Рагхаван Нарасимхан. В кни- книге автора Einfiihrung in die Analytische Zahlentheorie, Springer Lectu- Lecture Notes, 29 A966), ch. 3, был дан набросок другого доказательства, которое восходит к Форду (Ford L. R., American Math. Monthly, 45 A938), 586—601). Примечания к главе IV В качестве основных источников см. [2], [5] и [6]. § 1. Относительно символа Лежандра см. Legendre A. M., Essai sur la theorie des nombres, 1798, 2nd edition, 1808, § 135. Мы не рассматривали случай /? = 2, поскольку все целые числа являются квадратичными вычетами по модулю 2. § 2. Первое опубликованное доказательство A773 г.) теоремы Вильсона было дано Лагранжем (Lagrange J. L., Oeuvres, Paris, III, 425). Эта теорема впервые была установлена Варингом (Waring E., Meditationes algebraicae, 1770, p. 218) и была приписана Вильсону. Харди и Райт говорят, что «есть основания считать, что она была известна задолго до Лейбница».
Примечания 179 § 3. Теоремы 5, 6, 7 можно найти в книге Харди и Райта [2], стр. 70, 297. Предложенное здесь доказательство теоремы 7 дано Эр- митом (Hermite С, Journal de Math. A), 13 A848), 15; Oeuvres, Pa- Paris, I, 264). § 4. Варинг установил без доказательства, что каждое положи- положительное целое число можно представить в виде суммы четырех квад- квадратов (Waring E., Meditationes algebraicae, 1770, p. 204—205); Ла- гранж доказал это утверждение в том же году; см. его Oeuvres, III, p. 189. См. также [1], II, гл. 8. Примечания к главе V § 1. Теорема 1 была установлена Эйлером и частично доказана Лежандром. Полное доказательство было дано Гауссом в 1795 г. См. Bachmann P., Niedere Zahlentheorie, 1902, I, ch. 6, где приведено несколько доказательств. § 2—3. Идея доказательства теоремы 1 с помощью формулы вза- взаимности для сумм Гаусса восходит к Кронекеру (Kronecker L., Мо- natsber. Kgl. Preuss. Akad. Wlss. Berlin A880), 686—698; 854—860; /. fur die reine und angewandte Math., 105 A889), 267—268; Werke A929), IV, 278—300). Однако, как указал К. Л. Зигель, в книге Линделёфа (Lindelof E., Calcul des Residus, p. 68) имеется ссылка на работу Шаара (Schaar) 1848 г. о формуле взаимности для сумм Гаусса. Эта идея была распространена на числовые алгебраические поля Гекке (Hecke E., Gottinger Nachrichten A919), 265—278; Werke, 235—248) и Зигелем (Siegel С. L., Gottinger Nachrichten (I960), 1—16; Ges. Abhandlungen, 1966, III, 334—349). Приведенное здесь доказа- доказательство по существу принадлежит Зигелю. Интеграл, использован- использованный в доказательстве теоремы 2, играет важную роль в теории дзета- функции Римана- См. Siegel К. L., Quellen und Studien zur Geschihte der Math., 2 A932), 45—80; Gesammelte Abhandlungen A966), I, 275. Относительно оценок обычных сумм Гаусса с помощью контур- контурного интегрирования см. также Mordell L. J., Messenger of Math., 48 A919), 54—56. Благодаря замечаниям Зигеля вывод A4) из A2) здесь несколь- несколько короче, чем в книге автора Einfuhrung in die analytische Zahlen- Zahlentheorie (loc. cit., ch. 3). Так как g(—m, —n)=g(m,n), случай m<0, n>0 может быть сведен к случаю m>0, ft<!0. Соотношение B1) показывает, что —1 является квадратичным вычетом для простых чисел, сравнимых с 1 (mod 4), и квадратичным невычетом для простых чисел, сравнимых с 3(mod 4). § 4. Теорема 3 принадлежит Эйлеру (Euler L., Opera Omnia, Leipzig-Berlin-Zurich A), III, 240). Примеры и замечания см. в книге Радемахера (Rademacher H., Lectures on elementary number theory, New York, 1964, p. 74, 82,)
180 Примечания Примечания к главе VI В качестве основных источников см. [2], гл. 16—18 и [6]. § 2. Утверждение о том, что г(п)=О(п&) для каждого е>0, эквивалентно утверждению, что r(n)=o(nz) для каждого е>0. Относительно теоремы 1 см. Gauss С. F., Werke, II, S. 272—275. § 3. Относительно теоремы 6 см. Полна Г. и Сеге Г., Задачи и теоремы из анализа, ГИТТЛ, М., 1956, II, стр. 177, 413. Относительно теорем 5 и 6 см. Харди и Райт [2], стр. 259. Теорема 9 была доказана Дирихле в 1849 г. (см. Dirichlet P. G. L., Werke, 11,49—66). Улучшение Г. Ф. Вороным остаточного члена приведено в Ann. ScL Ecole Norm. Sup. C), 21 A904), 207—267; 459—533. Утверждение о том, что остаточный член не может быть () было доказано Харди (Hardy G. H., Proc. London Math. Soc. B), 15 A916), 192—213). § 4. Относительно истории чисел Мерсенна и совершенных чисел см. Диксон [1], I, гл. 1—2. § 5. Относительно теорем 15 и 19 см. Mobius A. F., /. fur die reine und angewandte Math., 9 A832), 105—123; Werke A887), IV, 589—612. См. также Ландау [4], § 150—152. Теоремы 16 и 17 были доказаны одновременно Дедекиндом (Dedekind R., /. fur die reine und angewandte Math., 54 A857), 21) и Лиувиллем (Liouville J., /. de Math, pures et appliquees B), 2 A857), 111). § 6. Относительно теоремы 20 см. Ландау [4], § 59. Теорема 22 принадлежит Мертенсу (Mertens F., /. fur die reine und angewandte Math., 77 A874), 290—291). См. также Ландау [4], § 152. Оценка Zj \к(п)п~* без использования тождества Эйлера (до- п=\ казанного позже в гл. VII, § 4) есть результат замечания Рагхавана Нарасимхана. Относительно доказательства формулы 2jn-2 = ji2/Q п=1 см., например, Knopp K-, Theory and application of infinite series, 1951, p. 237, 323, 376. Примечания к главе VII В качестве основных источников см. [3], гл. 1 и [4], § 12—28. § 1. Относительно теоремы 1 см. Euler L., Opera Omnia, Leip- Leipzig-Berlin-Zurich A), 8, § 279; A), 14, 216—244. § 2. Теорема 3 принадлежит Чебышеву; см. Чебышев П. Л., Соб- Собрание сочинений, т. I, Изд-во АН СССР, М.—Л., 1944, стр. 191—207.
Примечания 181 § 3. Относительно доказательства Пиллаи теоремы 4 см. Pil- lai S. S., Bull. Calcutta Math. Soc, 36 A944), 97—99; 37 A944), 27. См. также Ландау [4], § 22. § 4. Теорема 7 доказана Чебышевым; см. Чебышев П. Л., Соб- Собрание сочинений, т. I, Изд-во АН СССР, М.—Л., стр. 173—190. См. также книгу Ингама [3]. стр. 16—21. Эйлер использовал формальное тождество. § 5. Теорема 8 принадлежит Мертенсу (Mertens F., /. fur die rei- ne und angewandte Math., 78 A874), 46—62). См. также книгу Инга- Ингама [3], стр. 22. Формула Стирлинга дана, например, в книге Титчмарша (Titch- marsh E. С, The theory of functions, Oxford, 1932, 2nd edition, 1939, § 187). Примечания к главе VIII § 1—4. Теорема Вейля была доказана им в Math. Annalen, 77 A916), 313—352. Разъяснение понятия «отклонения» дано Дж. В. С. Касселсом (Gassels J. W., An introduction to Diophantine approximation, Cambridge, 1957, ch. 4; русский перевод: Кас- селс Дж. В. С, Введение в теорию диофантовых приближений, ИЛ, М., 1961.) § 5. Кронекер доказал свою теорему в Berliner Sitzungsberichte A884); см. также Kjonecker L., Werke, Leipzig, Teubner, III (I), 47— ПО. Относительно дальнейших достижений см. Koksma J. F., Diophantische Approximationen, Ergebnisse der Math., Bd. IV, Heft 4 A937). Доказательство Бора (Bohr H.) теоремы 8 дано в /. London Math. Soc, 9 A934), 5—6. См. также Харди и Райт [2], гл. 23. Примечания к главе IX В качестве основных источников см. Minkowski H., Geometrie der Zahlen, 1st edition, 1896, и Diophantische Approximationen, 1927. См. также Siegel С. L., Geometry of numbers, New York University, 1945. § 2. Теорема 1 справедлива без предположения об ограниченно- ограниченности множества 5. Действительно, если оно не ограничено и имеет ме- меу F(S)>2n, то можно взять пересечение множества «S с кубом м: | Xh\ <ZM, l^k^Zn, и если М достаточно велико, то Sm = =SC)Km будет ограниченным множеством, удовлетворяющим тре- требуемым условиям в силу счетной аддитивности меры Лебега. Мы не стремились к рассмотрению оптимальных предположений, поскольку не желали углубляться в вопросы измеримости. Формули- Формулировка и доказательство теоремы 3 продиктованы этими соображе- соображениями. Минковский доказал теорему 3 в 1891 г.; см. его Gesammelte Abhandlungen, I, S. 264. ру К
182 Примечания Доказательство формулы Зигеля (8) дано им в Ada Math., 65 A935), 307—323. Лемма, которая расположена между теоремами 2 и 3, принадле- принадлежит Г. Д. Биркгофу, как это установил Бликфельдт (Blichfeldt, Trans. Amer. Math. Soc, 15 A914)). См. также приложение в книге Касселса (loc. cit., примечания к гл. VIII). В теореме 2 мы использовали тот факт, что замкнутое множест- множество в Rn измеримо по Лебегу. Минковский (loc. cit.) показал, что ограниченное выпуклое мно- множество в Rn имеет объем в смысле Жор дана. См. Minkowski H., Geometrie der Zahlen, Leipzig, Teubner, 1896, 50—60, а также его Theorie der konvexen Korper, Ges. Abh., 2, 142—143, и книгу Бляшке (Blaschke W., Kjeis und Kugel, Leipzig, 1916, 57; русский перевод: Бляшке В., Круг и шар, «Наука», М., 1967) Если выпуклое множество S имеет меру Лебега F(S), 0<F(S) <С <С<х>, то оно ограничено. См. Cassels J. W. S., An introduction to the geometry of numbers, Springer, 1959, p. 109; русский перевод: Кас- селс Дж. В. С, Введение в геометрию чисел, ИЛ, М., 1965. Примечания к главе X В качестве основных источников см. Ландау [4], § 95—103. См. также Siegel К. L., Lectures on analytic number theory, New York University, 1945. § 5. Основная теорема этой главы, а именно теорема 8, была впервые доказана Дирихле в 1837 г., см. его Werke, I, 307—342. Элементарное доказательство было дано Мертенсом (Mertens F., Wiener Sitzungsberichte, 106 A897), 254—286). Новое элементарное доказательство было предложено Сельбергом (Selberg A., Annals of Math. B), 50 A949), 297—304; Canadian J. of Math., 2 A950), 66— 78). Другое элементарное доказательство дал Цассенхаус (Zassen- haus H., Comm. Math. Helvetia, 22 A949), 232—259). Примечания к главе XI В качестве основных источников см. Ландау [4], включая при- приложение П. Т. Бейтмана, стр. 929—931, где дана история доказатель- доказательства асимптотического закона распределения простых чисел. Идея о связи поведения п(х) со свойствами функции ?(s), где s — комп- нулей С (s) восходит к Риману (Riemann В., Uber die Anzahl der Prim- zahlen unter einer gegebenen Grofie, Monatsberichte der Preuss. Akad. der Wissenschaften, Berlin A859—1860), 671—680; Werke, И edition, 1876, S. 136—144; 2nd edition, 1892, S. 145—155). § 1. Первое доказательство асимптотического закона распреде- распределения простых чисел было дано Адамаром (Hadamard J., Bull, de la Soc. Math, de France, 24 A896), 199—220) и Валле-Пуссеном (de la Vallee Poussin C.-J., Annales de la Soc. sci. de Bruxelles, 202 A896),
Примечания 183 183—256). Полное изложение классического доказательства см. в кни- книге Ингама [3], гл. 2. § 2. Относительно теоремы Винера — Икеары см. Ikehara S., /. Math. Phys. Mass. Inst. Tech., 10 A931), 1—12; Wiener N., Annals of Math., 33 A932), 1—100; 787; и Wiener N., The Fourier integral, Cambridge, 1933, § 19 (русский перевод: Н. Винер, Интеграл Фурье и его приложения, «Наука», 1963, § 19). Теорема справедлива при бо- более слабых предположениях, но для вывода асимптотического зако- закона распределения простых чисел достаточно той формулировки тео- теоремы, которую мы рассмотрели. Данное здесь доказательство теоремы Винера — Икеары не ис- использует общей тауберовой теоремы Винера и по существу является доказательством Бохнера (Bochner S., Math. Zeit., 37 A933), 1—9), упрощенным Ландау (Landau E., Berliner Sitzungsberichte A932), 514—521) и Бохнером в его Lectures on Fourier Analysis, Princeton University, 1936. Оно дается в том же самом виде, как и в лекциях автора: Lectures on the Riemann zeta-function, Tata Institute of Funda- Fundamental Research, Bombay, 1953. Элементарное доказательство асимп- асимптотического закона распределения простых чисел было дано Сель- бергом (Selberg A, Annals of Math. B), 50 A949), 305—313).
УКАЗАТЕЛЬ Абсцисса абсолютной сходи- сходимости ряда Дирихле 154 — сходимости ряда Дирихле 153 Арифметическая функция 25 вполне мультипликатив- мультипликативная 103 мультипликативная 25 d(n) 65 D(N) 69 r{n) 63 R(N) 64 ®(x) 89 A(n) 77 |x(/i) 77 n(x) 87 a(n) 74 Ф(я) 23 Ф@ 82 -ф(х) 89 Асимптотический закон распре- распределения простых чисел 165 Бора доказательство теоремы Кронекера 126 Взаимно простые числа 10 Группа абелева 145 — циклическая 145 Делимость 7 Делитель 7 Дирихле L-функция 159 Дробная часть 113 Дробь 14 — несократимая 14 — правильная 14 — Фарея 14 Единственность ряда Дирихле 158 Зигеля доказательство теоремы Минковского 131 Каноническое разложение чис- числа 8 Квадратичный вычет 40 — закон взаимности 50 — невычет 40 Класс вычетов 21 приведенный 22 Коэффициенты ряда Дирихле 105, 150 Кратное 7 Критерий Эйлера 43 Лемма Биркгофа 135 — Чебышева 93 Линейно независимые числа 123 Медианта 16 Множество выпуклое 130 — симметричное 130 Модуль 10 — тривиальный 10 Наибольший общий делитель 10 Наименьшее общее кратное 12 Неравенство Чебышева 101 Обобщенная сумма Гаусса 50 Образующий элемент группы 145 Определитель квадратичной формы 140 — решетки 137 Остаток 7 Отклонение 114 — по модулю 1 117 Положительно определенная квадратичная форма 140 Полоса условной сходимости ряда Дирихле 154 Полуплоскость сходимости ря- ряда Дирихле 153
Указатель 185 Последовательность Фарея 14 Постоянная Эйлера 71 Постулат Бертрана 97 Представление непримитивное 45 — примитивное 45 Произведение рядов Дирихле 157 Простое число 7 Простые числа Мерсенна 76 Прямая сходимости ряда Ди- Дирихле 153 Равномерно распределенная последовательность 114 по модулю 1 116 Решетка 137 Римана дзета-функция 145 Ряд Дирихле 105, 150 Символ Лежандра 41 Система вычетов полная 23 приведенная 23 Совершенное число 76 Соотношения ортогональности 146 Составное число 7 Сравнение 21 Сравнимость по модулю т 21 — по модулю 1 113 Сумма Гаусса 50 Теорема Адамара 166 — Валле-Пуссена 166 — Вейля 118 — Вильсона 41 — Винера — Икеары 168 — Гурвица 37 — Дирихле 113, 163 — Евклида 11 Теорема единственности разло- разложения на простые сомножи- сомножители 8 Теорема Кронекера 123 — Лагранжа о сравнениях 28 — Лагранжа о сумме квадра- квадратов 47 — Ландау 156 — Мертенса 82 — Минковского 131 — Пойа 19 — Ферма 24 — Чебышева 91 — Эйлера 24 Тождество Эйлера 103 Трансляция множества 130 Формальное произведение ря- рядов Дирихле 157 Формула Дирихле 73 — Зигеля 133 — Мертенса ПО — обращения Мёбиуса первая 78 вторая 80 — Стирлинга ПО — суммирования Абеля 106 Функции Чебышева 89 Функция Мангольдта 79 — Мёбиуса 77 — сумматорная 63 — Эйлера 23 Характер абелевой группы 145 — главный 145, 149 — по модулю т 149 Хинчина доказательство теоре- теоремы Гурвица 37 Целая точка 63 — часть 30 Целое кратное 7 Частное 7 Числа Мерсенна 76 — Ферма 18
ОГЛАВЛЕНИЕ Предисловие к русскому изданию 5 Предисловие 6 Глава I. Теорема единственности разложения на простые со- сомножители 7 § 1. Простые числа 7 § 2. Теорема единственности разложения на простые со- сомножители 8 § 3. Второе доказательство теоремы 2 10 § 4. Наибольший общий делитель и наименьшее общее кратное 12 § 5. Последовательности Фарея 14 § 6. Бесконечность множества простых чисел 17 Глава II. Сравнения 21 § 1. Классы вычетов 21 § 2. Теоремы Эйлера и Ферма 23 § 3. Число решений сравнения 27 Глава III. Аппроксимация иррациональных чисел рациональ- рациональными и теорема Гурвица 30 § 1. Аппроксимация иррациональных чисел 30 § 2. Суммы двух квадратов 33 § 3. Простые числа вида 4&±1 34 § 4. Теорема Гурвица 35 Глава IV. Квадратичные вычеты и представление чисел в виде 40 суммы четырех квадратов § 1. Символ Лежандра 40 § 2. Теорема Вильсона и критерий Эйлера 41 § 3. Суммы двух квадратов 44 § 4. Суммы четырех квадратов 47 Глава V. Квадратичный закон взаимности 50 § 1. Квадратичная взаимность 50 § 2. Формула взаимности для обобщенных сумм Гаусса . 50 § 3. Доказательство квадратичного закона взаимности . . 56 § 4. Некоторые приложения 60
Оглавление 187 Глава VI. Арифметические функции и целые точки .... 63 § 1. Общие замечания 63 § 2. Функция г(п) 63 § 3. Функция d(n) 65 § 4. Функция о(п) 74 § 5. Функция Мёбиуса \х(п) 77 § 6. Функция Эйлера ср(я) 81 Глава VII. Теорема Чебышева о распределении простых чисел 87 § 1. Функции Чебышева 87 § 2. Теорема Чебышева 91 § 3. Постулат Бертрана 96 § 4. Тождество Эйлера 103 § 5. Некоторые формулы Мертенса ПО Глава VIII. Теоремы Вейля о равномерном распределении и теорема Кронекера ИЗ § 1. Введение 113 § 2. Равномерное распределение в единичном интервале . 114 § 3. Равномерное распределение по модулю 1 116 § 4. Теоремы Вейля 118 § 5. Теорема Кронекера 123 Глава IX. Теорема Минковского о целых точках в выпуклых множествах 130 § 1. Выпуклые множества 130 § 2. Теорема Минковского 131 § 3. Приложения 137 Глава X. Теорема Дирихле о простых числах в арифметиче- арифметической прогрессии 142 § 1. Введение 142 § 2. Характеры 145 § 3. Суммы характеров. Соотношения ортогональности . 147 § 4. Ряды Дирихле. Теорема Ландау 150 § 5. Теорема Дирихле 159 Глава XI. Асимптотический закон распределения простых чисел 165 § 1. Необращение в нуль функции t,(\+it) 165 § 2. Теорема Винера—Икеары 167 § 3. Асимптотический закон распределения простых чисел 173 Список литературы 176 Примечания 177 Указатель 184
УВАЖАЕМЫЙ ЧИТАТЕЛЬ! Ваши замечания о содержании книги, ее оформлении, качестве перевода и другие просим присылать по адресу: 129820, Москва И-110, ГСП, 1-й Рижский пер., 2, изд-во «Мир» К. Чандрасекхаран ВВЕДЕНИЕ В АНАЛИТИЧЕСКУЮ ТЕОРИЮ ЧИСЕЛ Редактор Д. Ф. Борисова Художник К. И. Милаев Художественный редактор В. И. Шаповалов Технический редактор Е. Н. Лебедева Корректор С. М. Лебедева Сдано в набор 16/VII—1973 г. Подписано к печати 17/IV—1974 i. Бумага тип. № 1. 84Х1087з2 = 2,94 бум. л. 9,87 усл. печ. л. Уч.-изд л. 7,78. Изд. № 1/7266. Цена 62 коп. Зак. 870 Издательство «Мир», Москва, 1-й Рижский пер., 2 Владимирская типография Союзполиграфпрома при Государственном комитете Совета Министров СССР по делам издательств, полиграфии и книжной торговли Гор. Владимир, ул. Победы, д. 18-6.