НАРОДНЫЙ
УНИВЕРСИТЕТ
Е. П. ОЖИГОВА,
кандидат
физико-математических наук
ЧТО ТАКОЕ
ТЕОРИЯ
ЧИСЕЛ
ИЗДАТЕЛЬСТВО
«ЗНАНИЕ»
Москва 1970
517.1
С-45
2-2-3________________
Б.3.47—1969 г.—№ 28
Предисловие
Эта книга познакомит вас с кругом вопросов, которые'
решает теория чисел, с некоторыми приемами их ре-
шения и основными понятиями.
Заметим, что теория чисел часто вызывает интерес про-
стотой постановки ее задач, но затем отпугивает труд-
ностью их решения. Однако именно трудность реше-
ния задач теории чисел привлекла к ней Ферма,
Эйлера, Лагранжа, Гаусса, Галуа.
J3 первом и втором разделах говорится о предмете,
методах и приложениях этой науки, в третьем и чет-
вертом даны краткие исторические сведения.
Остальные разделы посвящены изложению отдельных
вопросов теории чисел, представляющих самостоятель-
ный интерес и доступных для читателя, незнакомого q
высшей математикой.
Что такое теория чисел?
Если задать этот вопрос современным мате-
матикам, они ответят на него по-разному. Один скажет: тео-
рия чисел занимается изучением свойств целых чисел. Дру-
гой ответит: это просто часть теории вероятностей. Третий
заговорит непонятным языком: теория чисел — это теория
алгебраических чисел, теория алгебраических функций с ко-
нечным полем констант и аналитическая теория чисел. Чет-
вертый скажет: теория чисел? Да ее вообще не существует!
Пятый не станет пытаться определять теорию чисел, а посо-
ветует ознакомиться с задачами, которые она решает, и с
методами, которыми она пользуется.
В каждом из этих ответов есть доля истины. Действитель-
но, теория чисел занимается изучением свойств целых чисел,
но она занимается и свойствами других чисел: алгебраиче-
ских, трансцендентных. Правда, что ее задачи часто решают
с помощью теории вероятностей. Если говорить о настоящем
времени, то, действительно, сейчас теория чисел расширилась
до такой степени, что превратилась во множество новых дис-
циплин — в современную алгебру, в геометрию чисел, в веро-
ятностную теорию чисел и т. д. Даже самостоятельных ка-
федр теории чисел в университетах и педагогических инсти-
тутах почти не осталось.
Как же ответить на этот вопрос?
Мы будем различать теорию чисел, понимая под этим
науку о свойствах целых чисел, и современную теорию чисел,
возникшую из первой в связи с расширением понятия целого
числа и с новыми методами.
Эта современная теория чисел уже не является единой
наукой и распадается на разделы, относящиеся к различным
областям математики. С тем же основанием, с каким говорят,
что теории чисел теперь не существует, можно было бы ска-
зать, что почти вся современная математика — это расши-
ренная теория чисел.
В этой брошюре мы коснемся теории чисел и некоторых
Истоков современной теории чисел.
О значении теории чисел писали многие выдающиеся ма-
тематики. Приведем высказывания двух великих ученых
XVIII в. — Леонарда Эйлера и Жозефа Лагранжа. Заметим,
что теорию чисел часто называли «арифметикой» или «выс-
шей арифметикой»,
4
В «Лекциях по математике» (1795) Лагранж писал:
«Один древний говорил, что Арифметика и Геометрия —
крылья математики. Я считаю,- что можно сказать без мета-
форы, что эти две науки являются основой и сущностью всех
наук, изучающих величины.
Но они служат не только основой, они служат, так ска-
зать, еще и дополнением. Так как когда находят результат,
то, чтобы суметь его использовать, необходимо перевести его
в числа или линии; чтобы перевести его в числа, нужна по-
мощь Арифметики; чтобы перевести его в линии, нужна по-
мощь Геометрии»!.
Леонард Эйлер, больше всех разделов математики любив-
ший теорию чисел, горячо защищал ее от обвинений в бес-
плодности и отсутствии приложений:
«Среди всех проблем, которые обычно трактуются в ма-
тематике, никакие не считаются большинством более бесплод-
ными и лишенными приложений, чем те, которые состоят в
изучении природы числа и исследовании делителей...' Кроме
того, что отыскание истины само по себе казалось бы по-
хвальным и достойным человеческого познания, они (древ-
ние) хорошо чувствовали, что благодаря изучению этих пред-
метов расширяется само искусство вычисления, и свойства
ума становятся более способными для выполнения более
трудных задач. Весьма правдоподобным кажется, что эта
наука (математический анализ) никогда не достигла бы та-
кой степени совершенства, если бы древние не посвятили
столько сил развитию такого рода вопросов, какие сегодня
большинство считает столь маловажными из-за их бесплод-
ности. Потому не следует сомневаться в том, что дальнейшее
усовершенствование этих вещей принесет впоследствии новые
успехи анализу»*.
В самом деле, все развитие математики вызвано или ус-
пехами геометрии или достижениями теории чисел. Многие
математические теории построены по аналогии с теоретико-
числовыми. Не касаясь успехов математики, вызванных про-
грессом геометрии (Евклид, Лобачевский, Риман!), остано-
вимся на тесной связи развития математики с достижениями
теории чисел.
В первую очередь развитие математики связано с расши-
рением понятия числа. Объектом теории чисел являются це-
лые числа. Обобщение понятия числа — действительные чис-
ла — позволило Ферма и Декарту создать метод координат,
а с ним аналитическую геометрию и математический анализ.
1 Ж. Лагранж. Элементарные лекции по математике (J. Lag-
ra n ge. Oeuvres, t. 7. Paris, 1877, pp. 198—199),
« Л. Эйлер. О дружественных числах. Собрание арифметических
сочинений (L. Euler. De numeris amicabilibus. Commentationes arithme-
ticae collectae, t, 2, Petropoli. 1849, pp, pp. 627—639),
5
Основная идея этого обобщения или расширения понятия
доела состояла в следующем. Если целым числам ...—3, —2,
,—1, 0, 1, 2, 3,... соответствовали точки на числовой оси ох
с целыми координатами, и обратно — каждой точке с целой
координатой соответствовало целое число, то после введе-
ния действительных чисел каждая точка числовой оси полу-
чила свою координату и каждому действительному числу,
стала соответствовать какая-то точка на числовой оси. Полу-
чилось, как обычно говорят, взаимнооднозначное соответст-
вие между множеством действительных чисел и множеством
точек прямой.
Действительные числа обладают не только свойствами
делых чисел, но и некоторыми новыми свойствами. Их можно
складывать, умножать, делить, их можно возводить в сте-
пень, извлекать из них корни. Они приобрели новое свойство—
между точками на действительной оси нет'промежутков, они
идут сплошь, непрерывно, подобно тому, как чертит линию
карандаш или как течет река. А от точки с целой координа-
той к другой такой же точке приходилось перескакивать че-
рез отрезок длины, равный одной или нескольким единицам.
Это свойство действительных чисел можно выразить словом
непрерывность — множество действительных чисел обладает
.свойством непрерывности. Множество целых чисел обладает
.свойством дискретности или прерывности. Целые числа вхо-
дят в множество действительных чисел, но в нем бесконечно
много и других чисел. Существуют обобщения понятия чис-
ла и обобщения понятия целого числа, в которых сохраняют-
ся свойства целости, дискретности.
Другое расширение понятия числа — комплексные числа,
геометрическим изображением которых служат точки плос-
кости, на которой выбрана система координат. В множестве
комплексных чисел есть числа с целыми комплексными коор-
динатами (например, 2 + 3t; —1 —11 и т. д.). Они образуют
множество целых комплексных чисел, в котором сохраняют-
ся свойства целости. Геометрически такие числа представля-
ются точечной решеткой на координатной плоскости.
Такие расширения понятия числа создают новые разделы
математики и способствуют ее развитию. Особенно успешно
действуют обобщения понятий теории чисел в тех случаях,
Когда они оказываются связанными с геометрией.
Так появился могущественный метод координат.
Измерение длин, площадей, объемов, объединяющее уси-
лия геометрии и теории чисел, привело к возникновению ин-
теграла и к созданию интегрального исчисления.
Процессы и методы теории чисел порождают аналогич-
ные методы в алгебре, математическом анализе и т. д.
Так, алгоритм Евклида (процесс нахождения общего наи-
большего делителя двух делых чисел) явился прообразом
б
такого же алгоритма в алгебре многочленов, алгоритма -раз-
ложения обыкновенной дроби в непрерывную. Теорема един-
ственности разложения целого положительного числа на про-
стые множители была источником новых идей в анализе и
алгебре, основных в алгебраической н аналитической теории
чисел. На ней основано знаменитое тождество Эйлера, по-
служившее, в свою очередь, основой для исследований
П. Л. Чебышева, П. Лежен-Днрнхле, Б. Римана и многих
других. Теория чисел явилась источником идеи теории групп.
Исследования в области теории чисел послужили основой
для открытии Эвариста Галуа.
Предметом теории чисел служат свойства целых чисел.
Расширение понятия числа и появление новых методов из-
меняют предмет теории чисел. Каждое новое расширение
понятия целого числа порождает новую современную (для
этого времени) теорию чисел. Возникли теория целых комп-
лексных чисел, теория целых алгебраических чисел, арифме-
тика кватернионов и т. д.
Исходные задачи теории чисел всегда связаны со свойст-
вами целых чисел двух родов: 1) с мультипликативными*
свойствами (представление числа в виде произведения) и
2) с аддитивными > свойствами (разложение числа на сла-
гаемые). Объединить эти свойства помогают алгебраический
и геометрический подходы к теории чисел.
Рассматривая целые числа как корни неопределенных
уравнений (при алгебраическом подходе), мы объединяем
эти свойства целых чисел. При геометрическом подходе со-
вершенно равноправны мультипликативная задача о числе,
делителей некоторого данного целого положительного числа
и аддитивная задача о числе представлений этого числа в
виде суммы двух квадратов. Геометрически обе задачи сво-
дятся к задаче определения числа целых точек в некоторой
плоской области.
Методы теории чисел и всякой современной теории чисел
порождены или непосредственно теорией чисел, или геомет-
рией, или, имея своим источником эти науки, прошли путь,
пролегающий в других частях математики. Различают эле-
ментарные, аналитические, геометрические, вероятностные
методы. Иногда они применяются комбинированно. В зави-
симости от методов различают, например, геометрическую
или аналитическую теорию чисел. Геометрическая теория чи-
сел пользуется геометрическим истолкованием целых (или
обобщенных целых) чисел и геометрическими средствами до-
казательства теорем теории чисел. Аналитическая теория чи-
сел использует для решения задач средства математического
« Multiplicand (лат.) — умножение.
< Additio (лат.) — прибавление, сложение.
анализа ^дифференциальное и интегральное исчисления, ря-
ды) и теорию функций комплексного переменного. Содержа-
ние методов теории чисел постепенно изменяется и услож-
няется. Например, если при Эйлере аналитические методы
теории чисел пользовались средствами дифференциального
и интегрального исчисления и теории рядов, то после работ
Дирихле и Римана аналитические методы постоянно пользу-
ются теорией функций комплексного переменного. Геометри-
ческие методы теперь связаны с теорией алгебраических мно-
гообразий. Используются в теории чисел теория групп и по-
лугрупп, теория полей и колец —- средства современной ал-
гебры,
Основные применения
теории чисел
Первое и главное применение: объекты, за-
дачи, идеи, понятия, методы теории чисел служат для созда-
ния и развития понятий, методов, алгоритмов в других обла-
стях математики.
Во-вторых, результаты и методы теории чисел могут при-
меняться непосредственно, в той же форме, к другим вопро-
сам математики, например к приближенному вычислению
площадей и объемов, к решению алгебраических уравнений.
В геометрии теоретико-числовые доказательства приме-,
яялись, например, для установления признаков разрешимо-
сти или неразрешимости задач на построение с помощью
циркуля и линейки.
Решение неопределенных уравнений в целых числах (дио-
фантов анализ) служило у Эйлера средством освобождения от
иррациональностей.
В-третьих, теория чисел применяется и в других обла-
стях науки и техники, например в кристаллографии, в радио-
технике,
Из истории теории чисел
Многие понятия, задачи и методы теории
Чисел пришли к нам из древности: от древних греков, китай-
цев, вавилонян, египтян. Об их происхождении говорят, меж-
ду прочим, сохранившиеся до наших дней названия: алго-
ритм Евклида, способ решета Эратосфена, пифагоровы тре-
угольники, диофантов анализ, египетские дроби и т. д.
i
Знакомство с арабскими рукописями и латинскими пере-
водами Евклида и Диофанта-я средние века возбудило у ев-
ропейцев интерес к задачам теории чисел. В XV—XVI bbl
появляются первые' печатные издания «Начал» Евклида1 в
латинском переводе.
В XVI веке выходят в свет латинские переводы «Ариф-
метики» Диофанта. По словам Ж. Лагранжа, перевод 1575 г.
был сделан,с рукописи, найденной в библиотеке Ватикана.
В 1621 г. француз Баше де Мезириак издает «Арифметику»
Диофанта с греческим и латинским текстом и со своими ком-
ментариями. Вопросы теории чисел занимали в это время и
других ученых. Наибольший интерес представляют теорети-
ко-числовые результаты П. Ферма (1601—1665), юриста,
советника парламента в Тулузе. Классическое образование
и большие способности к языкам позволяли ему свободно
читать греческих й латинских авторов и даже консультиро-
вать других знатоков древних текстов. Внимательное изуче-
ние трудов греческих ученых Архимеда, Паппа, Аполлония
привело Ферма к созданию аналитической геометрии (одно-
временно с Р. Декартом) и к созданию начал дифференци-
ального и интегрального исчисления.
Внимание Ферма привлекла книга Диофанта, изданная
Баше де Мезириаком. На полях этой книги рядом с заме-
чаниями Баше появились заметки Ферма. Основные от-
крытия Ферма по теории чисел содержатся в его замечаниях
к книге Диофанта и в его письмах к ряду европейских мате-
матиков. При жизни Ферма не было опубликовано ни одной
его статьи по теории чисел.
Зато в конце XIX — начале XX в. во Франции было изда-
но собрание сочинений Ферма — 5 толстых томов большого
формата. Наибольшей известностью в теории чисел пользу-
ются следующие результаты и-задачи Ферма:
1)	Малая теорема Ферма о том, что а в степени р—1, где а
и р взаимно просты и р — простое », при делении на р дает
в остатке единицу:
ap~l = kp 4-1
k — целое положительное число.
2)	Доказательство теоремы о том, что всякое простое число
вида 4п+1 есть сумма двух квадратов.
* Числа а и b называются взаимно простыми, если не имеют общих
делителей, кроме 1 (например, 3 и 5, 26 и 27 и т. д.). Это свойство запи-
сывают так: (a, b) — 1. Число р называется простым, если делится толь-
ко на себя и на единицу (например, 2, 3, 5, 23). Число, имеющее делители,
отличные от единицы и самого числа, называется составным. Общий на-
ибольший делитель d двух чисел а и b обозначают (a, b) = d. Для вза-
имно простых чисел а и b общий наибольший делитель равен единице:
9
3)	Общее решение уравнения
х*—ауа= 1
в целых- числах.
(а —г заданное натуральное число, не равное квадрату,
х, у — неизвестные целые числа).
4)	До сих Нор не доказанная в общем виде и яеопровергну-
тая «последняя» или «великая теорема Ферма»: уравнение
Xя+ уя = гп
не имеет решений в целых числах при п целом, большем 2.
5)	Ошибочное утверждение Ферма:
выражение 22'"+1, при m — любом натуральном числе,
представляет всегда простые числа.
К сожалению, все почти утверждения Ферма были им ос-
тавлены без доказательств. Это обстоятельство до сих пор
вызывает ожесточенные споры. Одни математики считают,
что у Ферма были доказательства, но до нас не дошли. Дру-
гие — что он получал свои результаты с помощью простых
наблюдений над числами. Ответить на этот вопрос, конечно,
трудно.
Лишь один документ сохранил для потомков применяв-
шийся Ферма метод бесконечного спуска. Это письмо Ферма
к Каркави (1659). Оно было опубликовано только в 1879 г.
и потому Эйлер, Лагранж, Лежандр, Гаусс не были знакомы
с этим документом. Они знали о методе Ферма лишь по за-
мечанию Ферма к одной из задач Диофанта.
В письме к Каркави (1659) Ферма писал, что он нашел
совсем особый путь, новый способ доказательства, названный
им бесконечным или неопределенным спуском. Сначала он
пользовался методом бесконечного спуска только для дока-
зательства «отрицательных предложений». Например, Ферма
доказывал методом бесконечного спуска такое утверж-
дение:
«Не существует прямоугольного треугольника в целых
числах (т. е. длины сторон этого треугольника выражаются
целыми числами), площадь которого была бы равна квадра-
ту целого числа». Доказательство этого утверждения, по Фер-
ма, выглядело так: если бы существовал прямоугольный тре-
угольник в целых числах, площадь которого была бы равна
квадрату целого числа, то существовал бы и другой прямо-
угольный треугольник, меньший первого и обладающий тем
же свойством. Таким же образом из существования
второго треугольника следовало бы существование третьего
треугольника, меньшего, чем второй, и обладающего тем же
свойством. Можно было бы продолжать это рассуждение до
бесконечности. Но не существует бесконечного множества
10
целых положительных чисел, меньших некоторого данного
целого положительного числа. Поэтому мы придем к проти-
воречию. Из нашего рассуждения следует, что невозможно
существование прямоугольного треугольника, площадь кото-
рого равнялась бы квадрату (напомним, что и стороны и
площадь надо здесь брать только целочисленные).
Ферма указывал дальше, что йосле долгих размышлений
он сумел применить метод бесконечного спуска и к доказа-
тельству «утвердительных предложений». Например, он сумел
доказать этим методом теорему о том, что каждое простое
число вида 4п +1 представимо суммой двух квадратов. Фер-
ма перечислял в письме к Каркави утверждения, которые он
смог доказать с помощью своего метода.
Впоследствии Л. Эйлер использовал метод бесконечного
спуска для доказательства ряда теорем, среди которых были
два частных случая теоремы Ферма: уравнения х»+уз*=гз и
x*4-f/4=z« не имеют решений в целых числах. Методом спуска
пользовались и другие математики. Вновь обратились к мето-
ду бесконечного спуска математики XX в. А. Пуанкаре,
А. Вейль и другие в исследованиях, посвященных теории неоп-
ределенных уравнений.
Отметим, что идея сведения задачи к подобной же задаче
с меньшими числами была еще у комментатора и переводчика
«Начал» Евклида Кампануса в XIII в. Может быть, и до него
эта идея существовала в трудах древних греков или в араб-
ских трактатах, не дошедших до европейского читателя.
Хотя сочинения Ферма и были изданы через несколько
лет после его смерти, они не привлекли в то время особого
внимания математиков. Как известно, именно конец XVII в.
и начало XVIII в. были ознаменованы рождением дифференци-
ального и интегрального исчислений, имевших обширное поле
применения. Математики усиленно занялись разработкой и
приложениями этих новых методов, оставив в стороне задачи
теории чисел.
Математики разрабатывали различные отделы нового ис-
числения (дифференциальное и интегральное исчисление, ря-
ды),’применяли интегрирование и дифференцирование к ре-
шению задач механики, физики, геометрии.
Одним из творцов дифференциального и интегрального ис-
числения, или, как его часто называют, математического ана-
лиза, продолжателем исследований Ньютона и Лейбница,
явился Леонард Эйлер (1707—1783). Его любимым пред-
метом была теория чисел. Поэтому не удивительно, что имен-
но у Эйлера возникла мысль применить в теории чисел мето-
ды математического анализа.
Первые сочинения Эйлера по теории чисел были вызваны
результатами Ферма. В одной из работ Эйлер доказал, что
утверждение Ферма о том, что выражение 2зт +1 при т=Г,
U
2, 3, 4,... всегда дает простые числа, неверно. Уже для слу-
чая т=5 2»s + l равно составному числу 641-6 700 417.
В дальнейшем Эйлер доказал почти все утверждения
Ферма, в том числе и упоминавшиеся выше два случая по-
следней теоремы Ферма. Эйлеру принадлежит свыше ста
сочинений по вопросам теории чисел, а ведь теория
чисел — лишь небольшая часть его математического творче-
ства.
До сих пор они еще не изданы на русском языке, хотя
много лет Эйлер жил в Петербурге и-был (с 1731 г.) членом
Петербургской академии наук. Его сочинения публиковались
в изданиях Академии в основном на латинском языке.
Л. Эйлер явился создателем теории чисел. Ему принадле-
жат основные методы этой науки, создание ее основных поня-
тий и некоторая систематизация ее. В архиве Академии наук
(Ленинград) хранятся записные книжки Эйлера. Сейчас со-
ветские математики наряду с опубликованными работами Эй-
лера изучают и эти ценные рукописные материалы. Большая
часть работ Эйлера по теории чисел была собрана и опубли-
кована в «Собрании арифметических сочинений» (Commenta-
tiones arithmeticae collectae, тт. I—II, Petropoli, 1849). В под-
готовке этого издания приняли участие академик В. Я. Бун я-
ковский (1804—1889) и молодой ученый, впоследствии
также академик, П. Л. Чебышев (1821—1894). Они соста-
вили систематический указатель сочинений Эйлера по теории
чисел, который облегчил читателю возможность изучения
трудов великого ученого.
Все арифметические работы Эйлера они разделили на
3 части. I раздел — «Делимость чисел». Сюда вошли рабо-
ту, связанные с мультипликативными свойствами чисел (с
их разложением на множители). II раздел — «Разложение чи-
сел в суммы различного вида» посвящен аддитивным зада-
чам. III раздел — «Диофантов анализ». Он содержит рабо-
ты, относящиеся к решению неопределенных уравнений в це-
лых числах.
В конце указано несколько работ, ранее не публиковав-
шихся, из разных отделов теории чисел.
Ряд важных результатов Эйлера по теории чисел был им
включен во «Введение в анализ бесконечных» (1748).
Большой цикл работ Эйлера начался с доказательства ма-
лой теоремы Ферма. Он дал несколько разных ее доказа-
тельств. При этом он изучил свойства остатков («вычетов»)
от деления чисел на одно и то же простое число.
Так, он выяснил, что при делении на простое число р чле-
нов геометрической прогрессии I, а, а»,..., где (а, р)==1, ни
один из членов прогрессии не делится на р.
При делении на р членов этой прогрессии получается не
более р—1 различных остатков («полная система вычетов»).
12
Если при делении на р один из членов этой прогрессии,
например ак, дает в остатке 1, то k равно р—1 или является
делителем числа р—I.
Эйлер обобщил теорему Ферма на случай составного чис->
ла N: если (a,	— то всегда —1 делится на АС
(Л/>1). Функция ф(Л^), впоследствии получившая название
функции Эйлера, означает количество чисел, не превосходя-
щих N и взаимно простых с ним. В дальнейшем читатель
ознакомится с выводом формулы для ф(Л^).
Особенно важна созданная Эйлером теория степенных
вычетов. Число г называется вычетом степени п по модулю
р, если существует такое число х, что х" при делении на р
дает в остатке г.
Из степенных вычетов внимание Эйлера и многих его
последователей более всего привлекали квадратичные выче-
ты (г называется квадратичным вычетом по модулю р, если
существует такое число х, что Xs при делении на р дает в ос-
татке г). Большим достижением Эйлера явился открытый им
закон взаимности квадратичных вычетов (см. стр. 51).
Эйлер составил таблицы простых чисел до миллиона и
дальше. Для их составления нужно было уметь определять,
является данное число простым или составным. Для этой
цели Эйлер использовал некоторые оригинальные приемы,
среди них применил видоизмененное решетоЭратосфе-
на (см. стр. 59). Используется им также теорема о том, что
всякий делитель суммы двух взаимно простых квадратов
есть сумма двух квадратов.
Аналитические методы Эйлера основаны на установлен-
ной им связи бесконечных рядов и бесконечных произведе-
ний. Так, исходя из равенства
(1—х)(1 — х’)(1— х*)... = 1—х — Xs 4-х‘4-х’— х“—(1)
Эйлер приходит к рекуррентной формуле для суммы о(л)
делителей числа п:
а (п) = <з(п — 1) 4-в (л — 2) — с(п — 5)— с (л — 7) 4- ... (2)
Строго доказать равенство (1) Эйлер не смог, а потому счи-
тал, что и все выведенные из него формулы также еще не
доказаны.
Пример.
Пусть л=6. Составим рекуррентную формулу (2),
Здесь. .
л-1=5,
л-2 = 4,
л —5 = 1.
13
Остальные члены в правой части формулы (2) отсутствуют^
Подсчитаем о(п) для п — 1, 4, 5, 6:
П=1, а(1) = 1,
/1 = 4, о(4) =1 +24-4 = 7,
п = 5, а(5) = 1+5 = 6,
п = 6, а(6)=1+2 + 3 + 6 = 12.
Действительно, о(п) =cr(n—1)+а(п—2) —< <т(п— 5), так как
12 = 6+7—1.
Другая рекуррентная формула для о(п) была найдена
спустя столетие В. Я. Буняковским.
Эйлер, по-видимому, хотел установить аналогичную ре-
куррентную .формулу для л(п) — количества простых чисел,
не превосходящих п, но эта задача не была решена ни Эйле-
ром, ни кем-либо другим из последующих поколений мате-
матиков.
С этими исследованиями связаны работы Эйлера по раз-
биению чисел на слагаемые. Задачи о разбиении чисел были
такого типа: сколькими различными способами число может
быть представлено как сумма двух, трех, четырех или вооб-
ще любого количества чисел? Для того чтобы решить воп-
рос, сколькими различными способами данное число М мо-
жет быть разложено на р частей, не равных между собой,
Эйлер составляет бесконечное произведение:
S = (1 + Xz) (1 + x’z) (1 + x3z).
и ряд
s = l+ Аг + Bz3 + Cz’ +, • г
Приравнивая произведение и ряд, он получает
(1 + xz) (1 + x3z) (1 + Xsz)... = 1 + Аг + Bz3 + Cz* + .
Коэффициенты членов ряда выразятся по формулам:
А = х + х3 + х’ + х* +...
В = х8 + х3 4~ 2х! + 2х* + Зх7 + Зх8 +,, е
С = х* + х3 + 2х’ + Зх’ + 4х'° + 5хи +...
Коэффициенты ряда В показывают, сколькими различными
способами показатель степени х может быть разложен на
две неравные части. Например, в члене 2хв показатель 6
можно представить в следующих видах:
6=1+5 и 6=2+4
(6=3+3 — не годится, так как нужны «различные» ча-
сти) а
14
Коэффициенты ряда С показывают» сколькими различными
способами показатель степени х может быть разложен на
3 неравные части. Например, в члене 4хю показатель 10
можно представить четырьмя способами (среди слагаемых
не должно быть равных; так, например, 10 = 4+44-2 — не
годится): 10= 14-24-7= 14-34-6= 14-44-5=24-3 + 5.
Аналогично решаются и другие задачи на разбиение чи-
сел. Теперь часто говорят о научном предвидении. Легко при-
вести пример такого предвидения у Эйлера. Он указал, что
с помощью разложения
S= 14-х + х’ + х, + х’* + ...
можно будет доказать теорему Ферма о том, что всякое це-
лое положительное число есть треугольное (см. стр. 56) или
состоит из двух или трех треугольных чисел; с помощью ряда
1 4- х 4- л* 4- х* 4- х1* 4-...
можно будет доказать теорему о четырех квадратах (каждое
целое положительное число есть или квадрат, или сумма
двух, трех или четырех квадратов) и т. д. Эйлер указал и
путь будущих доказательств. Чтобы получить разложение
числа на треугольные числа, надо будет, писал Эйлер, взять
дробь
______________1______________
(1 — г) (1 — хг)(1— хЯг)(1—х**)...
и разложить ее в ряд: 14-/>z4-Qz«4-/?z»4-.4 (коэффициенты
этого ряда функции только от х).
Тогда окажется, что
Р = 14-х4-х3 4-х*4-л”4-..
где в показателях степеней стоят треугольные числа
Q будет содержать степени х, показатели которых являются
суммами двух квадратов, R будет содержать степени х, пока*
затели которых являются суммами четырех квадратов, и т. д.
Путь, указанный Эйлером, послужил впоследствии осно-
вой аналитического доказательства Якоби теоремы о четырех
квадратах и ряда других подобных утверждений.
Эйлер применил аналитический метод и к задачам муль-
типликативного характера. Он исходил из выражений
е*-е~х „ ех+е~х
г	н - л 1 >
15
представленных в виде ряда и в виде бесконечного произве
дения: например.
2
1.2	1-2-34
25*»/ ’ *
При х== — г отсюда получается
, I	I я4*2 I	/1 I
Z
25 2
' 1-2-4 ' 1-2-3-4-4 1	4 • Ч ’
Коэффициент при z в левой части этого равенства равен
сумме обратных нечетных квадратов:
л 112	.,1,1.1,
Л-Т = 1 + Т+» + «+:“
При z® будет коэффициент В:
В = ——— = 1 + — + — + — + ... ит. д.
1-2-3 4 4	9»	25»	49’-
Затем Эйлер переходит к изучению рядов, которые получа-
ются при разложении дробей общего вида
1 — аг — рг» — т?3 — ...
В частности, он получает свое знаменитое тождество для
^-функции («дзета-функции»):
1 + — + — + — + — + ...+ —
' 2* З3 4* 5s	/Is
=п
р
где р—все простые числа, as>l.
В случае $= 1 произведение и ряд расходятся.
Вопросов сходимости рядов и бесконечных произведений
Эйлер не рассматривает и потому сам считает, что настоя-
щего доказательства этих утверждений он не имеет.
Большое значение в развитии диофантова анализа имела
«Алгебра» (1768—1769) Эйлера. Здесь и во многих других
работах Эйлер решал различные неопределенные уравнения
в целых числах, следуя своим предшественникам. По одному
замечанию Ферма он сумел реконструировать метод бесконеч-
ного спуска и успешно применял его при решении неопреде-
ленных уравнений, в частности для доказательства великой
теоремы Ферма при п = 4 и п = 3. Часто Эйлер использовал
для решения неопределенных уравнений непрерывные дроби.
С их помощью он решал, например, уравнение Ферма;
%2 — ау?= 1.
16
Много сделал для теории чисел современник Эйлера
Жбзеф Лагранж (1736—1813), занявший место
Эйлера в Берлинской академии наук, когда Эйлер уехал от-
туда в Петербург. Ему принадлежит первое доказательство
теоремы о четырех квадратах, путь которого указал Эйлер,
важные исследования по теории квадратичных форм, полное
решение уравнения Ферма х*— ау*=1 и другие важные ре-
зультаты.
Лагранж доказал теорему Вильсона, приведенную в кни-
ге английского математика Э. Варинга «Алгебраические
размышления» (Г770). Теорема Вильсона состоит в следую-
щем:
Если п — простое число, то число 1-2-3... (га—1)-}-Т де-
лится на п. (Отсюда сразу же следует: если это число
1 • 2 • 3... (га—1) +1 не делится на га, то га не может быть про-
стым).
Э; Варйнгу математики обязаны и другим важным резуль-
татом — он впервые сформулировал такое утвержде-
ние («гипотеза Варинга»): «Всякое целое число есть или куб,
или составлено из двух, трех, четырех, пяти, шести, семи, вось-
ми или девяти кубов; есть квадрато-квадрат» или составлено
из двух, трех, и т. д. до девятнадцати квадрато-квадратов и
так далее. Кажется поэтому, что можно утверждать то же са-
мое для любого числа величин любого измерения»*.
В другом месте Варинг также без доказательства утверж-
дает: «Каждое четное число есть сумма двух простых чисел и
каждое нечетное число является простым или суммой трех
простых чисел» (там же, стр. 379). Эта теорема, известная
под названием «проблема Гольдбаха», впервые была опубли-
кована Барингом в 1770 г. Гольдбах сообщил ее в письме к.
Эйлеру в 1742 г., но переписка Эйлера с Гольдбахом была
напечатана только в 1843 г.
Первый систематический курс теории чисел был опублико-
ван А. М. Лежандром (1752—1833). В первом (1798) и
втором (1808) изданиях он назывался «Очерк теории чисел»,
в третьем издании (в двух томах)—«Теория чисел» (1830).
В «Теории чисел» Лежандра были изложены результаты
Эйлера, Лагранжа и самого автора. Наиболее интересные ре-
зультаты Лежандра: первое неполное доказательство квадра-
тичного закона взаимности, асимптотические формулы для
числа простых чисел в натуральном ряде и в арифметической
прогрессии, аналитическая запись решета Эратосфена, удоб-
ные обозначения:
Е(х) — целая часть числа и (-£- ) — «символ Лежанд-
• Так называлась четвертая степень числа.
» Э. Варинг. Алгебраические размышления (Е. Waring. Medi-
tationes algeoraicae. Cantabrigae, ed, 3, 1782, p. 349).
П
ра». В третьем издании своего трактата Лежандр дал подроб-
ное изложение некоторых глав фундаментального сочинения
Гаусса «Арифметические исследования». Он привел также до-
казательство теоремы о многоугольных числах; принадлежа-
щее О. Коши, и доказательство великой теоремы Ферма для
случая и=5; найденное им самим по методу Л ежен-Дирихле.
Вслед за первым изданием этой книги появился капиталь-
ный и оригинальный труд «Арифметические исследования»
(1801) К. Гаусса (1777—1855), успешно применившего тео-
рию чисел к теоретическому решению древней задачи о по-
строении правильного семнадцатиугольника с помощью цир-
куля и линейки. Гаусс взглянул на теорию чисел с новой точки
зрения, стараясь в ее построении придерживаться единого
принципа.
Он ввел в теорию чисел понятие сравнения (без этого наз-
вания и обозначений сравнения и некоторые их свойства были
еще у Эйлера и Лагранжа).
Если разность b—с делится на число а, то Ъ и с называ-
ются Сравнимыми друг с другом по модулю а. Число а Назы-
вается модулем, а каждое из чисел b и с — вычетом другого
(«6 — вычет с по модулю а»). Обозначается сравнение так;
b = c(mod а)
и читается: «6 сравнимо с с по модулю а». Если какое-либо
число m несравнимо с с по модулю а (т. е. разность m — с не
делится на а), то m называется невычетом с по модулю а.
Понятие и обозначение сравнения было введено Гауссом
по аналогии с понятием уравнения, в связи с тем, что свойства
сравнений напоминали свойства уравнений. Кроме того, срав-
нение можно всегда записать в виде уравнения:
b — c = ka или b — c + ka,
где k — целое число. Вся теория чисел была изложена
у Гаусса с помощью теории сравнений.
Например, малая теорема Ферма у Гаусса выглядела так:
ар-1Е l(modp), где (а, р) — 1.
Действительно, это означает, что при (а, р) = I разность
а”-1— 1 делится на р.
Он рассматривал сравнения первой и второй степени и
сравнения высших степеней, подобно тому как это делается
для уравнений. Свойства сравнений напоминают свойства ра-
венств. Сравнения по одному и тому же модулю можно скла-
дывать, умножать, делить на одно и то же число и т. д. Коэф-
фициенты при степенях неизвестного можно заменять числа-
ми, сравнимыми с ними по данному модулю. Члены сравне-
ния можно переносить в другую часть сравнения с противопо-
ложным знаком.
18
Вычеты обладают многими интересными свойствами.
Пусть т — простое число. Все целые числа при деле-
нии на т дают в остатке одно из т следующих чисел: 0,1,2,
3,т—1. Действительно, для чисел, делящихся на т, оста-
ток равен 0. В общем случае остаток должен быть целым
числом и меньше т. Любое целое число а можем записать
в виде
а= km+r
или в виде сравнения:
а Е г (mod/и).
Все г<т, г—0,1,2,3,..., (т— 1).
Если, например, возьмем число
а = 2т 3, где т > 3, то
2т + 3 Е 3 (mod т).
Объединим все целые числа, сравнимые с одним и тем же
числом по модулю т, в один класс. Так как для каждого мо-
дуля т имеется т возможных остатков, то все числа по моду-
лю т распределяются в т различных классов.
Пример.
Возьмем т = 7. При делении на 7 всегда получится один
из следующих остатков: 0, 1, 2, 3, 4, 5, 6 или число, сравни-
мое с одним из этих остатков.
Например, число
25 E4(mod 7), так как 25 = 7  3+4, остаток 4.
38 Е 3(mod 7), так как 38 = 7-5+3, остаток 3.
— 19++2 Е — 5 (mod 7), так как —19= (—3)-7+2 =
= (-2)-7-5.
Но мы условимся рассматривать только неотрицательные
остатки. Поэтому из чисел +2 и —5 выбираем +2
2Е — 5(mod 7).
49 — 0 (mod 7), так как 49=7 - 7 + 0, остаток = 0.
Таким образом, по модулю 7 существует 7 классов.
I класс — все числа, делящиеся на 7, т. е. 0, 7, 14, 49, 28, 35,
140, —140, —14,...
И класс — числа, дающие при делении на 7 в остатке 1:
1, 8, 15, 29, 36, —6, —13, —27, —34,...
III класс — числа, дающие в остатке 2: 2, 9, 16, 23, 30, 37,..
—5, —12, —26,...
IV	класс — числа, дающие в остатке 3,
V	класс —	»	»	4,
VI	класс —	»	>5,
VII	класс —	»	»	6.
Если число т— составное, то остатки (классы) могут
иметь с т общие делители. Если взять только все те остатки
(или те классы), которые взаимно просты с модулем, то по-
лучим приведенную ‘систему вычетов по модулю т.
1»
Например, если от = 16,
г=0, 1,2, 3,4, 5, 6,7.8, 9.
Взаимно простыми с т будут числа I, 3, 7, 9; числа 0, 2,4,
5, 6, 8 имеют с 10 общие делители.
Следовательно, приведенная система вычетов по модулю
10 будет: 1, 3, 7, 9.
Все остатки: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 образуют полную
систему вычетов по модулю 10. Если m — простое число, то
приведенная система вычетов по модулю m будет: 1, 2, 3,
4... m—1, так как все эти числа взаимно просты с т.
В качестве представителя класса можно взять любое чис-
ло данного класса (по модулю т). .Система представителей
всех классов по данному модулю будет также являться пол-
ной системой вычетов. Система представителей классов чи-
сел, взаимно простых с пг, будет являться приведенной сис-
темой вычетов по модулю т, т. е. все числа одного класса
совершенно равноправны в отношении делимости на т, лю-
бое из них ничем не отличается от других.
Докажем теперь теорему Эйлера. Пусть {а, т)~ 1, х —
пробегает (принимает значения) приведенную систему выче-
тов по модулю т. Тогда произведения ах также будут про-
бегать приведенную систему вычетов по модулю т. где т
может быть и составным числом. Действительно, если
ax = axl (mod от),
и обе части сравнения сократим на а (это можно сделать по
свойствам сравнений), тогда
х = хх (mod от), (ах, от)=1,
т. е. ах^ах только для сравнимых между собой х.
Следовательно, если х пробегает различные числа, не-
сравнимые между собой по модулю от и взаимно простые
с от, то и ах пробегает те же числа (приведенную систему
вычетов).
Таким образом, если xlt х2,.„, хт(т)— приведенная система
вычетов по модулю от, то
ах, • ах,... ах¥{т) = х,х,х,... x<p(n,)(mod от).
Сократив на Xi х2...xV(my , получим
= 1 (mod от).
Это теорема Эйлера (обобщение теоремы Ферма на
случай от-составного). Здесь ф (от) означает количество чи-
сел, непревосходящих от, и взаимно простых с ним.
В частном случае, когда т=р— простое, получаем <р(р) =
= р—1, откуда получаем малую теорему Ферма;
а(₽-0 = l(m0d/>).
20
Гаусс ввел ж рассмотрение целые комплексные чвсла —
первое обобщение целых чисел, создав для них новую тео-
рию чисел- Гаусс дал также геометрическое истолкование
некоторых вопросов теории чисел.
Наследником и продолжателем идей Эйлера, Лагранжа,
Гаусса в теории чисел явился П. Ле жен-Дир икле (1805—
1859).
В школьные годы он увлекался математикой и историей.
Окончив гимназию на родине, в Германии, Дирихле слушает
лекции в парижских высших учебных заведениях: Сорбонне
я в Коллеж де Франс. Он изучает самостоятельно «Арифме-
тические исследования» Гаусса, ставшие на всю жизнь ею
настольной книгой. Интерес к теории чисел совмещался у
Дирихле с увлечением математической теорией тепла м дру-
гими вопросами математической физики, занимавшими тог-
да умы французских математиков.
Позднее, вернувшись на родину, Дирихле познакомился
с Гауссом лично, переписывался с ним, посылал ему свои
сочинения, а в 1855 г. унаследовал его кафедру в Геттингене.
В своей первой работе «О невозможности некоторых не-
определенных уравнений 5-й степени» (представлена Париж-
ской академии в 1825 г., опубликована в Берлине в 1828 г.)
Дирихле с помощью метода бесконечного спуска доказал не-
возможность некоторых классов уравнений пятой степени.
Вскоре после представления им этой статьи в Парижскую
академию было опубликовано, дополнение к «Теории чисел»
Лежандра, являвшегося рецензентом статьи Дирихле, где
методом, аналогичным методу статьи Дирихле, доказыва-
лась невозможность решения в целых числах уравнения
х5-ь^5=25 (великая теорема Ферма для п=5).
В 1832 г. Дирихле доказал справедливость теоремы Фер-
ма для л=14. Он же впервые доказал теорему об ариф-
метическихпрогрессиях (1837);
Всякая арифметическая прогрессия, первый член и раз-
ность которой взаимно просты, содержит бесконечно много
простых чисел.
Для доказательства этой теоремы Дирихле пришлось раз-
работать аналитический метод, основываясь на примерах его
использования, имевшихся в трудах Эйлера.
Другая большая заслуга Дирихле состоит в изучении им
асимптотических законов для теоретико-числовых функций.
В заметке «Об определении асимптотических законов в тео-
рии чисел» (1838) Дирихле говорил о том, что функцию
сложной природы при неограниченном возрастании незави-
симой переменной часто можно приближенно заменять дру-
гой, более простой, функцией, подобно тому, как течение
кривой в геометрии представляется другой линией (напри-
мер, прямой) — ее асимптотой. Дирихле предложил по ана-
21
логии с геометрией называть такую более простую функцию
асимптотическим законом для более сложной, если отноше-
ние этих функций стремится к единице при неограниченном
возрастании аргумента:--^—* 1 при х -*<х> , Дирихле на-
s(x)
шел примеры таких асимптотических законов у своих пред-
шественников: Стирлинга, Лежандра, Гаусса. Своей целью
Ьн считал создание методов, которые, в частности, могли бы
привести и к доказательству асимптотических законов, ука-
занных Гауссом и Лежандром.
Дирихле хотел применить свой метод к задаче о числе
делителей х(п) данного натурального числа га. Оказалось,
что функция т(п) изменяется очень неправильно, более удоб-
ным было взять ее среднее значение.
(2 — знак суммирования). Дирихле находит асимптотичес-
п
кий закон для суммы2 т(Л) 1
п
\\(£),= nlogn-b (2С — 1)п -Ь О (Уп)
и для других функций. Он вводит в теорию чисел и часто
применяет в своих работах «ряды Дирихле», являющиеся
обобщением рядов, которыми пользовался Л. Эйлер. Одна из
его работ так и называется: «Об использовании рядов в
теории чисел» (1838)^ Большое влияние на несколько поко-
лений математиков оказали «Лекции по теории чисел» Ле-
жен-Дирихле, печатавшиеся с дополнениями другого не-
мецкого математика Р. Дедекинда, ученика Дирихле.
Дирихле развил аналитические методы теории чисел, но
ему принадлежат также заслуги и в применении и развитии
геометрических и элементарных методов теории чисел.
Вопросами теории чисел занимались современники Ди-
рихле К. Г. Якоби, Ф. Эйзенштейн, Ж. Лиувилль,
Ф. Миндинг и другие. Середина XIX в. была отме-
чена выдающимися результатами в области теории
чисел. Почти одновременно (в 1848—1854 гг.) появля-
ются исследования П. Л. Чебышева (1821—1894) и фран-
цуза А. Полиньяка (1826—1863) по простым числам, оз-
наменовавшие собой важный шаг в развитии этой теории.
1 Если функции f (х) и g(x) таковы, что абсолютная величина отно-
У (л)
шения ——— остается ограниченной при всех х,то пишут: /(x)=0(g(x))
S\x)
и говорят; «/(х) порядка g(x)>.
22
В 1859- г.- выходит в свет работа ученика Дирихле и Гаусса
Б. Римана о числе простых чисел, не превосходящих дан-
ной величины, где Римаи применил идеи Эйлера и Дирихле
для рядов с комплексными переменными. В этой работе, как
некогда у Ферма, почти ничего не было строго доказано.
В 1890 г. по предложению Ш.-Эрмита Парижская, академ
мия наук выдвинула в качестве темы на премию, на 1892 г.
доказательство асимптотического закона распределения проч
стых чисел в натуральном ряде, рекомендуя использовать,
специально развив для этой цели, идеи работы Римана.
Асимптотический закон распределения простых чисел «
натуральном ряде состоит в следующем:, требуется найти
асимптотическую формулу для функции л(х), обозначающей
количество простых чисел, не превосходящих х (т. е» х)
в натуральном ряде 1, 2, 3, 4,... х,...
Премию в 1893 г. получил французский математик
Ж. Ада мар, развивший методы Римана. Но доказательство
закона распределения простых чисел он сумел дать только
через 3 года, в 1896 г., одновременно с бельгийцем Ш. д е. Л а
Валле-Пуссеном. Оба они использовали при атом идеи
Римана (аналитические методы для рядов с комплексными
переменными). Позднее аналитические доказательства Адама-
ра и Валле-Пуссена были упрощены Э. Ландау и другими ма-
тематиками.
Геометрические методы теории чисел, ведущие свое нача-
ло от Гаусса и Дирихле, особенно успешно развивались в
конце XIX—начале XX в. в работах Г. Минковского
(1864—1909), Г. Ф. Вороного (1868—1908), советских уче-
ных Б. Н. Д е л о н е, Б. А. В е н к о <в а.
Расширения понятия целого числа, идущие от Гаусса и
Галуа, породили теорию целых алгебраических чисел, теорию
идеалов, теорию групп, арифметику кватернионов и другие
разделы современной теории чисел и современной алгебры.
В последнее время математики добились успехов в приме-
нении методов теории вероятностей к задачам теории чисел.
Особенно значительные успехи в этом направлении достигну-
ты советскими математиками Ю. В. Линником, И. П. Ку-
билюсом, Б. М. Б.редихиным, А. Г. Постниковым.
Вклад русских математиков
в теорию чисел
Традиции Эйлера оказали сильное влияние па
творчество русских математиков, в первую очередь петербург-
ских.
Современник Гаусса, Дирихле, Чебышева, Римана, Яко-
би, Абеля и Галуа Виктор Яковлевич Буняковский
23
<1804—1889) много и успешно работал в области теории
чисел. Может быть, его скромные труды оказались в, тени
из-за слишком «яркого фона». Первая работа Буняковского
по. теории чисел «Числовые исследования» (1831) была по-
священа обобщению теоремы Эйлера, в свою очередь обоб-
щившей малую теорему Ферма.
Малая теорема Ферма, как уже говорилось, выражалась
сравнением
о^-1) zz J (mod р),
где (а, р) = I.
Теорема Эйлера}
= 1 (mod п),
здесь (а, л) = 1, а ф(л) — функция Эйлера, выражающая
количество чисел, не превосходящих п и взаимно простых с п.
Буняковский доказал теорему: если разность двух простых
.	п"-1
чисел а—о делится на простое число р, то разность а —
— Ьрп~\ где п — целое положительное число, будет делиться
да рн, или
а”"-1 = Z>₽e-1 (mod р”).
Вот как Буняковский доказывает эту теорему.
Дано, что а—b делится на р, т. е. aE&(mod р) или а = b+pk.
Разложим по формуле бинома Ньютона:
ср’-1 = (b + pk)Pn~l = Ьрп-\ рп-1ркЬРя~1-1 +
+	-pW^ + ...Ч-
1*4
I />я~1 О’”"1 — 1) •. - <Рп~Х — ')	_г+1 tr+1	.
Т 123...(г + 1)	Р 	-Г
+...+ррП~1крп~\
Отсюда
др"’1 _ ftp”-’ = pr‘-k bPn~1 ~1+ рП+''кг (ря~* — ljfcp"’1-2 + ...
1*2
...+ * 1 —	• Ср""1—г)__.gii) +
т 12 3...(г + 1)	т
... + ррЯ~г-1гРп~\
24
Разделим обе части равенства на рп1
=;k b^"1 -1 + k* (рп~1 — 1)^л-1 -2 -+
рп	V
+... + Р?"-1-" Л'*"1-1.
Проверим, что.все коэффициенты в правой части —- целые'чис-
ла. Достаточно для этого рассмотреть коэффициент общего,
члена:
12 3...(г + 1)
Покажем, что произведение 1-2... (г + 1) не может содер-
жать более г множителей, равных р. Для этого подсчитаем,
сколько раз в это произведение входит множитель р. Простое
Число р войдете состав произведения n! — 1 •2-3...71 в сте-
пени, равной (это доказал еще Лежандр) *
Г—]+[-ч]+[-71+---+Г41’
I Р J L Рг J L Р’ J I Р I
где pf наибольшая целая степень п, такая, что п, т- е,
l= Г 1Qg” 1
L logP J ’
Действительно; простое р войдет в состав следующих чисел:
р, 2р, 3/>,...,£ур<
Число войдет в состав следующих чисел:
р\2р',
Lp* J
Число р* войдет в
Р*. 2/, Зр*..Г-Jlр* и т. д.
L/>3 J-
Следовательно, число р встретится в первом ряду£—J раз, во
втором и т, д. Всего оно встретится в пГ
X — Г— 1 4- Г— 1 4- Г—1 4-	I Г я 1
'_bJ+bJ+L/4+-+L7J
раз
’ Знак [х] обозначает «целую часть ж», т. е. наибольшее целое число,
ве превосходящее ж,
Таким образом,

В нашем случае вместо п! имеется (г +' 1)! Обозначим х чис-
ло, показывающее, сколько раз р содержится в Щ
Тогда
где
г +1
Рч
Покажем, что х<г. Мы можем
как [/и] < tn):
p’+I *•
заменить все [т] на т (так
а
Р р2
рч
Р Рг р*
рч
р—ь
Рч
Pq-1
Рч
Здесь4
— ~ < 1, поэтому и r + 1 •
р — 1 pi	р — 1
и сумма
рч-т-
Р р2	рч р—1
Следовательно, р При р-2, х<г+Г; при р=3,
х=~~; при р=
л»
что и требовалось.
Таким образом, рл+',при делении на 1-2-3... г будет
Т. е. - ; --целое, а тогда и
Р • 1 • 4 . . . Г
п РГ(РП-Х~1)...(РП-Х~Г)
1-2.3... (г + 1)
целое и теорема доказана.
26
4
В виде упражнения читатель может: I) доказать, что если.
а+b делится на простое р, (р>2), то а арП~1 + ЬрП~1 делит-
ся на рп, где п — целое, >>2; 2) получить обобщение теоремы
Буняковского:
.Л.-1,., +	.
-----------—— ------------------= целому числу,
Р Pl Р2 •••
если а±Ь не делится на произведение рр^..., {рк > 2).
Буняковский опубликовал много статей по вопросам теории
чисел. Но основной его заслугой является распространение
идей и методов теории чисел в русской науке. Ему принадле-
жат статьи в энциклопедия*, специальный математический
словарь. В 1835 г. вышел сборник «Летопись факультетов на
1835 г.» со статьей Буняковского, где был дан краткий обзор
истории теории чисел от Диофанта до 30-х годов XIX в. Бу-
няковский применял теорию чисел к решению некоторых за-
дач элементарной геометрии. Работы Буняковского тесно свя-
заны с трудами Эйлера, Гаусса, Лежандра. В «Лексиконе чи-
стой и прикладной математики» («А—Д»), изданном Буня-
ковским (1839), давались объяснения математических терми-
нов, в том числе терминологии теории чисел.
В. Я. Буняковский привлек молодого П. Л. Чебышева к под-
' готовке-издания «Собрания арифметических сочинений» Эйле-
ра. Знание сочинений Эйлера и потребовавшееся для их ком-
ментирования изучение трудов других авторов—Лагранжа,
Лежандра, Гаусса, Дирихле — явились прочной основой для
дальнейших занятий Чебышева теорией чисел. Чебышев изда-
ет «Теорию сравнений»—первый систематический курс тео-
рии чисел на русском языке (1849). За. это сочинение Чебы-
шев. был удостоен докторской степени и премии Академии
наук.
Предметом теории чисел Чебышев считал решение неопре-
деленных уравнений в целых числах. В книге были использо-
ваны работы Гаусса, Лежандра, Лагранжа. Были и результа-
ты, принадлежавшие самому Чебышеву. Особенно интересны
три прибавления. Третьим прибавлением была знаменитая
работа «Об определении числа простых чисел, не превосхо-
дящих данной величины» (-1848), в которой Чебышев уточ-
нил предложенные Лежандром асимптотические формулы
для функции л(х) (число простых чисел, не превосходящих х),
где р — простые числа.
27
В работе «О простых числах» (1850), Чебышев рассмот-
рел функции в(х), хР(х). и T(x) t
е(х) = £Ю^, 'Г(л)=2^А
₽<х	Ра<Х
а>2
где р — простые числа.
7'(x) = logl-2-3...fxl,
где [х] обозначает наибольшее целое число,-<х («целая часть
л»). Обозначим К(п)—общее наименьшее кратное чисел
1,2,3...п и разложим К(п) на множители. В состав К(п)
могут войти только простые множители, не превосходящие п.
Простое р, < п, войдет в К(п) в наибольшей степени v, где
v_ Г l°g" 1
L l°g/> 1 ’
Рассмотрим произведение
\ * / \*^/ \ * /
и разложим его на простые множители. Простое число р вой-
дет в это произведение в степени
rks.-H ,08Т Чу
L logP J L IogP J logP J	P
Поэтому будет выполняться равенство:
к(пж(^у
ИЛИ
\ Z /	\ э /	\ П J
Если взять функцию log К(п) = (я), то
i'W=log«l = logK(n) + log/<(-|j+logK(-|-) + r..
или
Все это разные формы тождества Чебышева.
Чебышев выводит основнсе тождество
23
обозначая
Y(x) = 0 (х) + © (л2 ) + в(х3) + ..«
®(*) = SloS*
Р<*
7'(x) = logl-2-3...[x]
(при— <2 слева и справа в тождестве Чебышева будет О,
k
так что оно справедливо для всех — ). На основании этого
тождества Чебышев устанавливает для функции Т. (х) сле-
дующие 2 неравенства:
Т(х)>Г(х) + Т (~р - Т (-р-г (р\ - т (р\
'F (х) - ¥
Для установления этих неравенств с помощью тождества Че-
бышева записывается величина
г w+i Ш - т (т) - т (т) - т (т}
С помощью свойств числа 30 строится знакопеременный ряд}
Так как V(x) не убывает, то ряд слева убывающий, и его
сумма будет заключена между ’Р(х) и ^(х) —отку-
да и получаются указанные неравенства. С помощью форму-
лы Стирлинга для log[x]! имеем
И
Т (х) = 2 tog As = xlogx — x-f-O (log х).
Чебышев выводит оценки для величины Т'(х):
Г(х) + Г(35-
~7'(Ч-')<А* + 410ёх’
\ □ J
29
_т(±\>Ах--f-logx-l.
Для V (х) получаются следующие неравенства!
¥ (х) > Ах —|- log х — 1,
¥(x)-Yf^<Ax + 41ogX.
Первое неравенство дает нижнюю границу для ¥(х), второе
неравенство позволяет найти верхнюю границу для ¥(х).
Действительно, легко проверить, что функция
f (х) = A At + log- х + A log х
удовлетворяет уравнению
f(x) ~ f (~й =	+ V loS х'
\ о /	2
Вычитая почленно это равенство из неравенства
T(x)-T^)<Ax + -|-iogx,
видим,что
¥(x)-¥^-f(x) + ff^<0
\ о J	\ о /
ИЛИ
Y(x)-f(x)<¥(^-ff^-V
\ О /	\ О /
Заменяя последовательно хна — ,— ,...,— , найдем
6 6s бп
Ч(*)-f(X)<¥(f )<W(-f (£-)<...
\ о /	\ о /	\ о* /	\6*/
Так как
то в силу предыдущих неравенств имеем
¥(x)-f(x)<l.
30
Подставляя вместо f (х) ее значение, получим
W < -L Дл + _JL_ |Og. х + Л iog х 4 1]
V{x)>Ax—|~logx —1.
Зная границы для 4х (х), Чебышев сразу же находит границы
и для 0 (х):
0(х)<4лс-ЛП+--’т Jog* х 4-4 log-«4-2,
О	4 10g О	2
0 (х) > Ах -	д Ух- ------ tog1 х —Т 1оё х — 3*
5	б log 6	4
где А = 0,92129202...
Эти оценки позволили Чебышеву доказать, между прочим,
постулат Бертрана (1845)«Начиная от п>3 существует
всегда простое число, большее чем а и меньшее чем 2а—2».
Работа Чебышева «О простых числах» породила много иссле-
дований. Их авторы сначала уточняли границы для 6(х), за-
тем доказали существование предела
lim --у- Прц х _> со.
Из работы Чебышева «Об определении числа простых чи-
сел, не превосходящих данной величины» (1848) следовало,
что если этот предел существует, то он равен 1. Перейдя от
функции 0(х) = 21ogp (р — простые числа) к функции
р<х
л(х) =21, получили асимптотический закон распределения
простых чисел в виде
Х-»от X
logx
Ученики П. Л. Чебышева, петербургские математики
А. Н. Коркин, Е. И. Золотарев, А. А. Марков,
В. А. Марков, Ю. В. Сохоцкий, Г. Ф. Вороной раз-
вивали другие направления теории чисел — теорию квадра-
тичных форм и теорию целых алгебраических чисел. Е. И. Зо-
лотарев наряду с Дедекиндом создал теорию делимости целых
алгебраических чисел. Этими вопросами занимались затем
А. А. Марков, Ю. В. Сохоцкий, Г. Ф. Вороной, И. И. Иванов
подвел итоги сделанного в этом направлении, установив эк-
» J. Bertrand, Journal de 1’Ecole polytechnique, L 18, Paris,
1845, pp. 123—140.
31
бивалентность теорий Золотарева и Дедекинда (работы
И. Иванрва 1.891 и 1893 гг.). А. А. Марков, Г. Ф. Вороной,
Я- В. Успенский рассмотрели частные случаи проблемы дели-
мости алгебраических чисел. Советские математики Б. Н. Де-
лоне; Д. К- Фаддеев и В. А. Тартаковский успешно продол-
жили исследования в области теории алгебраических чисел.
А. Н. Коркину принадлежит метод решения двучленных
сравнений.
Теория квадратичных форм, начало систематическому ис-
следованию которой в России положили совместные работы
Е. И. Золотарева и А. Н. Коркина, с тех пор многие годы уси-
ленно разрабатывалась русскими математиками. Изменилось,
правда, направление исследований.
Коркина и Золотарева, а за ними А. А. и В. А. Марковых,
Г. Ф. Вороного, Б. А. Венкова интересовал вопрос о точной
верхней границе минимумов квадратичных форм с двумя, тре-
мя и более переменными. Современные математики занима-
ются в основном вопросами представления чисел квадратич-
ными формами, оценками количества таких представлений,
его асимптотическим выражением.
Особенно плодотворным оказалось геометрическое истол^
кование свойств квадратичных форм и создание геометриче-
ской теории чисел в трудах Г. Минковского и Г. Ф. Вороного,
а позднее и многих других математиков, в том числе Б. Н. Де-
лоне, Б. А. Венкова. Г. Ф. Вороной занимался также асимпто-
тическими законами. Он уточнил остаточный член в формуле
Дирихле для суммы числа делителей St(k) числа п, усовер-
шенствовав для этой цели метод Дирихле оценки числа целых
точек, под гиперболой. Эти исследования Вороного были про-
должены его учеником по Варшавскому университету В. Сер-
пинским и И. М. Виноградовым. (О работах Виноградова
см. стр. 55—56).
Имя профессора Н. В. Бугаева и его работы долгое
время оставались незаслуженно забытыми. Николай Василье-
вич Бугаев (1837—1903) был одним из первых членов Мос-
ковского математического общества и одним из создателей
журнала «Математический сборник». Этот журнал выходит с
1867 г. до наших дней. С 1866 по 1903 г. он преподавал в Мос-
ковском университете. Н. В. Бугаев был последовательно чле-
ном, секретарем, вице-президентом и, наконец, президентом
Московского математйческого общества. Его разнообразные
научные интересы лежали в области теории сходимости рядов*
функционального исчисления, приближенных вычислений, ал-
гебры, интегрирования дифференциальных уравнений, но
больше всего Бугаев увлекался теорией чисел. В последней
области им написано свыше сорока работ. Бугаев утверж-
дал, что общие приемы анализа приучают рассудок решать
32
различные вопросы так, чтобы частности не влияли на ход и
процесс мысли. Когда же нужно разработать некоторую ис-
тину, не опираясь на общие соображения, не пользуясь выго-
дами заранее выработанного процесса, нужен другой способ
мышления. Этот способ воспитывается решением задач тео-
рии чисел. Теория чисел может справедливо быть названной
«математическим арсеналом, из которого моэйно заимство-
вать самое разнообразное оружие». Он, хотел создать в тео-
рии чисел методы, столь же общие, как и в математическом
анализе, следуя в этом отношении Ж- Лиувиллю.
Бугаев вводит в теорию чисел понятия числового интегра-
ла и числовой производной.
Числовым интегралом по делителям Бугаев называл сум-
му значений функции ](d) по всем делителям d числа п:
2f(d) = F(n).
При этом /(п) называлась числовой производной по делите-
лям для функции F(n) и обозначалась
f(n) = DF(n).
В современных обозначениях формула числовой производной
по делителям может быть записана в виде
о/л	\ a J
где ц.(п) — функция Мёбиуса:
1
Н«) = (-1)*
О
при /1=1,
при и=ААА---А»
для остальных га,
где pi — различные, простые. Сумма
2 f(k) = F(n)
к<п
называлась числовым интегралом по натуральным числам,
функция f(n)=F(n)—F(п—1) — числовой производной по
натуральным числам.
Подобные суммы рассматривались и раньше. Но Бугаеву
первому пришла в голову мысль создать на основе f(n) и
F(n) систематическое «дифференциальное и интегральное ис-
числение» в области теории.чисел.
Теорию чисел Бугаев делил на два больших отдела: (I)
теорию неопределенных уравнений и (II) теорию числовых
Функций. Бугаев считал неверным ограничиваться изучением
числовых функций только с точки зрения их «зависимости от
функций аналитических». Он указывал, что использование
анализа — это только один из методов изучения числовых
33
функций, метод сильный, но не единственный. В I отдел ow
огнес также теорию сравнений и теорию квадратичных форм.
Первый отдел он назвал теорией чисел, второй — числовым
исчислением, или числовым анализом. В исследованиях Бу-
гаева часто встречается символ Е(х) («целая часть лэ)1, ко-
торому автор придавал очень большое значение.
Вот как записывает Бугаев количество целых положи-
тельных решений N неопределенного уравнения- г -]-ах = л:
n=e(—\.
\ в /
Числр таких же решений уравнения
z + ах + by = п
(а, Ь, п>0, различные числа) он записывает двумя спосо-
бами:
Отсюда следует тождество
из которого затем Бугаев выводит ряд следствий. Он распро-
страняет свой прием и на более общие классы неопределен-
ных уравнений. Бугаев, продолжая развивать аналогию меж-
ду математическим анализом и теорией числовых функций,
рассматривал также «числовые ряды». Например, суммы
вида;
г« = ^-Affifi (у)
k<n
— числовой ряд по функциям £(~г,где А(п) определялось
по формуле:
A(n) = D[F(n)-F(n-l)l.
С помощью подобных числовых сумм Бутаев выводит «закон
взаимных разложений»)
* До сих пор мы обозначали целую часть х через [х]. Это обозначе-
ние Гаусса. Бугаев обозначает ее Е (х), по Лежандру.
34
если
то
*<»	\ л /
Ф(в)=2Ф(А)£[А\
*<л	\ * J
S7 ф (Е \ = S Ф (Л) F (е (±\\.
*<я	\	\ Ж //	*<Л	\ \ к / J
Из этого общего тождества он получает множество тождеств
для различных числовых функций.
Вот одна из функций, введенных в теорию чисел Бугаевым:
Пусть
2/'(^) = Iogn,
dm
где l'(d) пока неизвестная функция.
Чему равна 1'(п) — числовая производная логдрифма? Бу-
гаев показывает, что эта функция имеет вид
d/n	\ а /
или, как легко отсюда получить:
i'(«) = -J-Sp(d)logd,
где р(и)—функция Мёбиуса.
До сих пор функцию Г (п) называют функцией Мангольд-
та, рассмотревшего ее значительно позже. Обычно 1'(п) обо-
значаютЛ(п), тогда
Iogn= SA(d).
Если взять от SA(d) числовой интеграл по натуральным
d/n
числам:.
2 2A(d)= Siog^,
Л<л d/n	И<п
обозначить
и выразить Slog/г по формуле Стирлинга:
У log k = п log п — п 4- 0 (log п),
к<п
S5
то получим
п '(Я
2£Л(<0 = 2 2 A(m) = 2Y (-7')
*<nd/ft	*=Х m=l	*<л	\ я J
и отсюда
2 ЧТ (— 'j =nlogn — n + 0(logn),
*<л	\ к )
Легко проверить, что обозначенная Т(л) функция — та же,
что у Чебышева. То есть получено равенства Чебышева
(см. стр. 28). Функция Л (л) такова;
А(п) — 1 ПРИ п~Р^ (где р — простое; а^1, целое)
( 0 для остальных п.
Вообще, если имеется числовой интеграл F(n) ио делителям
от некоторой функции:
2м=т
то числовая производная от F(n), равная f(n), определяется
по формуле:
</л	\ Л /
Эти две формулы представляют собой известную еще Лиувшь
лю и Дедекинду пару формул обращения.
Примеры.
1) Пусть
Р(п) — S 1 = Чл) —число делителей п,
Тогда
К») = 1=2|.(ф(^,т.е.
а/л \ а J
d/n \ а /
2) Пусть F(n) = 2 d = <г(п) СуММа делителей
а/п
Получим формулу:
f (д) = п = 5 Р («О « (-у ).
d/л	\ а ]
Работы Н. В. Бугаева по теории чисел разнообразны и еще
мало изучены. На IV математическом съезде в 1961 г, было
36
показано (А. А. Киселев, Е. П. Ожигова), что из одного об-
щего тождества Бугаева легко получается тождество А. Сель-
берга, лежащее в основе доказательства Сельберга-Эрдеша
закона распределения простых чисел. Идеи Бугаева разви-
вались в исследованиях его учеников и зарубежных ученых:
Гегенбауэра, Чиполлы, Грама и других. О выдающемся вкла<
де советских ученых >в теорию чисел будет сказано в следую-
щих разделах.
Элементы теории чисел
ОСНОВНАЯ ТЕОРЕМА АРИФМЕТИКИ
Всякое целое число, большее 1, представляется единствен-
ным образом в виде произведения степеней простых сомно-
жителей (если не обращать внимания на порядок следова-
ния этих сомножителей):
где alt а,,..,, «*>0.
АЛГОРИТМ ЕВКЛИДА
Наибольший из общих делителей двух целых чисел а. и б
называется их общим наибольшим делителем (ОНД), Обоз-
начим его (а, Ь),
Примеры.
1) Даны числа а=15 и 6 = 48. Их общий наибольший де-
литель равен 3, так как 15 = 3 - 5, 48 = 24-3; 2) Числа а=25,
Ь = 100 имеют
ОНД =(25, 100) =25,
Всякое целое число а можно единственным образом пред-
ставить в виде
a = bq 4- г, где 0<г<6, Ь<а.
Если a=bq-[-r, то множество общих делителей чисел а и б
совпадает со множеством общих делителей чисел bur.
Алгоритм Евклида для нахождения общего наи-
большего делителя двух положительных целых чисел а и б.
Состоит в следующем. Делим а на Ь, получаем равенство
а = bqt -j- г„ 0 < rt < b, затем делим b на rt.
6 = ri<h 4-	0 < G < гх, затем делим гх на г2
а т. д.
гп~2 = ra-iq„ 4- гя, 0 < гЛ < rn-i
87
Процесс заканчивается, когда получим некоторое гя+1“О.
Это обязательно произойдет, так как ряд убывающих целых
положительных чисел Ь, гъ гг,... ле может содержать боль-
ше b положительных целых чисел.
Общие делители чисел а и Ь те же, что и у чисел b, rfl
те же, что у чисел rh г2, и т. д., что у гп-з, rn-i, наконец, те
же, что у г„. В то же время
(a, b) = (b, rfr=(ru г,) = ,.. = (гя_1> гл) = гя.
Таким образом:
1) Совокупность общих делителей чисел а и b совпадает
с совокупностью делителей их ОНД.
2) ОНД равен г т. е. последнему отличному от нуля
остатку в алгоритме Евклида.
Пример.
Найти ОНД чисел 398 и 234:
398 = 234-1 + 164	70=24-2+22
234=164-1+70	24 = 22-1+2
164= 70-2+24	22 = 2-11
Последний остаток=2. Следовательно, (398, 234) =2.
НЕПРЕРЫВНЫЕ ДРОБИ
Выражение
со + —
Я1 +-----------
t
где целые числа Ь\, Ь2,..., с1( с2,—>-0, называется непрерыв-
ной, или цепной дробью. Мы будем рассматривать такие
дроби при Ьк =1 (А=1, 2, 3,...). Бывают конечные и беско^
вечные непрерывные дроби.
Конечная дробь
1
а» 4-... + —•
ап
называется n-й подходящей дробью для бесконечной непре*
рывной дроби
к = ав 4—----з---- }
Р„ и Q„ называются соответственно числителем и знамена'
телем п-й подходящей дроби.
При п= 1, 2, 3,... выполняется равенство
PnQn-l-Pn^Qn = (-\)n-\
38
78 78
33
33
Разложим, в цепную дробь обыкновенную дробь — |
33 _	1 	1	1	1
12	2+ 12
1
2+,—Г-
1+ 3
Это конечная цепная дробь.
Теперь разложим в цепную дробь иррациональное; число У&.
а=/5 = 2 + —;
“1
”- = VsA =/5+2 = 4 + ^-,
5 т * — »	’
где а, = а, = а, и Т. Д.
«=/5 = 2 +-Ц—
Любое вещественное число а разлагается в непрерывную
дробь;
а = ах +
Если а—иррациональное число, то дробь бесконечная, если
а—рациональное число, то дробь конечная. Для рациональ-
ной несократимой дроби а=—разложение ее в непрерывную
ь
дробь тесно связано с алгоритмом Евклида,;
Действительно:
,	а .г,
a = bql + r1, — = qt + -f ,
О	и
Ь — rtqt + Г„ —=<7, + — ,
г»—1 — rnqn-t-i + Гл+i, —-— — qn+i 4------------------------
гп	гп
*9
Отсюда

СРАВНЕНИЯ ] СТЕПЕНИ
Рассмотрим сравнение первой степени с одним неизвест-
ным:
ах = b (mod tn).
1) Если (a, ni)=d и d не делит числа Ь, то сравнение это не
имеет решений.
Доказательство
Допустим, что существует Хо, удовлетворяющее этому
сравнению;
gx0 Е b (mod tri).
Это можно зайисать в виде уравнения
ах0—b=km или ах0—ktn=b, где k — целое.
Здесь левая часть делится на d, а правая не делится, что
невозможно.
2) Если (а, т) = 1, то сравнение
ах Е^ (mod т).
имеет единственное решение.
Доказательство
Возьмем полную систему наименьшие неотрицательных
вычетов.по модулю т, т. е. числа 0, 1, 2,..., (т—1). Так как
(а, /п) = 1, то числа а«0, а-1, а-2, ..., а(т— 1) также обра-
зуют полную систему вычетов. Значит, среди них найдется
одно и только; одно число, принадлежащее тому же классу,
что и число Ь. Обозначим это число ах0.
Будем иметь ox0E&(mod т). Причем х0 — единственное,
удовлетворяющее этому сравнению.
Решение сравнений
/ способ
Для нахождения х0 воспользуемся теоремой Эйлера.
При (a, ni) — 1
а’^Е 1 (mod m).
Умножим обе части этого сравнения на 6:
taT(m,E6 (ijiodm),
Можно переписать это сравнение в виде
а• (ат (mbl • b) Е b (mod tn)
40
и обозначить
Х. = а’('п,-1.б,
вернее,
xt = (mod т).
Это будет единственное решение (класс решений) сравнения.
П р им ер.
Решить сравнение
Эх = 8 (mod 34).
Здесь (У,34) = 1, вычислим <р(34), см. стр. 62—63:
«Р (34) = 34 (1 - — Wl -	= 34-4-— = 16-
т ' '	\	2	17 J 2 17
Поэтому
х. Е 91б-1-8 Е З30-8 Е 8 (2187)’ (mod 34),
но 2187ЕИ (mod 34), поэтому ХоЕ8*(11)2 (mod 34), таким
образом,
ЛЕ 16 (mod 34).
77 способ
Чаще сравнения первой степени решают с помощью не-
прерывных дробей.
Пусть
Ра Pr	ps-i Pt_m
Q. ’ Qi	Q^i ’ Qt a
последовательность подходящих дробей разложения —
в непрерывную дробь:
т ___	1____
а ~ д + 1 г причем (а, т) = 1.
Тогда решением сравнения ах Е b (mod т) является.
л Е (— (mod/n).
Докажем это.
По условию (a, m) = l, (Ps, Q,)el. Поэтому, так как
Р' т п „
— = —, ТО Ps = m, Qs = a.
Qs а
По свойству подходящих дробей P^iQs — PsQt-i— (— 1)J.
Подставим значенияQПолучим aPj_i =(—,
или, иначе говоря, aPf-iE.(—IJ’Xmod/n). Чтобы получить
41
в правей части число Ь, умножим обе части сравнения н<
(—Q* получим
а ((— 1)’ bPs-i) = b (mod m),
т, е. X Е (— 1)г b Pt-i (mod т).
Пример.
Решить сравнение 55х E7(mod 87)*
г»	87
Разложим — в непрерывную дробь.
00
Запишем теперь подходящие дроби:
А 1	А _ 2	А	3	Р„	8
Q. 1	’	Qi	1	’	<?»	2	’ Q,	5 ’
А _	11	А	_ 19 _ Р« _ 87
<?4	7 ’	<?»	.12	Qt	55
Поэтому хЕ(—1)*«7«19 (mod 87) = 46 (mod 87)—искомое
решение.	_
Если (a, m)=d и d/b, то сравнение ax=6(modm) имеет
d решений. Все эти решения образуют один класс по мо*
т
дулю — .
л
Действительно, это сравнение эквивалентно сравнению
atx Е bt (mod гп,),
которое имеет единственное решение, где = — «
d
Пример.
Решим сравнение
111х = 75 (mod 321)..	(1)
Здесь а = 111, 6 = 75, m=321; (111, 321) =3, причем 6 = 75 де-
лится на 3. Поэтому сравнение имеет 3 решения. Делим обе
(Части сравнения и модуль на 3, получим сравнение
37х Е 25 (mod 107).	(2).
Решим сначала это сравнение.
Раскладываем дробь — в непрерывную дробьз
107 _ 9
37
^=2+тг=2+-гт=2 +
33	1+ 33
В этом случае п = 4;
= 2 +------Ц- = Ря_! = 26, Qn-i = 9.
Л"1	1 + 4
О
Получим решение сравнения (2) в виде
х Е (- 1)‘ • 26 • 25=99 (mod 107),
так как — 26 • 25 Е— 650 Е— 8 Е 99 (mod 107).
Следовательно, решения сравнения (1) будут: X— 99;
994-107; 99+2-107 (mod 321), или хЕ99; 206; 313 (mod 321).
Зная решение сравнений, легко решить и соответствую-
щие неопределенные уравнения.
Уравнение ах+Ьу=с запишем в виде ах Ес (mod 6). Если к*
удовлетворяет этому сравнению, то х=хо и у — с* ~~ д— будут
ь
представлять собой решение уравнения
ах+6у=с.
43
Пример.
Решить в целых числах уравнение:
50х—42у-=34.
Здесь (50,42) * 2, 2 делит число 34.
Рассмотрим сравнение 25хЕ 17 „(mod 21)’, или так как
25 — 4 (mod 21)
4х = 17 (mod 21), х = 20 (mod 21), л. = 20.
Поэтому 25  20—21 у»=17, р»=23 (или i/o = 23(mod 25))«
Любое решение диофантова уравнения имеет вид
л = 20+ 21/
У = 23 + 25/,
гдё / — целые числа.
УРАВНЕНИЕ ФЕРМА
Из неопределенных уравнений второй степени особенно
важную роль играет уравнение Ферма
х'-ау* = \.
Это уравнение при каждом целом положительном а, отлич-
ном от квадрата,^ имеет бесконечно много решений в целых
числах. Решения снова получаются с помощью непрерывных
дробей (Бухштаб. Теория чисел, стр. 299—300). Расклады-
вают V а ъ непрерывную дробь. Если k длина периода раз-
ложения ]/^а в непрерывную дробь, то все решения уравне-
ния Ферма в целых положительных числах будут;
х — Pkn—i) у — Qftn—1,
где п—любое натуральное число такое, что kn—четно;
Qt—'подходящие дроби.
Пример.
Найти наименьшие целые положительные значения х, у,
удовлетворяющие уравнению
___	х«—22у»=1.
Разложим V 22 в непрерывную дробь,
“1
«. = -7=U---= в- = ^±1 = 2 + 1
* VZi+4	/22 — 2	3	а,
6	1
«,=_____1___=	3	=Г2 + 4=4 J
*	/22'+2	/22 — 4	2	Т •«
3
44
1_________3	_ /22 4-2 _ < , _I
Ъ Z22** 2 " У22—2	6	* Г ••
-=-±-----= -7=^— =/22 + 4=8 + “»
/22 4-2 ! /22 — 4 Г	о7 1
6
1	/2 + 4
/Й4-4 —8
Поэтому
/22=4+ 11
Период насчитывает 6 членов.. Здесь k=6 (длина периода).
х«=Р5, yt=Q5—наименьшие значения х и у. Вычислим их:
/*5=197, Q=42. Следовательно, х»=197, ^=42.
П р и м е р.
Решим уравнение (найдем наименьшие положительные
Х.У)^
л«—7^2=1. Разложим/~7 в непрерывную дробь;
/7 = 2 + ^-,
*1 — 1 4-----»
•1
•1 = 14------1
“8
/7 = 2+ —
*14-
45
Длина периода k=4. Значит, х0=Р3, у0 = <Эз- Таким обра*
зом, х0 = 8, у«=3.
ВЫВОД ПРИЗНАКОВ ДЕЛИМОСТИ С ПОМОЩЬЮ ТЕОРИИ СРАВ*
НЕНИЙ
Теория сравнений применяется также к доказательству
признаков Делимости чисел. Вот как можно Вывести, напри-
мер, признак делимости Паскаля (1623—1062).
Пусть число N записано в системе счисления с основ»*
нием g‘.
N = ал?я + ал-ig"-1 + ... + ato' 4. a,g + а„
где	g— 1 для всех 6 = 0, 1, 2, 3,..., п.
Обозначим, вычеты степеней числа g по mod m:
bt Е 1 (mod /и), bt = g (mod m), bt E g* (mod tn),..
bn E gn (mod tn).
Число N делится на tn тогда и.только тогдз, когда делит-
ся на т число
°<Д> + O1&1 + d»bt -f",.. + anb„,
В этом и состоит признак Паскаля. Действительно, пусть
справедливы сравнения
bt Е 1 (mod tri), b,=g (mod tn),.... b„ E gn (mod tn).
Заменим степени g их вычетами no mod tn-.
N z= at 4- a,g 4- a,g* 4- ... 4- a„gn = atb, 4- a,bt 4-	+
4- a„h„ (mod tn).
Отсюда следует, что N делится на т в зависимости от
того, делится ли на т число а^Ьо+а^Ь^... 4-а„6„.
В частном случае, при g— 10 (т. е. в десятичной системе
счисления) получаем сравнения
bt Е 1 (mod tri), bt Е 10(mod tn), bt E 10*(mod tri),
bn E Юл (mod tn).
Пусть, например, m = 3. Тогда
bt E 1 (mod 3), b, E 1 (mod 3),..., b„ = 1 (mod 3),
т. e. для делимости числа TV на 3 нужно, чтобы делилась на
3 сумма цифр числа N: ao+fli’+a24----+an-
Точно так же можно получить из признака Паскаля и другие
хорошо известные признаки делимости (на 5, на 7, на .11
и т. д.)«
46
КВАДРАТИЧНЫЕ ВЫЧЕТЫ И СИМВОЛ ЛЕЖАНДРА
Возьмем сравнение второй степени
х* Е a (mod р), (а, т) = 1.
Те значения х, которые удовлетворяют сравнению; называ-
ются . его решениями. Если сравнение & = a (mod р) раз-
решимо, то число а называется квадратичным вычетом для
числа р. Если неразрешимо — а называется квадратичным
невычетом. Мы знаем, что для р—простого и (х, р) = 1 спра-
ведлива теорема Ферма
Е 1 (mod р).
Следовательно, это сравнение имеет р—1 решений: I, 2,...,
Р— 1
Пусть р/-2, тогда р—1 — четное число и сравнение это
можно представить в виде
(х 2 — iX/7” 4-1) ЕЕ Omod(p).
Если имеем сравнение вида
f. (*) fm(x) = ° (mod р),
где[я (х) — многочлен n-й степени, fm (х) — многочлен m-ft
степени, то сравнения
fm (х) Е О (mod р) й f,(x) Е О (modp)
имеют соответственно тип решений Следовательно,
£=L
х 2 —1-0 (mod р)
или
—1
х 2 El(modp) имеет —решений,
а сравнение
p-i
х 2 Е — 1 (modр) имеет тоже решений.
Оказывается, необходимым и достаточным условием того,
чтобы число d было квадратичным вычетом по модулю р
(р—простое нечетное), является выполнение сравнения
р—i
d 2 Е 1 (mod р).
р—i
Числа d, удовлетворяющие сравнению d 2 Е —I (mod р),
будут квадратичными невычетами.
* Если коэффициенты этих многочленов не делятся на р,
47
Обозначим [ — ) положительную или отрицательную еди-
\ Р )
ницу, смотря по тому, будет а квадратичным вычетом или не-.
вычетом числа р (Здесь (а,	—
Этот символ j называется символом Лежандра.
СВОЙСТВА СИМВОЛА ЛЕЖАНДРА
Легко показать, что
p-i
f—) = а. 2 (modp),
\ р /
где р — простое число, (а, р) = 1.
Действительно, по теореме Ферма,
ар~1 = 1 (m0(j
(Р-1) — четное при р ф 2, потому
/ р—1	\ / р—I	х
\а 2 — 1 Да 2 + 1 / = О (mod р).
Если а — квадратичный вычет по модулю р, то
а ~ х* (mod р).
Следовательно, имеет место сравнение
р-1	р-1
а 2 — 1 = 0 (mod р) или а 2 = 1 (mod р).	(1)
Если а — квадратичный невычет по модулю р, то имеет место
сравнение
р-t	р-1
а 2 +1 = 0 (mod р) или а 2 = — 1 (mod р).	(2)
Сравнение (1) означает, что
р-1
(— ) = а2 (mod р).
\ Р /
На основании этого сравнения выводятся свойства сим-
вола Лежандра.
Свойство 1
Если а Е Oj (mod р), то (—] = ( — i.
\ Р 1	\ Р /
Свойство 2
48
Свойство 3
л-t
Свойство 4
(а-Ь с.1 \_____/ д \j
р /	\ р ) ’
Отсюда, в частности, следует, что
так как
т. е. в числителе символа Лежандра можно отбрасывать лю-
бой квадратичный множитель.
Свойство 5
л»-1
(-) = (-!) ’ •
\ Р J
Свойство 6
(Закон взаимности квадратичных вычетов>
л—t g-t
р, q— простые нечетные числа.
Обобщенный символ Лежандра или символ Якоби
/ а \
Можно рассматривать аналогичный символ 1^7) для Р со-
ставного нечетного, большего I:
пусть Р = pt • pt.. .pft, (а, P) = l.
Тогда символ Якоби определяется равенством
(д\____/ д \ / д \	( а \
Р ) ~\ptJ\Pt)" \ Ри / ’
Его свойства аналогичны свойствам символа Лежандра.
Свойство 1
Если а = сп (mod Р), то 0^ =	•
Свойство 2
49
Свойство 3
p~i

Свойство 4
Свойство 5

Свойство 6
Если Р и Q — положительные, нечетные, взаимно простые, те
Р-1	0-1
Поэтому 219 является квадратичным вычетом по модулю
заз.
Пример 2.
Определите, являются ли квадратичными вычетами по
модулю 17 числа 1; 2; 3; 5; 6; 75; 90; 1000.
Пример 3.
Вычислите символы Лежандра — Якоби
32 \ (2Д.	/ 325 >. / 144	/ 1021 \
45 ) ’ \ 12) ’ \ 7 ) ’ \ И9 /	\ 225 ) ’ \ 731 /*
В общем случае, когда а = q, где q — нечетное простое
число, для каких модулей р число q будет квадратичным вы-
четом? Ответ на этот вопрос дает теорема, которая называет-
ся квадратичным законом взаимности.
50
КВАДРАТИЧНЫЙ ЗАКОН ВЗАИМНОСТИ
Если хоть одно из двух нечетных простых чисел р, q имеет
форму 4n + 1, го
да 4п4“3, то
В обоих случаях
(_Р_\ _ (£\
\ я ) \ р )’
Если же оба числа р и q ви-
Р_'\ —
Ч )	\ Р )’
Теорема эта была открыта Эйлером. Лежандр дад непол-
ное доказательство этой теоремы. Первое полное доказатель-
ство дал Гаусс, впоследствии нашедший еще 7 ее доказа-
тельств.
Лемма.
(Доказательство леммы можно прочитать в «1еории сравне-
ний» П. Л. Чебышева) 1.
Если р и q — нечетные простые, то
Геометрическое доказательство закона взаимности, принадле-
жащее Эйзенштейну. На координатных осях отметим точки с
координатами Л (0,0), В cf— , —\ дГо, —
\ 2 j \ 2	2 у \	2 /
где г и q — простые числа (рис. 1).
Обозначим Р число точек с целыми координатами («це-
лых точек»), лежащих внутри прямоугольника ABCD (мы его
будем обозначать /?). Вычислим Р двумя способами.
I. Проведем диагональ АС. Ее уравнение;
У=~ х>
Так как дробь ~ несократимая, то на прямой у—-^-х будет
только три целые точки:
(0, 0), (г, q), (—г,—q)<
~ 1 «Теория сравнений». Поля. собр. соч. П. Л. Чебышева, т. I, АН
СССР, М.-Л., 1944, стр. 69.
51
Диагональ АС не задевает ни одной целой точки внутри R,
поэтому число целых точек

где Р\ — число целых
Рг — число целых
точек внутри А АВС.
точек внутри Д ADC.
Для целых точек в Л АВС х принимает значения
1, 2, 3
2
Проведем прямую MN, перпендикулярную АВ} ее уравнение:
х=и, где и—одно из чисел 1, 2, 3,....	.
&
На отрезке прямой х=и в промежутке от у—О
а
до у— — и лежат целые точки
(и, 0), (и, 1), (и, 2),...,(и,	и]).
Точку (и, 0) исключим, так как она лежит на границе АВ
прямоугольника R, а не внутри него. Последнюю точку сохра-
няем, так как АС не может ее задеть (на АС нет целых точек
внутри /?). Итак, внутри треугольника АВС лежат на отрезке
MN точки
(u, 1), (и, 2).[т- “])•
Количество этих точек:
“<7
поэтому
Но w — любое целое число из 1, 2, 3,
Аналогично вычислим количество целых точек внутри &4DC1
II. Теперь подсчитаем Р другим способом. Количество це«
лых точек (х, у) внутри R, где
х= 1,2,3,.*, Х=1; у = 1,2,3,,»», 1=1,
Л	Л
будет
Поэтому равенство
Можно записать так:
г-1	«-1
Но по лемме
Следовательно,
S3
откуда яолучаем, что
(А) (.£.) = (-If.*'-(-О??
что и требовалось доказать.
Существует свыше 50 доказательств квадратичного зако*
на взаимности, в числе которых доказательства Е. И. Золо-
тарева и В. Я. Буняковского. Закон взаимности для кубиче-
ских вычетов доказывали К. Г. Якоби, Ф. Эйзенштейн,
Т. Сгилтьес, А. М. Журавский и др. Общий закон взаимно-
сти доказал в 1950 г. советский, ученый И. Р. Шафаревич.
ИНДЕКСЫ
Для решения сравнений высших степеней по аналогии с
понятием логарифма вводится в теорию чисел понятие ин-
декса. Если a Eg* (mod т), где k 0, то k называется ин*,
дексом числа а. по модулю т при основании g и обозначает-
ся:
k = indga
(«индекс числа а при основании g»).
Каждое число а, взаимно простое с т, имеет некоторый
единственный индекс k среди чисел ряда 0,1,..., <р (т) >— 1.
Числа с данным индексом образуют класс’ чисел по модулю
tn. Подобно логарифмам индекс произведения сравним с
суммой индексов по модулю <р (т).
fnd^c Е ind?a + ind^ft 4- ind^c (mod <p (m)).
Для индексов составляются таблицы — таблица для на-
хождения индекса по числу и таблица для нахождения чис-
ла по индексу. Для решения, например, сравнения
(mod т) берут индексы левой и правой части;
п indr х Е indg a (mod <р (т)).
Это сравнение разрешимо только тогда, когда indffa кра-
тен d, где d общий наибольший делитель п и ф (т).
Аддитивные задачи
теории чисел
Это задачи, связанные с представлением
целого числа п в виде суммы нескольких целых слагаемых
ak определенного вида:
п = а, + at 4-... -f- af.
St
Например, рассматривают разложения числа п ид сумму
квадратов: п = a*i+ Д2»4-... + а2/ (для различного числа
слагаемых).
Представление числа п в виде суммы простых чисел со-
ставляет знаменитую проблему Гольдбаха:
«Всякое нечетное п представляется в виде суммы трех
простых чисел (л>5).
Всякое четное л представляется в виде суммы двух про-
стых чисел (л>2)».
Эта задача составляла предмет длительных и упорных ис-
следований на протяжении почти двух столетий. В ее реше-
ние «несли большой вклад советские математики Л. Г. Шн н-
рельман и И. М. Виноградов. Но до сих пор проб-
лема Гольдбаха еще не является вполне решенной.
Задача представления числа л в виде суммы m-х степе-
ней чисел, a * составляет известную проблему Баринга, зани-
мающую центральное место среди аддитивных проблем тео-
рии чисел.
Под гипотезой Баринга понимают обычно следующее ут-
верждение:
для любого целого k существует целое s = s (й), такое,
что каждое целое л есть сумма не более s й-х степеней, ила
иначе:
для каждого целого k существует целое s, зависящее
только от k (где й,а>0), такое, что диофантово уравнение
л = а* 4- л* -f-... 4- а* .
имеет хоть одно решение в целых неотрицательных числах.
В частном случае (k = 2) получаем задачу о представление
числа в виде суммы квадратов, исследованную Эйлером л.
Лагранжем.
Первое полное решение проблемы Варинга дал Давид
Гильберт в 1909 г. Следующее решение другим способом
дали Харди и Литлвуд, использовав для этой цели средства
теории функций комплексного переменного (1919—1923).
При этом Харди и Литлвуд, кроме доказательства того фак-
та, что уравнение
л = с 4* л 4- • • • + °
1 1	2 1	J
имеет хоть одно решение в неотрицательных числах, вывели
асимптотическое выражение для количества решений этого
уравнения (чего не было у Гильберта). Кстати, именно ис-
ходя из этого асимптотического выражения, они и сумели
доказать проблему Баринга.
В 1924 г. И. М. Виноградов опубликовал свой первый спо-
соб решения проблемы Баринга, очень просто устанавливав-
ший верхнюю границу числа представлений л.
55
В 1928 г. он дал другой метод, упрощавший вывод асимп-
тотического выражения числа решений. Продолжая совер-
шенствовать свой метод тригонометрических сумм, И. М. Ви-
ноградов применял его к различным аддитивным задачам, в
частности к проблеме Гольдбаха. Л. Г. Шнирельман предло-
жил для решения аддитивных задач теории чисел свой ме-
тод, основанный совсем на других принципах, позволивший
ему доказать впервые, что всякое целое положительное чис-
ло есть сумма ограниченного числа простых слагаемых. Этим
был сделан первый важный шаг к решению проблемы
Гольдбаха, позднее решенной И. ,М. Виноградовым для всех
достаточно больших нечетных чисел. Элементарное решение
проблемы Баринга по методу Шнирельмана сумел дать
Ю. В. Линник в 1943 г.
Еще одна аддитивная задача—о представлении целого
п в виде суммы многоугольных чисел —издавна занимала
умы многих математиков. Поясним термин «многоугольные
числа». Числа треугольные получаются суммированием по-
следовательных натуральных чисел:
1; 1 + 2=3; 14-24-3 = 6; 1+2 + 34-4 = 10; 14-24-34-4+5=15;...
Их можно изобразить геометрически (рис. 2).

Рис. 2
Обозначим n-ое треугольное число Рз. Для него будем
иметь выражение (сумма п членов арифметической прогрес-
сии с разностью 1),
Р, = 1 4- 2!-|- 3 4-... 4- п = '*£’±11.
Квадратные числа получаются суммированием п членов ариф-
метической прогрессии с разностью 2 (нечетных чисел):
1,14-3,14-34-5, и т. д.
Р? = 14-3 + 54- ,..4-(2n-l) = (2^~P+1 п =
А

Геометрически их можно представить в виде (рис. 3).
п-е m-угольное число Рпт представляет собой сумму п чле-
нов арифметической прогрессии, пер-вый член которой 1, а
разность равна (т — 2), т. е.
рп — (т — 2)п* — {т — 4)п
т	2	*
Отсюда, например, выражение для пятиугольных чисел (т =
i=5) (рис. 4).
Злг— л   (Зл — 1)л
Это будут числа: При п = 1 Р’ = п = 2 Р2 = ь п=3 Р^ = я = 4Р4 = о . о 'с /7’2	/7 =	»	2 = 1, = ^•2 = 5, = 9-'-3 = 12, = ^^•4 = 22. 2 •3	/7 = «	Л = 5 Рис. 4 57
Многоугольные числа интересовали еще пифагорейцев, а
позднее Диофанта, многих восточных и европейских матема-
тиков средневековья, Кардано, Штифеля, Декарта, Вал-
лиса. '
Ферма высказал предположение, что каждое целое число
ебть либо треугольное, либо сумма двух или трех треуголь-
ных чисел; либо квадратное число, либо сумма двух, трех или
четырех квадратов; либо .пятиугольное, либо сумма не более
пяти пятиугольных чисел и т. д.
Для случая квадратов эта теорема была доказана сов-
местными усилиями Эйлера и Лагранжа. В общем случае ее
В' 1815 г. доказал О. Коши, знамевитый французский матема-
тик (1789—1857).
Решето Эратосфена
«Решето Эратосфена» — так называется
Способ высеивания простых чисел, принадлежащий древне*
греческому ученому Эратосфену (Эратосфен родился в Кич
рене в 276 г. до н. э., умер в 194 или 196 г. до н. э., заведо*
вал библиотекой в Александрии),
Из натурального ряда чисел
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,.,
вычеркивают все числа, делящиеся на 2 (кроме 2); делящие?
ся на 3 (кроме 3), на 5 (кроме 5) и т. д. Остаются после,
этой операции «решета» только простые числа ц It
1, 2, 3, 5, 7, 11, 13; 17,.,
Этот древний способ дожил до наших дней, пережив немало
превращений. При этом, если мы хотим получить все простые
числа, не превосходящие некоторого числа х, то достаточно
вычеркивать все числа, кратные простым, не превосходящим
Ух.
Действительно, пусть pi, рч—, рп —все простые числа, не
превосходящие У х. Тогда всякое составное число N, такое,
что	х, можно представить в виде произведения не
менее двух множителей. Пусть это будет N = А • В, 1£предпо«
ложим, что А<В. Поэтому А не может быть > У х (тогда
было бы и N>x). Следовательно, А< У~х. А или простое
(тогда оно одно из чисел pi, Рг, Рз-, Рп), или А составное,
тогда его простые множители также содержатся среди pi,
р-,..., Рп- То есть это N будет вычеркнуто как число, кратное
какому-нибудь из чисел pi, рг,..., рл.
58
\7 7 >	1	7	V	13	17	19	23	29
о	р	р	р	р	P	Р	' Р	Р
1	р	р	р	р	Р	7	О	Р
2	р	р	р	р	7	Р	р	Р
3	7	р	р-	р	P	Р	р	7
	и	р	р	7	Р	Р	и	Р
								
Рис. 5
Эйлер использовал измененное им решето Эратосфена для
составления таблиц простых чисел и для отыскания наимень-
ших делителей.
Все числа по модулю 30 будут представляться в виде N =«
r=30 q+r. При г=0, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18,
20, 21, 22, 24, 25, 26, 27, 28 эти числа имеют с 30 общий де-
литель и, следовательно, не могут быть простыми. Могут быть
простыми только числа Л/=30?+г при г=1, 7, 11, 13, 17, 19,
23, 29.
Их и надо проверять. Эйлер составляет таблицу наимень-
ших делителей (рис. 5).
Слева записываются значения <7=0, 1, 2, 3, 4, 5,...; ввер-
ху— значения г=1, 7,11, 13, 17, 19, 23, 29,
В клетках таблицы
записывают букву р, если
.число N = 30<7 + г — про-,
стое, и записывают на-
именьший делитель этого
числа, если оно составное.
В первой строчке стоят
всюду буквы р, так как
числа М=30-0-Ьг—все
простые.
Во второй строчке
стоят наименьшие делите-
ли чисел М=30* 14-г, т. е<
числа N = 31, 37, 41, 43,
47, 49, 53, 59. Так как все эти числа, кроме числа 49, простые,
то во всех клетках, кроме шестой (соответствующей числу 49),
будут стоять буквы р. В шестой клетке записываем число 7 —
наименйший делитель числа 49, В третьей строчке стоят наи-
меньшие делители чисел N — 30 • 2 + г, т. е. N = 61, 67, 71»
.73, 77, 79, 83, 89.
Среди них 77 — составное, остальные простые. Наименьший
делитель числа 77 снова 7,
В четвертой строчке составными будут числа N = 91 =7 • 13 и
N — 119 = 7-17. Наименьшие делители снова = 7 и т. д. Про-
веряем только, делятся ли числа из прогрессий Л?=30<7 + г
для указанных 8 значений г на одно из этих г, начиная с наи-
меньшего. Все остальные числа проверять не надо, так как
.они составные (имеют с 30 общий делитель).
В. Я. Буняковский в статье «Об одном видоизменении спо-
соба, известного под названием Эратосфенова решета»
(1882) дал оригинальный прием, посредством которого мож-
но находить все простые числа определенного вида, заклю-
ченные между двумя данными границами. Он решает, напри-
мер, такую задачу: найти все простые числа, которые начи-
59
паются я оканчиваются цифрой 1 и заключены между ЮГ
и 191 включительно. Пусть х такая цифра (число десятков),
что если поставить ее в числе 101 вместо нуля, то получится
составное число, которое делится на простое р. Получим ра«
девство
д . pk—Юх » 101 или 101 + 1 Ох —0 (mod р)’,
где Л — целое число.. Так как число 1x1 должно делиться на
р, то р не может быть равно 5 (тогда бы число оканчивалось
на 5 или на 0), но может быть одним из чисел 3, 7, 11, 13.
Надо теперь решить полученное неопределенное уравне-
ние
pk-10* = 101.	(1)
Пусть Ао, хв — наименьшее целое решение уравнения
рА-10х = 1.	(2>
Тогда х = 101хо pz.
Но 0< х<9, поэтому для определения 2 имеем следующие
два неравенства}
,4^ й
р	р
Полагаем последовательно р = 3, 7, 11, 13. Для р = 3 урав-
нение
рА0 — 1Охо = 1, примет вид ЗА, — 10х, = 1;
подберем х« и А,:
Х. = 1, ЗЛв —10=/=!
х, = 2, ЗА, — 20 = 1 при А, = 7,
т. е. хв « 2, А, » 7.
Тогда х а= .101 <2—3z,
где
. 101-2 _R~1	. 101.2-9
= 67Т’ 2> —
т. е. 67-i- ^2^64 4•
•>	о
Следовательно, z ** 65, 66, 67.
Тогда
х = 202-3.65=7
X = 202—3.66=4
X = 202—3.67=1.
Подставляя эта значения х в число 101 вместо 0, получим
числа 171, 141, 111. Все эти числа делятся на 3.
Аналогичным образом для р = 7 найдем число 161. Для р =*.
= И 4Hcaof 121, для р = 13 такого числа нет.
Таким образом, между 101 и 191 составными числами бу-
дут 111, 121, 141, 161, 171. Следовательно, числа 131,151,181,
191 — простые. Читатель может по способу Буняковского:
1) определить между 1001 и 1991 все простые числа, начина-
ющиеся и кончающиеся на 1;
2) найти все простые числа между 100 и 1000 такие, что в
каждом из них сумма трех составляющих цифр равняется
постоянному числу, например, 16.
Эти задачи также были решены в статье В. Я. Буняковского.
Решето Эратосфена, решето Эйлера, решето Буняковского
и др. содержатся в более общем решете П. С. Порецкцго. Он
ввел функцию, значениями которой служат числа, взаимно
простые с произведением
П(р)=^р^Р,...рп
я тем самым с любым числом вида т = р? р? .. .р?5,
где pi, рг рл простые,а* а„^0 целые. Эта функция,
выражающая все числа, взаимно простые с данным чис-
лом т, выглядит так:
Т(/7(р))-Л/7(р).
Значения Y (т)—все числа, взаимно простые ст я-</п.
С помощью решета Эратосфена Эйлер, а затем Пуаясо
определяли количество чисел, взаимно простых с п и не пре-
восходящих п. Эту функцию мы обозначали <р (л).
Пусть имеется п последовательных натуральных чисел:
1,2, 3.....п;
Вычеркнем из этого ряда все числа, которые делятся на pi,
таких чисел будет — «
Pt
Останется п---— чисел, не делящихся на рь Теперь из остав-
Pi
шихся чисел выбросим все числа, делящиеся на рг.
Их будет
п
п— —
Pi
' •
Л	Л
Останется
61
Продолжая дальше выбрасывать числа, делящиеся ва р3,
pt, V, Рк придем к формуле
<р (п) = П (1 - -1- у 1 - А _ (1 - А \
Ч PiJ\ PiJ \ Рк)
Пример.
Сколько имеется натуральных чисел, не превосходящих
100 и взаимно простых с ним?
<р(100) = 100<1 —
1-1 = 40.
так как 100 = 2« • 5», т. е. р\ — 2, р2=^ 5.
Первую аналитическую запись «решета Эратосфена» встре-
чаем у Лежандра в его «Теории чисел».
Пусть [х]— наибольшее целое число, не превосходящее х.
Количество чисел, х, оставшихся после вычеркивания чи-
сел, кратных 2, 3, 5 и другим простым р х, обозначим К,.
Тогда
к=и- УГу]+ У Г—1- У Г—]+•••
LP/J Л4 L PiPk J ЛЛ [p:PjPk]
р‘	рРк _	р1ркр)
р{<Ух	ptpk< Vx	_ p^p^iGT	(1)
К — число простых р, таких, что Ух<р^х, плюс 1 (так
как после вычеркивания останется" еще одно число —
.единица).
Позднее (1857) эта формула была вновь открыта Лиувил-
лем и Дедекиндом. Ее обнаружил в том же году в «Теории
чисел» Лежандра (1830, 2, § 11) английский математик
Г. Дж. С. Смит, который назвал этот принцип принципом
перекрытия.
Лежандр предлагал подобным же образом определять
число простых, не превосходящих х, содержащихся в ариф-
метической прогрессии.
Суммы в (1) распространяются по всевозможным комбина-
циям простых чисел рь р2, Рт Vх по одному, по два,
по три и т. д.
Сумма справа обрывается сама собой. Действительно, чтобы
получить количество чисел, которые не делятся на 2 и не пре-,
восходят целой части числа х (х — любое вещественное,
не обязательно целое), надо из количества всех чисел, не
превосходящих [х], вычесть количество чисел, делящихся на 2
и С И; таких чисел
будет |~ . Полу
/чаем:
— , так, как мы оперируем только с целыми числами и
2
62
Выбросим теперь все числа, которые делятся на 3 и на 5,
Соответственно получим:
•-на 31^ [х1-Г41-Гт1*
I At | I О I
— на 5: ЭД _ Ry] ~ Гт1 “ РЯ 1т>л.
1^1 I <Э J I □ I
Получим- после выбрасывания чисел, делящихся на 2, 3, 5Г,.
где р/ — все простые числа,
Но при этом оказывается, что некоторые числа мы выбрасы-
вали по нескольку раз. Например, число 6 делится на 2 н
на 3, значит, мы выбросили его 2 раза (среди чисел, деля-
щихся на 2, н среди чисел, делящихся на 3); число 28 делит-
ся на 2 и на 7, оно выброшено дважды, и т. д. Поэтому надо
к полученной разности прибавить количество тех чисел, ко-
торые делятся сразу на 2 простых:
"Лк
Затем замечаем, что среди этих чисел есть такие, которые
выброшены 3 и более раз.
Подсчитаем их количество?
[(где pi, Pk, Р) — все различные простые,ph рк, р.^У^х .
Это количество нужно вычесть из полученной суммы, чтобы
восстановить справедливость:
Продолжая дальше те же рассуждения, придем к формуле
Лежандра (1). Сумма справа конечна, так жак простых чи-
сел, конечное число.
В 1832 г. Мёбиус ввел функцию ц (п) («функция Мёбиу-
са»), с помощью которой аналитическая запись решета Эрато-
сфена принимает более удобную форму;
63
Напомним, что определяется эта функция так
Н(О =
1 для / = 1
О для I, содержащих квадрат какого-нибудь
простого числа
(—1)*ДЛЯ 1 = Р1Р2РЗ-Р.,
(а — количество простых множителей в /)„
Эта функция часто употребляется в разных вопросах теории
чисел.	_
Заметим, что, вычеркивая все числа, кратные 2, 3,..., -^Ухг
мы в то же время вычеркнули р сами числа 2, 3,..;, х .
Чтобы получить количество всех простых чисел х (обозна-
чают его л (х)), надо к К. прибавить количество простых чи-
сел, Х х, так как
/( = k(x)-k(/x) + 1.
В количество чисел К входит 1 (она не является простым
или кратным простого числа и поэтому также не вычеркива-
лась). Отсюда
ф) = /( + <х)-1
Француз А. Полинт>як (1826—1863) изложил историю
метода решета Эратосфена в заметке «Исторический очерк
о решете Эратосфена» (1853). Полиньяк считал этот метод
одной из самых больших ценностей, завещанных античностью,
хотя этот метод был почти забыт в его время. Полиньяк видо-
изменил метод решета Эратосфена, следуя Лежандру. Его
интересовало, в каком порядке следуют вычеркнутые и невы-
черкнутые числа. Он берет ряд чисел (а):
О, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15... и вычеркивает,
начиная с 0, каждое второе число.
Получается ряд (а^):
1, 3, 5, 7, 9, 11, 13, 15, 17, 19,
Расстояние между двумя невычер.кнутыми числами (коли-
чество вычеркнутых чисел) равно 1. Он называет диатомиче-
ской последовательностью последовательность, членами кото-
рой. являются расстояния между вычеркнутыми членами
1,1, 1,1,...
Теперь из ряда (а) вычеркнем (кроме каждого 2-го) каждое
3-е число, также начиная с 0. При этом получается ряд
(аг):
1, 5, 7, 11, 13, 17,.../;
Расстояния между каждыми двумя невычеркнутыми числами
(число вычеркнутых членов) будут:
1, 3, 1,3, 1, 3, 1,...,
Это диатомическая последовательность трех, или 2-я диатоми-
ческая последовательность. Теперь вычеркнем, начиная с О,
каждый пятый член последовательности из ряда (а) (кроме
каждого 2-го и 3-го), получим новый ряд чисел (а3):
1, 7, 11, 13, 17, ...
Диатомическая последовательность пяти:
1, 5, 3, 1, 3, 1, 3, 5, 1, 5, 3, 1, 3, 1, 3,... и т. д.
Полийьяк изучил свойства диатомических последовательно-
стей.
Всякая такая последовательность — периодическая. Пер-
вое число (вычеркнутое) ряда (ая), после которого коли-
чество вычеркнутых членов повторяется периодически, равно
произведению всех простых чисел до рп включительно (1-2;
1-2-3; 1-2-3-5; 1-2-3-5-7;...). Обозначим его Прп. Во
всякой диатомической последовательности период начинается
с 1, а члены периода, равноудаленные от концов периода (от
1 до 1), равны. Число членов периода n-й диатомической по-
следовательности есть произведение
(2 _ 1)(3 - 1)(5 - 1)... (рп-х - \){рп - 1) = А(Прп).
Сумма членов периода n-й диатомической последовательности
равна Прп—А(Прп). Полиньяк отмечал еще некоторые
свойства диатомических последовательностей.
Потом Полиньяк применил диатомические последователь-
ности к задачам теории чисел. Первой тёоремой Полиньяка
была следующая:
Между рпи рп всегда имеется по крайней мере одно про-
стое число.
Вторая теорема гласила, что между а" л a n+1 всегда есть
по крайней мере одно простое число. Эти утверждения указы-
вали границы, между которыми содержится хоть одно простое
число. Более узкий промежуток был указан Бертраном («по-
стулат Бертрана», 1845, см. стр. 31). В сентябре 1854 г.
Полиньяк опубликовал «Новые исследования о простых чис-
лах» в «Журнале чистой и прикладной математики» Лиувилля.
Здесь все теоремы о диатомических рядах были даны с дока-
зательствами. Была выведена и формула для
\ Z /	\ 5 /	\ п /
(см. стр. 28).
65
Постулат Бертрана был доказан Чебышевым как частный
результат в работе «О простых числах» (1850). Узнав о ра-
ботах А. Полиньяка, Чебышев заинтересовался ими и, будучи
во Франции, специально ездил в город Мец беседовать с По-
линьяком. Тот еще несколько лет публиковал статьи по тео-
рии простых чисел, где доказал, между прочим, несколько
утверждений Чебышева, потом участвовал в войне в качестве
капитана артиллерии и математикой больше не занимался.
В одной из заметок 1859 г. Полиньяк писал: «Г. Чебышев
первым доказал, что между а и 2а имеется всегда хоть одно
простое число, опираясь на одну формулу, которую мы с
ним нашли почти одновременно. Можно пойти далее и ут-
верждать (начиная от а = 2), что всегда между а и 4а имеет-
ся простое число вида 4n + 3»i. В доказательстве этого ут-
верждения использовался способ, примененный Чебышевым
в его статье «О простых числах», и не использовались диато-
мические ряды. Отсюда видно, что Полиньяк пришел к вы-
воду о преимуществе способа Чебышева.
В 1915 г. в Бюллетене Дарбу известный французский ма-
тематик Адамар напечатал «Работу Жана Мерлена о простых
числах». Адамар писал, что Жан Мерлен (Merlin), молодой
ученый, помощник астронома в обсерватории города Лиона,
подававший большие надежды, пал на поле брани. (Шла пер-
вая мировая война.) Это был очень скромный и очень трудо-
любивый человек.
«3 или 4 года назад, — продолжал Адамар,— он сообщил
мне набросок (essai) доказательства знаменитой теоремы
Гольдбаха: «Всякое четное число есть сумма двух простых».
В этом доказательстве был пробел и по этой причине оно не
было опубликовано. Однако мне совсем не кажется доказан-
ным, что столь оригинальный и столь интересный метод Мер-
лена не способен привести к цели».
Адамар выражал надежду, что метод Мерлена смогут ког-
да-нибудь дополнить. А принцип его во всяком случае должен
быть сохранен. «Я не считаю себя вправе утаить его от тех,
кто интересуется этим видом исследований».
Затем шла сама статья Мерлена с некоторыми мелкими
поправками Адамара.
Основой метода Мерлена явилось «решето Эратосфена».
Пусть А — целое число, ph рг,..., р„ — простые числа, не
превосходящие А, причем pi < рг <... < рп- Известно, что
если выбросить из ряда чисел (1): 1, 2, 3, 4, 5,..., А все числа
вада xpi (где i - 1, 2,..., п, а х — любое целое >. 1), то оста-
нутся все простые числа, < А. Мерлен называет такое реше-
то «решетом Эратосфена с началом 0». Выбросим из того же
1 Comptes rendus de 1’Academie des Sciences de Paris, 1859, . t. 49,
juillet—decembre, p. 624.
66
ряда (1) все числа вида A -f-xp/t где /=1, 2, 3,..., п; х — про-
извольное целое отрицательное число. Это будет «решето
Эратосфена с началом А».
Например, если .4 = 24, то ряд (1) будет
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24.
Числа вида xpi будут (так как Pi = 2, р2=3; р = 5 —не го-
дится, так как 5 >/24):
2, 2-2, 3-2. 4-2, 5-2, 6-2, 7-2, 8-2, 9-2, 10-2, 11-2, 12-2,
т. е. 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24,
а числа хр£ = х-3 будут: 3, 6, 9, 12, 15, 18, 21.
После их вычеркивания останутся числа
1, 5, 7, 11, 13, 17, 19, 23. Это «решето с началом 0».
Теперь рассмотрим «решето с началом А — 24». Числа A -f-
-{-xpi будут: 24 — х-2, 24 — х-3. Можно рассматривать по-
ложительные х и брать числа > А, но заменять их вычетами
по mod Л (pi—те же самые: /ь = 2, р2 = 3).
Тогда надо будет вычеркнуть из ряда (1) числа: 24—2=22,
24-2-2=20, 24-2-3=18, 24-2-4=16, 24—2-5=14,24—
2-6=12, 24—2-7=10, 24-2-8 = 8, 24-2-9 = 6, 24-2-10=4,
24-2-11 = 2, 24-2- 12=0.
Останутся числа 23, 21, 19, 17, 15, 13, 11, 9, 7, 5, 3, 1.
Теперь отсюда вычеркнем числа 24 — х-3, т. е. 24—3 = 21, 24—-
3-2=18, 24-3-3=15, 24-3-4=12, 24-3-5 = 9, 24-4-5=4.
Останутся: 23, 19, 17, 13, 11, 7, 5, 1 —те же числа, что и при
«решете с началом 0». Запишем эти оставшиеся ряды чисел
один под другим: один раз в порядке возрастания, второй —
в порядке убывания:
23 19	17 13	11	75	1
1 5	7 11	13	17 19	23
24 24	24 24	24	24 24	24
Очевидно, что всякое число, оставшееся после вычеркивания,
будет одновременно и вида р, и видаЛ—р' (р пр'—простые),
и, следовательно, представляет собой разложение, существова-
ние которого утверждает теорема Гольдбаха. Суммы по
столбцам все равны 24 (Л=р+р')- То есть 24 раскладывает-
ся на 2 простых числа (если 1 не считать простым) шестью
способами (если учитывать порядок слагаемых) или тремя
способами (если порядок слагаемых не учитывать): 24=17+-
4-7=134-11 = 19 + 5. Можно подобным же образом применять
процесс «решета» не 2, а больше раз.
Затем Мерлен переходит к подсчету количества отброшен-
ных членов ряда (1). Он выясняет, как учесть те числа, кото-
67
рые принадлежат одновременно нескольким предыдущим
прогрессиям, чтобы не считать их несколько раз. Мерлен ис-
пользует в вычислениях асимптотические формулы для
«(*), «(Ж),
Р<л
Он указал также ряд других вопросов, которые могут быть
решены теми же средствами. Можно узнать, бесконечно ли
число пар простых чисел, различающихся между собой лишь
двумя единицами («близнецов»), т. е. рл+i— рп = 2; беско-
нечно ли число пар простых, таких, что р л+i — Рп~ таких,
что рп+2— Pn+i =4 н рп+л — рп *=2 одновременно. Мерлен
предлагал также решить в простых числах неопределенное
уравнение первого порядка
ах + by = с
(а, Ь, с— взаимно простые).
Вслед за работой Мерлена появились в печати исследова-
ния норвежца Виго Бруна (Viggo Brun), Брун усовершенст-
вовал метод Мерлена. Метод Бруна подробно изложен в его
работе «Решето Эратосфена и теорема Гольдбаха» (1920), но
первые заметки были им опубликованы вскоре после появле-
ния работы Мерлена (1915, 1916).
Брун напомнил слова, сказанные Эдмундом Ландау на кон-
грессе математиков в Кембридже в 1912 г., о том, что он счи-
тает проблему Гольдбаха и проблему «близнецов» (о беско-
нечности числа пар простых «близнецов») недоступными для
современного состояния науки. Но, продолжал Брун, после
того как Мерлен указал, что к ним можно применить метод,
аналогичный методу «решета Эратосфена», появилась исход-
ная точка для решения этих задач*. Брун доказал теоремы:
1. Всегда между пип + Уп существует число, количество
простых множителей которого не превосходит И, когда
n>N;
2. Каждая арифметическая прогрессия, первый член и раз-
ность которой взаимно просты, содержит бесконечно мно-
го членов, количество простых множителей в которых не
превосходит 5.
Брун доказал также «ослабленную» гипотезу Гольдбаха:
«Можно записать каждое четное число х, большее хв, как
сумму двух чисел, количество простых множителей которых
не превосохдит 9», и ослабленную теорету о «близнецах»:
«Существует бесконечно много пар чисел, имеющих раз-
1 V. Brun. La crible d’Eratosthene et le theoreme de Goldbach. Vi-
denkapsseisk. Skrift., 1, Mat. - Nat. KI., 1920, № 3, Kristiania, pp. 1— 3t>.
68
несть 2, в. классе чисел, количество простых множителей кото-
рых ве вревосхедит 9» (Бруи, стр. 32}.
С помощью теоремы Чебышева (постулата Бертрана) вы-
водится верхняя граница для количества чисел, которые
остаются невычеркнутыми носле применения методов решета
Эратосфена и Мерлена.
Через несколько лет «решето» привлекло внимание совет-
ских математиков. В. А. Тартаковский, видоизменив метод
Бруна, сумел доказать, что в любой арифметической прогрес-
сии ex-f-b, где (о, b} = 1, до достаточно большого числа z
существует не менее
k----------
<f (в) log г
простых чисел или чисел, имеющих два простых множителя,
заключенных между
±+.	2-2.
Z3 И Z3
(здесь k — постоянная, ф (о) — функция Эйлера, выражаю-
щая количество чисел, взаимно простых с а и не превосходя-
щих а, е — сколь угодно малое, положительное, постоянное).
Работы А. А. Бухштаба внесли новые улучшения в метод
Мерлена — Бруна (1938—1944). В 1941 г. появилась работа
Ю. В. Линника «Большое решето». «Большое решето» позво-
лило высеивать последовательности при помощи простых чи-
сел с возрастающим числом вычетов. Эти работы вызвали ряд
исследований у нас и за рубежом.
Большое влияние на развитие «метода решета» оказала ра-
бота «Об элементарном методе в теории простых» (1947)
соотечественника и ученика Бруна — А. Сельберга. Здесь
решаемся такая задача: имеется последовательность целых
чисел О], а2,..., aN. Требуется найти верхнюю границу для ко-
личества тех чисел ап, которые не делятся ни на какое про-
стое число, не превосходящее г. Применяя свой метод к зада-
че о числе простых-«блиэнецов»„ Сельберг находит, что число
пар простых -«близнецов», не превосходящих х, будет мень-
ше, чем
о
, 10,6х
bg2x
Ленинградец И. В. Чулановский применил метод Сель-
берга к оценке количества простых чисел, не превосходя-
щих х, в арифметической прогрессии km-]-!, где (k, /) = 1,
Другой ленинградский математик А. И. Виноградов связал
решето Сельберга с аналитическим методом и применил к на-
хождению нижней границы количества N (г) тех чисел в по-
следовательности целых а>, о2,..., ал, которые состоят только
69
из простых, больших г. В качестве приложения своего метода
А. И. Виноградов показал, что каждое достаточно большое
четное число М может быть представлено в виде суммы двух
слагаемых: M —	каждое из которых содержит не
больше трех простых сомножителей, включая кратность.
Виго Брун обратил внимание на интересное замечание
Сильвестера (1883), который утверждал, что принцип решета
Эратосфена содержится в логической проблеме перекрытия.
(Об этом писал еще в 1857 г. Смит.) Это позволило использо-
вать метод Бруна также в случаях, не имеющих никакого от-
ношения к простым числам к
В 1963 г. ученик Н. П. Романова Б. В. Левин в
докторской диссертации «Метод решета и его применения»
исследовал различные методы «решета» и дал некоторые их
приложения. Лезин исследовал, сравнил и получил из бдного
общего принципа методы «решета» Бруна, Бухштаба, Сельбер-
га, установил связь элементарного метода доказательства
асимптотического закона распределения простых чисел с ме-
тодом «решета», указал связь метода «решета» с задачами
линейного программирования.
В заключение приведем еще одно применение «решета
Эратосфена» (Пуансо). Пусть р — простое число, (а, р) — 1.
Известно, что а"-1 Е l(modp) —теорема Ферма. Если б—
наименьший .показатель, такой, что а5 = 1 (modp), то говорят,
что а принадлежит показателю б по модулю р. Этот показа-
тель обязательно является делителем р — 1 или равен р—L
Действительно, так как одновременно а3 — 1 (mod р) и б — по
условию— наименьший такой показатель и ар-1Е1 (mod р),
то аСкр-1)—1 (modp), но меньше б он быть не может, следо-
вательно, он = б или б = р — 1. Число g, принадлежащее
показателю б = р—1, называется первообразным корнем по
модулю р. Числа g, g*...gp~l несравнимы по модулю 'р и
образуют приведенную систему вычетов по модулю р.
Понятие первообразного корня было введено Эйлером.
Пуансо указал следующий метод нахождения первообраз-
ных корней (покажем его на примере).
Пусть р = 61. Тогда р — 1 =60.
60 = 2«-3-5, т. е. простые множители числа 60 есть 2, 3, 5.
Требуется найти первообразные корни для этого р. Перво-
образными корнями числа 61 не могут быть ни квадраты, ни
кубы, ни пятые степени. Действительно, так как простые де-
лители числа 60 есть 2, 3, 5, то квадрат числа может стать
сравнимым с единицей (^1) по модулю 61 по меньшей мере
в 30-й степени; кубы сделают это уже в 20-й степени, пятые
степени —уже в 12-й. Таким образом, чтобы иметь первооб-
БРУН. Труды 3-го Всесоюзн. иатем. съезда, т. 4. М., Изд-во АН
СССР, 1959, стр. 131.
70
разные корки числа 61, т. е. >числа, которые »е могут быть,
сравнимы с единицей по 'модулю 60 в степени, меньшей ше-
стидесятой, достаточно исключить из 60 чисел натурального
ряда 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, И, 12, 13, 14, 15,..., 58, 59, 60
нее те, которые являются квадратами, кубами и пятыми сте-
иенями, или, 'вернее, вычеты этих степеней по модулю 61.
Это своеобразное применение метода «решета». Для полу-;
чения первообразных корней для данного простого числа вы-
черкивают квадраты, кубы и т. д., в зависимости от простых
множителей, числа р— 1.
Пуансо сам сравнивает свой метод с обычным методом
отыскания чисел N и взаимно простых с N — методом ре-
шета.
Задача.
1) Найдите все первообразные корни для числа 31.
2) Найдите все первообразные корни для числа 47.
Метод решета использует и академик И. М. Виноградов
при решении проблемы Гольдбаха.
п
Из суммы 2	=5 в методе Виноградова выбрасывают-
У=1
ся слагаемые, индексы v которых кратны pi, рг,..., где р*
наибольшее простое число, У п.
Если обозначить Н = р\ • pt- • -рк, a S2 e2’tbtfa,
п
’<7
где d все делители Н, то при вычеркивании получим
St= _2 еЫлр = ^у.^а,
Vn<p<.n
а — некоторое действительное число.
Суммы S и Sj отличаются друг от друга величиной порядка
О( 1^п). Поэтому далее И. М. Виноградов оперирует с сум-
мой St — более простой.
Метод «решета» играл важную роль и в исследованиях
Л, Г, Шнпрельмана,
Простых чисел
бесконечно много
Прежде всего еще в древности сумели пока-
казать, что простых чд сел, в.натуральном рдде J,.2,.3, 4, 5, 6,
7,8,9, 10, 11, 12, 13, 14, 15. 16, ... бесконечно много. Это
Утверждение впервые было доказано в «Началах» Евклида
следующим образом,
71
Допустим; что простых чисел существует лишь конечное
количество. Обозначим все эти простые числа Pi, р2, .-.i Pk и
составим число N=ptp2 ... рЛ4-1. Это число по предположе-
нию (ибо даже самое большое простое число рк меньше N)'
ие может быть простым. Следовательно, оно должно раскла-
дываться на мнояСители:
PiPtos... рк + 1 — qtqt... qm.
Ни одно из чисел qit q2, ... qm не может совпасть ни с одним
из чисел pi, р2, ..., рк, ибо. в случае qt =рлдолжна была бы р
правая часть равенства
P\Pi •••Рк —	•••?/» = “
делиться на это qi~ps, что невозможно, т. е. qit q2, .,., qm-r
еще какие-то простые числа, хотя мы считали, что их всего k.
Полученное противоречие доказывает теорему.
Аналогичным' образом было впоследствии доказано, что
простых чисел вида 4п+1, 4п—1, 6n+1, 6п—1 и т. д. беско-
нечно много.
Например, покажем, что простых чисел вида 4п— 1 беско-
нечно много. Предположим, что их конечное количество Pi, р2,
р6, .... рк. Составим число т — 4р{р2 — рк— 1. Это число немо-
жет иметь простые множители лишь вида 4п+1, так как
(4/h-f-l) X (4п2+1) = 16П1П2-Н(П1 + п2) + 1—число вида 4п+1,
а не 4п—Г(тоже для любого конечного числа сомножителей
вида 4п +1). Всякое нечетное простое число имеет вид 4п+1
«ли 4п—1. Поэтому среди множителей, входящих в т, должен
быть хоть один множитель вида 4п—1. Это простое число не
совпадает ни с одним из Pi, р2,, рк. Следовательно, это не
рее простые числа вида 4п—1, как было предположено. Полу-
ченное противоречие доказывает теорему.
Доказательство Эйлера (по книге Шнирельмана «Простые
числа»,стр. 45—46):
Эйлер дал другое доказательство теоремы о бесконечности
количества простых чисел в натуральном ряде. Снова предпо-
ложим, что число простых чисел конечно.
Пусть pi, р2, рз. .... рк—все простые числа.
Составим геометрические прогрессии:
Рг
1
РК
.72
Все эти прогрессии—сходящиеся ряды с положительными
членами. Поэтому их можно почленно перемножить и должен
снова получиться сходящийся ряд*:
_2_=У____1__.
Pk
(l)
Суммирование в правой части распространено на все возмож-
ные различные комбинации неотрицательных показателей
ан аг, .... а*. Но по основной теореме арифметики всякое це-
лое число разлагается на простые множители: п=-р^ p/^...р^
и притом единственным образом. Следовательно, сумма спра-
ва содержит все дроби вида — при любых целых положитель-
ных п.
Расположив слагаемые по возрастанию знаменателей
(можно располагать их в любом порядке, так как ряд сходит-
ся по предположению и имеет положительные члены), полу-
чим гармонический ряд:	+— + — +
2	3	4	 п
а его сумма по формуле (1) коиечна и равна
1______1 1
1—L i_-L 1——
Pi Pt ' Pk
Но гармонический ряд расходится (это легко доказывается
в первых лекциях по теории рядов). Получается противорег
чие. Следовательно, предположение о конечности количества
простых чисел неверно.
Для бесконечного числа простых чисел будет справедливо
равенство
1^=2^’>*
Р 1 р, Л=1
(р —все простые).
Это знаменитое тождество Эйлера. В левой части его —
бесконечное произведение. При s>l в правой части стоит схо-
дящийся ряд. При 5=1— расходящийся гармонический ряд.
со 1
Функцию У теперь обозначают £(s) и называют «дзета-
л=1
функция Римана».
Следующим этапом в вопросе об установлении количества
простых чисел было доказательство того, что в любой арифме-
1 Говорят, что ряд at + а» +._ + а„ +... сходится, если существует
конечный iim (а, + аг +... + ап ). Если такого предела не существу-
Л->оо
ет, ряд называется расходящимся.
73
Тической прогрессии ак-^-b, где (а, Ь)=!, существует беско-
нечно много простых чисел. Эту теорему доказал П. Лежеп-
Дирихле, исходя из обобщения тождества Эйлера (2), Тож-
дество Дирихле имеет следующий вад:
К*. х) = П(1~^г
р
В частном случае, например для прогрессии где
-I
(3)
л—1
Х(«)= С-1)
. О
2~
I ДЛЯ
ДЛЯ
нечетных nt
четных п, т, е.
Х(п)=1, если п = 4т-{-1,
—1, если n = 4m-{-3, легко проверить, что x(ffin)=r
=%("0х(«)«
L(s, %) означает
и тождество Дирихле принимает вид
1-4+W+---=n(i-f)(i+^).
Pi, Pl4	' 4	'
где Pi — вида 4m + 1,
pt — вида 4m + 3.
Теорема легко доказывается для частных случаев (простые
вида 4п+1, 4п—1, 6п+1 и т. д.) и сложно для общего случая:
прогрессии вида ax-f-b, (а, 6) = 1. Функция х(п) называется
характером Дирихле, ряд L (s, х) — рядом Дирихле. Большой
вклад в теорию L-рядов внес советский ученый Н. Г, Чуда-
ков.
Затем тождество Эйлера обобщалось и на другие случаи,
Риман использовал тождество для ^-функции, зависящей от
комплексного аргумента а. Идея Римана была применена для
аналитического доказательства асимптотического закона рас-
пределения простых чисел.
Закон распределения
простых чисел
Наряду с вопросом о бесконечности количе-
ства простых чисел в натуральном ряде и в арифметических
прогрессиях математиков издавна занимал вопрос о функции.
74
которая могла бы представить закон распределения простых
чисел (асимптотический закон распределения простых чисел).
Еще Эйлер писал: «Математики тщетно пытались до
сих пор установить некоторый закон в последовательности
простых чисел, и у нас есть основания считать, что это тайна,
в которую человеческий разум никогда не проникнет» *.
При первом взгляде на таблицу простых чисел действи-
тельнс_кажется, что в их расположении нет никакого поряд-
ка. При более тщательном изучении удается подметить неко-
торые особенности: промежутки между последовательными
простыми числами, вообще говоря, возрастают. Как угодно
далеко в таблице встречаются простые «близнецы», разность
между которыми равна 2:
3, 5; 11, 13; 29, 31; 41, 43; ...
В то же время существуют случаи очень больших проме-
жутков между последовательными простыми.
Математикам хотелось также установить правило, которое
позволяло бы решить, является или нет данное число простым.
Несколько таких правил известно. Например, теорема Виль-
сона: для простых чисел п всегда га!-|-1 делится на п, и ее об-
ращение: п — простое чйсло только в том случае, если га! +1
делится на га.
Но для практического решения вопроса о простоте
чисел это правило не годится, ибо определить, делится ли
га! + 1 на га при большом га, не легче, чем разложить само га на
множители. Эйлер хотел дать рекуррентную формулу для вы-
ражения р п через Pi, Pi, .... Pn-i по аналогии с его формулой
для выражения суммы делителей о (га) через о от меньших
чисел:
о (га) =. о (п — 1) + а (га — 2) — а (га — 5) — о (га — 7) 4- а (я—12) +.,
3£2 _ /г
где числа 1, 2, 5, 7, ... вида га — —--пятиугольные числа.
Но, к сожалению, ни Эйлер и никто другой из последующих
поколений математиков не сумел открыть хорошей рекуррент-
ной формулы для рп. До сих пор не доказано также, что су-
ществует бесконечно много пар «близнецов».
Для количества простых чисел, не превосходящих х:
ir(x) = Sl,
₽<*
где р — простые числа,
было выведено несколько асимптотических выражений.
Лежандр дал асимптотическую формулу
к(х)^-—
' '	log X — С
где С 1,08.
» Цнт. по кн.: R. Ayoub. An introduction to the analytic theory
of numbers. Providence (USA), 1963, p. 37.
75
Гаусс предлагая формулу
Обе эти формулы были даны без доказательств.
Можно показать, что простых чисел в бесконечном ряду
натуральных чисел хотя и бесконечное количество, но очень
мало по сравнен ню со всеми натуральными числами;
Ilm2L<±=o.
Л-*«» X
Иногда это выражают словами: «Вероятность того, что наугад
выбранное число — простое, равна нулю». Доказательство
этого факта также использует идею решета Эратосфена.
Важный шаг на пути к доказательству асимптотического
закона распределения простых чисел был сделан в середине
XIX в. ПЛ Л, Чебышевым. Он доказал, что если предея
*-кх> X
•ogx
существует, то его значение должно быть равно единице. Кро-
ме того, Чебышев определил постоянные А я в, для которых
выполняются соотношенм
А—— <*{*)< Я-т-^- или Д<-*(хХ- <Д.
logx	logx	X
log*
Следующий важный шаг был осуществлен Риманом
в 1859 г. Риман в своей единственной теоретико-числовой ра-
боте показал аналитический подкод к Задаче. Но его доказа-
тельство содержало ряд пробелов.
В 1896 г. аналитическим методом было дано доказатель-
ство закона распределения простых чисел одновременно
двумя учеными — Адамаром и Валле-Пуссеном.
Наконец, в 1948—1949 гт. П. Эрдёш и А. Сельберг доказа-
ли закон распределения простых чисел почти элементарно: 6ei
помощи теории функций комплексного переменного, исполь-
зуя из анализа только понятие предела.
Доказательство А. Сельберга и П. Эрдёша состоит из двух
частей, В первой части выводится арифметическое тождество
для функции R(x), равной разности в(х)—х, где 6(х)—функ-
ция Чебышева;
0(х)= 2 log А
₽<*
75
Во второй части авторы на основании этого тождества для
R (л)
R(x) показывают, что  при х-* оо, т. е. что
^.0 или -^-->1.
К х-»<х>	* JM09
От этой формы легко перейти к закону простых чисел в виде
я <*)	ц
X х-*х>
logx
Кстати, и П. Л. Чебышев доказывал все свои теоремы для
функции 0(х), а не для л(х).
После Сельберга и Эрдёша многие математики, в том чис-
ле и советские, совершенствовали это доказательство, приме-
няли метод Сельберга — Эрдёша к доказательству других
утверждений. Кроме того, потребовалось оценить R(x), оста-
точный член в формуле в(х) = x+R(x). Лучшая оценка’была
получена аналитическим методом, но и методом Сельберга —
Эрдёша удалось получить оценку, некогда найденную Адама-
ром и Валле-Пуссеном. Те же задачи решались и для функ-
ции я(х).
Много результатов по теории распределения простых чи-
сел (и их обобщений) принадлежит ташкентским математи-
кам: Н. П. Романову и его многочисленным ученикам.
Н. П. Романов дал ряд интересных работ по теории оператор-
ной 5-функции и операторным методам в теории чисел, развив
методы, идея которых была предложена Л. Г. Шнирель-
маном (1905—1938.),
Сколько целых точек
в плоской фигуре
Лежен-Дирихле впервые вычислил число
целых точе^с, т. е. точек с целочисленными координата-
ми, находящихся в части плоскости, ограниченной верхней
ветвью гиперболы ху = п и осями координат х=0,
(рис. 6). См. Бухштаб, стр. 48—53.
Подсчитаем количество целых точек в этой области. На
каждой ординате число целых точек будет равно :
для х=1 оно равно [п]=п,
[п 1
—- ,
I
«	Г п 1
для х—3 оно равно — I нт, д
77 '
Всего в этой области содержится Г(п) целых точек
*<Л
Здесь х= 1, 2, 3, п. Иными словами, это будет число реше-
ний уравнения ху~п в целых положительных х, у. Но, с кру-
гов стороны, можно показать, что
F(n) = 2 х(х),
х<п
где т (х) — число делителей х,
Рассмотрим уравнение ху—п. Каждый делитель d числа п
является решением этого уравнения, Точно так же его реше-
нием будет и — .
d
Если, наоборот, мы имеем какое-нибудь целое положи-
тельное решение уравнения ху=п; х0, у0, тохо ий будут дву-
мя делителями числа п; x0=d, у*——.Подсчитаем число дели-
d
телей для чисел 1, 2, 3,.... п:
т(1) = 1
т(2)=2, (d,=l; d2 = 2)
i(3) = 2, (d1 = 1; d, = 3)
i(4) = 3, (d,= 1; da = 2; dt = 4)
1(5) = 2, (d, = l; d, = 5)
t(6) = 4, (d, = 1; da = 2; d,=3; d4 = 6)
i(7) = 2, (d,= l; dt — 7)
i(8) = 4, (d, = 1; d, = 2; d, = 4; d4 = 8)
78
Сумма равна общему числу точек с целыми положи-
Кп
тельными координатами, лежащих в области ху^. N, х>0,
У>0.
Число .таких точек мы обозначали F(n). Таким образом,
Лежен-Дирихле показал, что F(n) равно
F(n)=znlogn + (2C— 1)л + 0(/л),
где С —постоянная Эйлера. Для доказательства этого утвер-
ждения Дирихле воспользовался тем, что ввиду симметрии
гиперболы относительно биссектрисы OD координатного угла
число целых точек внутри фигур E\ADM{ и EBDM (исключая
точки на осях) одинаково. Оно равно КДп), где
Л(п)=1][т]-
!<*</«
Число целых точек внутри квадрата OM\DM (исключая точки
на осях) равно
S П/л| = [К5]>.
1<й< Vn
Поэтому общее число целых точек внутри рассматриваемой
области F(n) равно
F(n) = 2
!<»< Vit
(формула Дирихле—Эрмита).
Заменив I— числами—,мы изменим сумму на величину
L k j	k
<2Уп?	_	_	__
Целая часть [Уп] равна У п или меньше У п на величину 6:
[Уп]^Уп-в,
тле О <0 <1,
поэтому
[Уп\* = (У^- 0)’ = п + О (J/7T).
Кроме того, известно, что
^Azziogn + c + o^X),
k<n
тле С — постоянная Эйлера. (Постоянная Эйлера С опреде-
ляется равенством
C = Hm<l + -l. + 4 + ...+ ±_logn).
Л-*- оо	«	<3	П
1^1-
19
Подсчитано, что С=0,577215...). Подставляя значения I
*<*L "J
и [л] в формулу для получаем
F(л) = 2п V-1 - п 4- ° (/л) = 2л (log Vn + C+0(pL))-
— л + О (Уп) = п log л 4- (2С— 1) л 4- О (Уп).
Таким образом, число целых точек в области А выражается
асимптотически формулой
F(n) = п log л 4- (2С—1)п-у О (Уп).
В дальнейшем математики усовершенствовали метод подсчета
целых точек. Г. Ф. Вороной получил вместо О (/”) величину
1
О (п 3	), где е > 0 сколь угодно мало.
Эта же формула дает асимптотическое выражение для
суммы числа делителей
F(n) = 2 т (А) = п logn 4- (2С—1)л 4- О (Уп).
Ь<п
Число целых точек в круге (рис. 7) F (г) выражается форму-
лой
F (г) = w14-0 (г).
Уравнение окружности радиуса г с центром в начале коорди-
нат, как известно, имеет вид х2+</2=г2. Количество целых то-
чек на одной ординате у=±Уп—хг будет равно 2[]/ г* —ла].
Все целые точки в круге получим, просуммировав это количе-
ство по всем целым значениям х от х=—г до х=-\-г или взяв
две суммы для х от 0 до г:
F(r) = 2%2 [У^^Гх*] = 4 5 1
х=0	х=0
Число целых точек в секторе: Fx(r) =[v/ п—хг] равно пло-
щади фигуры, составленной из квадратов, и потому за-
ключено между площадью сектора MON и площадью сектора
M.ON^.
4	4
Отсюда следует, что
F, (г) =-1^4-О (г),
а чиспл всех целых точек в круге равно 4/?1(г):
F(r) = та* 4- О (г).
83
Эта оценка была известна еще Гауссу. Французский матема-
тик III. Эрмит (1822—1901) вычислял число целых точек
в эллипсе. Остаточный член в формуле для числа целых точек
в круге уточнил В. Серпинский и другие математики.
Рассмотрим теперь область, ограниченную кривой У=Цх),
осью Ох и двумя ординатами х—а, х = Ь. Число точек с цело-
численными координатами в этой области (рис. 8) равно F(n),
где
х<Ь
х>а
Здесь опять [/(%)] — целая часть f(x). Мы подсчитываем це-’
лые точки обл(асти, не включая в их число точки на оси Ох и
на прямой х—а.
Действительно, чтобы подсчитать количество целых точек
на одной ординате, надо взять [/ (х)] при данном х. Затем на-
до эти выражения просуммировать по всем х от х=а до х=Ьч
Получается указанное выше выражение F(n).
Обозначим {/(х)} дробную часть f(x). Тогда
Так как обычно сумма S f(x) вычисляется сравнительно
х>а
просто, то вся трудность заключается в вычислении суммы
дробных частей
х<Ъ
х>а
Вычисление таких сумм важно и для других вопросов теории
чисел. Рассматривают подобные суммы для функций специ-
ального вида,например для многочленов (/(х) =д0х'’-|_о1х'»-1+
+ ...4-ая), для показательных функций (f(x) =ах) и др. Оцен-
81
кой сумм вида E(f(x)) занимались Г. Ф. Вороной, В. Серлин-
схий, Г. Харди и Литлвуд, Э, Ландау, И, М. Виноградов,
А. Вальфиш и другие.
В последние годы математики занимались подсчетом чис-
ла целых точек в различных областях пространства: в шаре,
эллипсоиде, гиперболоиде и других областях. Особенно увле-
кались этими вопросами ленинградские математики: акаде-
мик Ю. В. Линник и его ученики А. В. Малышев, Б. Ф; Ску-
бенко и другие,
Теория чисел Пуансо
Существует еще один способ построения
теории чисел, принадлежащий Пуансо. Целью Пуансо было
изложить теорию чисел, пользуясь только понятиями числа и
порядка.
Рассмотрим несколько чисел, расположенных в определен-
ном порядке;.
al, а2,	•••» aN f
и обозначим этими буквами вершины правильного много-
угольника, вписанного в круг (рис. 9).
Если, начиная с одной из точек, например с ах, переходить
от одной точки к другой, беря их последовательно по 2, по 3
или вообще no h точек, и этот постоянный интервал h будет
взаимно прост с N, т. е. (Л, N) = 1, то нужно будет пройти все
точки йь й2, ..., яд-, прежде чем мы снова попадем в исходную
ТОЧКУ й].
Действительно, предположим, что вы прошли часть из
этих N точек или вершин (беря по h точек, где h<N) и обра-
зовали правильный многоугольник с п сторонами. Каждая
сторона этого многоугольника соответствует h последователь-
ным сторонам исходного многоугольника. Обходя контур этого
многоугольника, причем придется обойти один или несколько
раз вокруг окружности, вы сможете, следовательно, сосчитать
число nh точек на пройденном пути. И так как вы по предпо-
ложению вернулись в исходную точку, то вы получите, что это
число nh равно точно кратному числу N точек полной окруж-
ности. Но если (Л, N) = 1, п < N, то произведение nh не можег
делиться на N и, следовательно, не может быть кратным N.
Поэтому, чтобы произведение nh было кратным N, т. е.
nh^qN, необходимо, чтобы n^N, а тогда я q^=h. Отсюда сле-
дует теорема:
Если имеем N точек, расположенных на окружности, и бу-
дем соединять их по Л точек, где (Л, #)»=!, то придется
82
пройти все N точек для того, чтобы попасть в исходную точку,
и при этом необходимо сделать h оборотов (Л раз обходам
полную окружность).
Обратно, соединяя М точек по h точек, пройдем через все
эти точки, пока придем в исходную точку, если (ft, /V) = 1. Дей-
ствительно, тогда h не сможет точно делить кратное N, кото-
рое будет меньше, чем hN, и, следовательно, наибольший дели-
тель Л, который может делить N, будет или 1; следова-
тельно, h и N будут взаимно простыми.
Если, таким образом, соединяя несколько точек через ка-
кие угодно равные интервалы, сможем вернуться к первой,
только пройдя через все другие точки, то можно утверждать,
что число этих точек — простое. Это дает род геометрического
определения простого числа.
Поясним это рассуждение примерами.
Пример 1 (рис. 10).
Возьмем на окружности 9 точек: W=9. Будем переходить
от одной точки к другой, проходя по две дуги. Получим после-
довательность точек: а{, as, а5, аъ ав, а2, ait ав, а8. Номера то-
чек пробегают полную систему вычетов по mod 9. Нам при-
шлось пройти все девять точек, чтобы снова попасть в исход-
ную точку at. Здесь ft=2. Мы 2 раза обошли окружность. При
этом мы прошли 18 точек, т. е. Лп=18; 2-п = 9-2 = 18; (2,9) = L
Пример 2 (рис. 11).
Пусть <V = 5.
Будем добавлять по 3 точки (или по 3 дуги). at, ait a2t as,
as, ah Номера точек будут: 1, 4, 7^2 (mod 5); 10=5
(mod 5); 13^3 (mod 5); 16 s 1 (mod 5), т. e. номера точек
пробегают все вычеты по модулю 5:
1, 4, 2, 0, 3, 1.
Здесь ft=3, N=5, (3, 5) = 1. Чтобы снова попасть в исходную
83
точку, нам пришлось пройти 15 точек (3 раза обойти окруж-
ность),
Пример 3 (рис. 12).
Пусть теперь Л/ = 10, Л=2. (N, h)=2. Последовательность
точек будет: аь а3, а5, а7, аь а8, а5, а7, а,, аь Каждое нечет-
ное число от 1 до 10 встретится 2 раза при двойном обходе
10 е
окружности; — =5 — возвращаемся впервые в исходную точ-
Ля
ку на 5-й точке. Число обходов равно L
Рис. 12
Теорема.
Если ft и не являются взаимно простыми между собой,
/у
то, соединяя N точек через й точек, пройдем только через —
л
из них, где d — наибольший общий делитель двух чисел й и N
(в нашем последнем примере d=(10, 2) =2,-^ =5).
а
Доказательство. Будем откладывать дугу й на окружно-
сти, пока не придем к исходной точке (это обязательно про-
изойдет самое большее через h полных обходов окружности).
Мы сделаем, таким образом, некоторое число q обходов во-
круг окружности и получим число qN, которое должно де-
литься на число h. Следовательно, наибольший делитель й,
который может делить jV, будет — и, следовательно, — будет
Я	Я
равно наибольшему общему делителю й и 2V,
Таким образом, будем иметь
—— d или q = —.
Я	Л
Но, если обозначить через х число сторон многоугольника,
который будет образован, и это число х будет обозначать так-
же число вершин или точек, через которые мы пройдем, полу-
64
чим, очевидно, произведение xh, равное кратному qN чмеяж
точек полных окружностей N. Это даёт ( так как q= —\
\	d J
Nh	N
xh = —и, следовательно, х= — ,
d	d
Таким образом, пройдем только через число х точек, где
и сделаем полный обход окружности q раз, где q= —,
d
что и
требовалось доказать.
Если общий наибольший делитель h nN равен 1, эти числа
взаимно простые. Тогда x—N, q=ht Отсюда как следствие
получается первая теорема.
Можно заметить, что это доказательство не предполагает
никаких свойств чисел и никаких теорем арифметики, даже
алгоритма отыскания общего наибольшего делителя Евклида.
Она может дать поэтому при необходимости новое правило
для отыскания общего наибольшего делителя.
Другое правило нахождения общего
наибольшего делителя двух чисел (Пуансо)
Разделив число В на А, получим некоторое частное mi и
остаток fir
В = Атг 4- fj.
Добавим делимоеВ ненова будем делить на Л.Если 2В = Л,то
делит В. Это и есть их ОНД. Если А не делит 2В, делим
2В на А:
2В = Ата 4- г»
ЗВ = Ат,-]-г,
А Л Л Л Л
зе-вл
Рис. 13
пВ = Ат„,
пока не получим г„ = 0.
Тогда — будет общим наибольшим
п
делителем Л и В. (Практически процесс
этот менее удобен, чем обычный
алгоритм Евклида.) Изложим тот же
процесс геометрически.
Берем прямую, отложим на ней
последовательно отрезки, равные одно-
му (В) из двух данных отрезков Л и В. Затем будем откла-
дывать другой отрезок А, исходя из какой-нибудь точки деле-
ния, пока не попадаем в другую точку деления; если это про<
изойдет после того, как отложена длина тВ, то — будет
• т
Общей мерой отрезков А и В (рис. 13).
85
Таким образом, ЗЛ='5В; -у делит В, т. е. числа А, В имеют
онд = у.
Можно вЗять окружность. Число В будет соответст-
вовать В последовательным точкам на окружности, представ-
ляющим вершины правильного многоугольника с В сторона-
ми. Исходя из какой-либо из этих точек, будем соединять точ-
ки через А сторон, пока не придем в исходную точку. Для это-
го надо было обойти окружность т раз. Получим наимень-
шее кратное тВ, которое будет делиться на величину А. Сле-
довательно, будем иметь —• в качестве общего наибольшего
т
делителя А и В.
Таким образом, чтобы найти ОНД, надо только сосчитать,
сколько раз при этом пришлось обойти окружность (рис. 14,
Рис. 14	Рис. 15
Отсюда получаются и другие теоремы теории чисел.
Пусть опять N точек правильно расположено на окруж-
ности (вершины правильного W-угольника), взяты они в опре-
деленном порядке.
Если переходим от одной точки к другой через а точек, где
a<N и (а, М) = 1, то придется пройти через все остальные и,
таким образом, снова получится правильный W-уголь-
ник.
Если в этом новом многоугольнике мы будем переходить
от одной точки к другой через р точек, где (р, N) = 1, то полу-
чится третий /V-угольник.
Таким образом, беря сначала по а тачек, а потом в новом
многоугольнике по р точек, в результате получим то же, как
если бы брали сразу по ар точек в первом многоугольнике.-
Так как, беря точки по ар, пройдем все N точек, то, следова-
тельно, (ар, N) = 1.
86
Имеем следующий фундаментальный принцип теории чи-
сел. Если два числа аир взаимно просты с N, то их произве-
дение ар тоже взаимно просто с Л/.
Отсюда как следствие получается теорема о том, что лю-
бое число N может быть разложено на простые множители
единственным образом.
Таким образом можно доказать теорему Эйлера:
х № = 1 (mod N), где <р (W) — функция Эйлера, а (х, N) — l
и другие теоремы теория чисел. Пуансо предлагал излагать
на этой основе теорию вычетов, решение неопределенных
уравнений и вообще всю теорию чисел,
КРАТКИЕ БИОГРАФИЧЕСКИЕ СВЕДЕНИЯ
О МАТЕМАТИКАХ
Брун Виго (род. в 1885 г.) — норвежский математик. Профессор
математики в Трондхейме (с 1924 г.), в Осло (1946—1956). Член Норвеж*
скрй академии наук и ряда иностранных обществ и академий. Основное
направление научных занятий — теория чисел. Им разработан пользую*
щийся широкой известностью «метод решета Бруна».
Бугаев Николай Васильевич (1837—1903) —профессор Московского
университета. Один из основателей Московского математического общества
и журнала «Математический сборник» (существует свыше 100 лет). Основ*
иые направления исследований: теория чисел, теория сходимости рядов!
приближенное интегрирование, теория дифференциальных уравнений.
Буняковский Виктор Яковлевич (1804—1889) — петербургский ма«
тематик. Учился в Париже, вице-президент Петербургской академии наук
(с 1864 г.). Преподавал некоторое время в Петербургском университете
и в Морском корпусе. Основные работы — по теории вероятностей, теории
чисел, интегрированию алгебраических функций, математической статисти*
ке. Написал «Лексикон чистой и прикладной математики» (1839) —словарь
математических терминов. Участвовал в издании сочинений Л. Эйлера по
теории чисел (1849),
Венков Борис Алексеевич (1900—1962)—воспитанник Ленинград*
ского университета, в дальнейшем профессор. Работал также в Матема*
тическом институте АН СССР им. В. А. Стеклова и в различных вузах.
Основные направления работ: теория квадратичных форм, геометрическая
теория чисел. Ему принадлежит прекрасный курс теории чисел «Элемен*
тарная теория чисел», где подробно освещены вопросы теории чисел, не
связанные с применением математического анализа, геометрии чисел и
целых алгебраических чисел.
Виноградов Иван Матвеевич (род.в 1891). Окончил Петроградский
университет в 1914 г., академик (1929). Герой Социалистического Труда.
В 1918—1920 гг. работал в Пермском университете, в 1920—1934 гг.— в
Ленинградском университете и Политехническом институте. С 1932 г. за-
ведовал математическим отделом Физико-математического института,
с 1934 г.— директор Математического института АН СССР. Основное на-
правление исследований — теория чисел. У И. М. Виноградова много уче-
ников, ставших к настоящему времени известными математиками. Средн
них профессора Н. М. Коробов, А. Г. Постников и другие. Метод триго*
неметрических сумм Виноградова оказал большое влияние на дальнейшее
развитие исследований по теории чисел в нашей стране и за рубежом.
И. М. Виноградов — член Лондонского королевского общества, член-коррес*
пондент Парижской АП, член-корреспондент Берлинской АН и многих
других иностранных академий и обществ. И. М. Виноградов продолжает
традиции петербургской школы.
Вороной Георгий Феодось.евич (1868—1908) — воспитанник Петер-
бургского университета, профессор Варшавского университета, член-кор-
респондент Петербургской академии паук. Основатель (наряду с немец-
ким математиком Г. Минковским) геометрической теории чисел. Основные
88
ебласти исследований: теория квадратичных форм, геометрия чисел, анали-
тическая теория чисел. Непосредственным учеником его является В. Сер-
пинский. Исследования Вороного развивали И. М. Виноградов, Б. А. Вен-
ков, Б. Н. Делоне и другие.
Гаусс Карл Фридрих (177?—1855) немецкий математик, астроном и
геодезист, еще девятнадцатилетним студентом открыл новые виды пра-
вильных многоугольников, которые можно было строить с помощью цирку-
ля и линейки. Это открытие являлось следствием теории, изложенной Га-
уссом в большом труде «Disqufpitioncs arithmeticae» (1801). Научная дея-
тельность Гаусса очень многогранна. Наряду с фундаментальными трудами
по теории чисел Гауссу принадлежат исследования в различных отделах
математики, механики, астрономии, геометрии, оптики, теории электриче-
ства и т. д. Окончил Геттингенский университет, с 1807 г. занимал кафедру
математики и астрономии в Геттингенском университете и был директо-
ром Геттингенской астрономической обсерватории. Первой крупной рабо-
той Гаусса был его фундаментальный трактат по теории чисел «Арифме-
тические исследования». Гаусс — один из создателей современной теории
чисел.
Гельфонд Александр Осипович (1906—1968), окончил Москов-
ский университет. Член-корреспондент АН СССР. Профессор Московского
университета. Основные направления исследований — теория чисел (транс-
цендентные и алгебраические числа, распределение дробных долей функ-
ций), теория целых аналитических функций, теория интерполяции и тео-
рия конечных разностей, вопросы аналитической теории чисел и др. В 1934 г.
он решил знаменитую 7-ю проблему Гильберта.
Граве Дмитрий Александрович (1863—1939), окончил Петербургский
университет. Ученик А. Н. Коркина. Профессор Киевского университета,
почетный член АН СССР. Создал советскую алгебраическую школу. Основ-
ные направления работы: теория дифференциальных уравнений, в част-
ности математическая теория географических карт, теория алгебраических
чисел, теория чисел, алгебра (теория групп), механика. Его учениками яв-
ляются Б. Н. Делоне, Н. Г. Чеботарев, О. Ю. Шмидт и другие.
Делоне Борис Николаевич (род. в 1890 г.) окончил Киевский уни-
верситет. Профессор Ленинградского университета (1922—1935). С 1932 г.
работал в Физико-математическом институте АН СССР (в дальнейшем —
в Математическом институте АН СССР) и-с 1935 г.— в Московском уни-
верситете. Член-корреспондент АН СССР. Основные направления работы:
теория чисел (решение неопределенных уравнений, квадратичные формы,
геометрическая теория чисел), геометрия, в частности геометрия теории
Галуа, геометрия Лобачевского, многогранники, кристаллография, алгебра.
Во всех этих областях у Б. Н. Делоне много выдающихся учеников (среди
них И. Р. Шафаревич, Д. К. Фаддеев и др.). Делоне принадлежат также ис-
следования по истории математики, среди которых книга «Петербурюкая
школа теории чисел» (1947). В своих исследованиях Делоне является
продолжателем традиций петербургской школы теории чисел.
Золотарев Егор Иванович (1847—1878)—представитель петербург-
ской математической школы. Ученик П. Л. Чебышева и А. И. Коркина по
Петербургскому университету. Погиб на 32-м году жизни от несчастного
случая. Исключительные способности Золотарева позволили ему в тече-
ние десяти лет его научной деятельности получить выдающиеся результаты
в области теории делимости целых алгебраических чисел, в теории прибли-
жения функций и в интегрировании алгебраических функций. Большим
вкладом в теорию квадратичных форм явились совместнее работы
А. Н Коркина и Е. И. Золотарева о минимумах квадратичных .форм.
89
. И -Золотаре» был Црофгсеором Петербургского университета и а^ымд-
тем Плгербуугаюй академии наук.
Иваной Иван Иванович (1862—1939)—член-корреспондект - АН
СССР, заслуженный деятель науки РСФСР, профессор Ленинградского
политехнического института. Окончил Петербургский университет в 1886 г.
Основные области исследований — тебрня чисел, интегральное исчисление,
дифференциальные уравнения.
Коркин Александр Николаевич (1837—1908), происходивший из
Крестьян Вологодской губернии, около пятидесяти лет был профессором
Петербургского университета. Учевяк П. Л. Чебышева, представитель пе-
тербургской математической школы. Основные направления исследований —
Теория чисел, дифференциальные уравнения, математическая физика. Кро-
ме университета, А. Н. Коркин преподавал свыше 30 лет в Морской ака-
демик. У Коркина очень много учеников. Средн них академики Е. И. Золо-
тарев, А. А. Марков, А. М. Ляпунов, А. Н. .Крылов, почетные академики
К- А. Поссе и Д. А. Граве, члены-кор респонденты АН СССР И, И. Иванов,
Н. М. Гюнтер, Г. Ф. Вороной и многие другие.
Лагранж Жозеф (1736—1813) родился в Турине. Увлекался древ*
ней историей и математикой. В 19 лет он уже преподавал в артиллерий-
ской школе в Турине. После отъезда Эйлера в Петербург занял его место
в Берлинской академии наук. Оттуда в 1787 г. переехал в Париж, где ос-
тавался все последующие годы. Известен своими выдающимися трудами
р области математики (математический анализ, дифференциальные урав-
нения, вариационное исчисление, математическая физика, теория чисел
уравнения в конечных разностях и т. д.) и механики. Лагранж препода-
вал в Нормальной и Политехнической школах.
Лежандр Адриен Мари (1752—1833)—французский математик,
Плен Парижской академии наук. Основные области исследований: матема-
тический анализ, эллиптические функции и эйлеровы интегралы, теория чи-
сел, вариационное исчисление, геометрия и др. Написал первый системати-
ческий курс теория чисел.
Лежен-Дирихле Петер Густав (1805—1859), родился в Германии. Учил-
ся сначала на родине, потом в Париже. Профессор Берлинского, а затем
Геттингенского университета. Основные интересы: математический анализ,
математическая физика, теория чисел. Лежен-Днрихле развил идеи Эйлера
в области аналитической теории чисел, Гаусса, Лагранжа и- Эйлера в обла-
сти алгебраической теории чисел. В области математической физики Ди-
рихле является воспитанником французской школы Фурье.
.Линник Юрий Владимирович (род. в 1915 г.), окончил Ленинград*
ский университет в 1938 г. Доктор физико-математических наук и профес-
сор с 1940 г. Профессор Ленинградского университета, сотрудник Ленин-
градского отделения Математического института АН СССР. Академик. Ос-
новные направления исследований — теория чисел, теория вероятностей и
математическая статистика. У Ю. В. Линника много учеников (среди них
А. В. Малышев, А. И. Виноградов и другие).
Марков Андрей Андреевич (1856—1922), академик, воспитанник Пе-
тербургского университета. Представитель петербургской математической
школы, ученик П. Л. Чебышева, А. Н. Коркина и Е. И. Золотарева. Основ-
ные направления исследований: теория квадратичных форм, теория вероя г-
ностей, теория конечных разностей. Много лег А. А. Марков был профес-
»
сором Петербургского-Петроградского университета. А. А. Марков —чело-
век большого гражданского мужества. Так, Маркоз потребовал, чтобы
синод отлучил его от церкви, в знак протеста против реакционных мер
царского правительства.
Пуансо Луи — французский математик (1777—1859). В 1797 г.
окончил Политехническую школу в Париже, затем преподавал там меха-
нику и математический анализ. Позднее был профессором в Лицее Бона-
парта. Член Парижской академии наук. Основные направления исследова-
ний: геометрия, механика, теория чисел и алгебра. Наибольшей известно-
стью пользуются его труды по статике.
Сельберг Атле — норвежский математик, ученик В. Бруна (род. в
1917 гЛ. Окончил университет в Осло. Профессор. В настоящее время жи-
вет в США. Сельберг вырос в семье математиков. Его отец., Оле Сельберг
(1877—1950), был профессором математики в Осло, братья Генрих-Люд-
виг (род. в 1906 г.) и Зигмунд (род. в 1910 г.)—также профессора мате-
матики. Брат Арне — (близнец Зигмунда)— инженер.
Сельбергу принадлежит более тридцати работ по теории чисел и мате-
матическому анализу. А, Сельберг совместно с П. Эрдёшом впервые сумел
найти доказательство закона распределения простых чисел, не использую-
щее средств теории функций комплексного переменного. Ему принадлежит
также усовершенствованный метод решета — «решето Сельберга». Он яв-
ляется членом многих академий и научных обществ,
Серпинский Вацлав (род. в 1882 г.)—польский математик. Уче-
ник Г. Ф. Вороного по Варшавскому университету. Профессор Варшавско-
го университета, академик Польской академии наук. Основные исследова-
ния — по теории чисел, теории множеств, топологии, теории функций дей-
ствительного переменного, функциональному анализу и другим разделам
математики. Серпинский член многих иностранных академий и обществ.
Сохоцкий Юлиан Васильевич (1842—1929), уроженец Варшавы.
Окончил Петербургский университет. В дальнейшем преподавал и был про-
фессором того же университета. Основные работы — по теории функций
комплексного переменного, интегрированию, теории делимости целых алге-
браических чисел, алгебре.
Чебышев Пафнутий Львович (1821—1894) —сын помещика Ка-
лужской губернии. Окончил Московский университет и с 1847 г. препода-
вал в Петербургском университете (до 1882 г.), где был профессором. Ака-
демик, иностранный член Парижской академии наук. С Чебышевым связа-
но создание петербургской математической школы. П. Л. Чебышев приоб-
рел известность своими работами по теории чисел. Впоследствии он зани-
мался исследованиями в различных областях математики и механики.
Наиболее известны его труды по теории приближения функций, по интег-
рированию алгебраических функций, теории вероятностей, теории механиз-
мов. Чебышев и его ученики прославили русскую науку и оказали сильное
влияние на математиков России и других стран.
Чудаков Николай Григорьевич (род. в 1904 г.), окончил Московский
университет. Профессор. Много лет преподавал в Саратовском государст-
венном университете. Сейчас работает в Ленинградском отделении Мате-
матического института АН СССР нм. В. А. Стеклова. Основное направле-
ние научных исследований: теория чисел. Большей вклад внес Чудаков
Р теорию L-рядов и L-функцнй Дирихле.
91
Шяирельмая Лев Генрихович (1905—1938), окончил Московский
университет. Профессор, член-корреспондент АН СССР с 1933 г. В 1934—
1938 гг. работал в Математическом институте АН СССР им. В. А. Стеклоц
ва. Основные направления научных исследований: топологические методы
вариационного исчисления, теория чисел. Шнирельман оставил выдающиеся
результаты и ряд глубоких идей в разных областях математики.
Эйлер Леонард (1707—1783) родился в Базеле (Швейцария). Учил-
ся у знаменитого математика Иоганна Бернулли (1667—1748). В 1727 г.
приехал в Россию, где уже находились сыновья И. Бернулли — Даниил и
Николай. С 1731 г.—член созданной в 1725 г. Петербургской академии наук.
Годы с 1741 по 1766 провел в Берлине, продолжая поддерживать научные
связи с Петербургской академией. В 1766 г. вернулся в Петербург, где
скончался в 1783 г. Эйлер оставил громадное печатное (свыше 850 опуб-
ликованных работ) и рукописное наследие и заложил основы многих на-
правлений в математике, механике, физике и других областях науки,
С 1911 г. в Швейцарии издается полное собрание его сочинений Opera
omnia. До настоящего времени выпущены 3 серии этого издания в количе-
стве 72 томов большого формата. Планируется издание 4-й серии, куда
будут включены записные книжки и переписка Эйлера. Основная часть ру-
кописного наследия Эйлера хранится в архиве АН СССР в Ленинграде,
А-
СОВЕТУЕМ ПРОЧИТАЛ»
Шнирельман Л. Г. Простые числа. М.—Л., Гостехиздат, 1940.
Хинчин А. Я. Великая теорема Ферма. М.—Л., Гос. техн.-теореТ, изд-
во, 1934.
Хинчин А. Я. Цепные дроби. М., Физматгиз, 1961.
Берман Г. Н. Число и наука о нем. М., Физматгиз, 1960.
Серпинский Б. Пифагоровы треугольники. М., Учпедгиз, 1959.
Серпинский В. Что мы знаем и чего не знаем о простых числах. М,—
Л., Физматгиз, 1963.
Серпинский В. О решении уравнений в целых числах. М., Физматгиз,
1961.
Депман И. Я- История арифметики. М., «Просвещение», 1965.
Делоне Б. Н, Петербургская школа теории чисел. М., Изд-во АН
СССР, 1947.
Матвиевская Г. П. Учение о числе на средневековом Ближнем и Сред-
нем Востоке. Ташкент, «Фан», 1967.
Прудников В. Е. В. Я. Буияковский—ученый и педагог. М., Учпедгиз,
1954.
Прудников В. Е. П. Л. Чебышев — ученый и педагог. М., «Просвеще-
ние», 1964.
Юшкевич А. П. История математики в России. М., «Наука», 1968.
Учебники
Наиболее доступен и снабжен краткими историческими комментария-
ми курс Бухштаба. Бухштаб А. А. Теория чисел. М., «Просвещение», 1966.
Виноградов И. М. Основы теории чисел. М., «Наука», 1965.
Венков Б. А. Элементарная теория чисел, М,—Л., 1937 (здесь-«эле-
ментарная» совсем не означает «простая»).
О ЧЕМ РАССКАЗЫВАЕТСЯ В ЭТОЙ КНИГЕ
Предисловие	. » 3
Что такое теория чисел?.............» . 4
Основные применения теории чисел .... 8
Из истории теории чисел ...... 8
Вклад русских математиков в теорию чисел . 23
Элементы теории чисел................ . 37
Аддитивные задачи теории чисел .... 54
Решето Эратосфена.......................  58
Простых чисел бесконечно много .... 71
Закон распределения простых чисел .... 74
Сколько целых точек в плоской фигуре ... 77
Теория чисел Пуансо ....... 82
Краткие биографические сведения о математиках 88
Советуем прочитать ........	93
Елена Петровна ОЖИГОВА
ЧТО ТАКОЕ ТЕОРИЯ ЧИСЕЛ
Редактор В. С. Захаров
Обложка П. Г. Цепелинскоео
Художественный редактор Т. И. Добровольнова
Технический редактор Л. А. Муравьева
Корректор А. А. Пузакова
А 04511 Сдано в набор 10.VI.69 V. Подл, к печ. 3.111.70 г.
Формат бумага бОХЭОУы. Бум. тип. № 1 Бум. л. 3.0.
Печ. л. 6.0.	Уч.-изд. л. 5.39
Тираж 45 000 экз. Заказ 1526. Цена 19 коп.
Издательство «Знание». Москва. Центр. Новая пл., д. 3/4.
Набрано в типография, пр. Сапунова. 2.
Отпечатано в типографии нз-ва «Знание».
Москва, Центр, Новая пл., д, 3/4.
Заказ 1219L
Уважаемые читатели!
Интересующимся естественными науками (ма-
тематикой, физикой, астрономией, биологией, меди-
циной и др.) издательство «Знание» предлагает
серию книг, выходящих по «Естественно-
научному факультету».
В 1970 году уже выщла книга С. Владими-
ров, М. Карев. Информация и мы.
Кроме того, намечено выпустить:
АЛЯКРИНСКИЙ Б. С. О таланте и способностях (Пси-
хологические очерки).
ГОРСТКО А. Б. Поиски правильных решений (О принци-
пах рациональной деятельности человека).
ИГНАЦИУС Г. И. Теория поля (Математический анализ
функций нескольких переменных).
МИРОШНИЧЕНКО Л. И. Солнце и космические лучи.
НИГМАТУЛИН И. Н. Современные ядерные реакторы.
ЭЙДЕЛЬМАН 3. М. Познание тайны зеленого растения
(К 200-летию учения о фотосинтезе).
Для того чтобы получить указанные книги, вам следует
обратиться в местный книготорг и сделать заказ по темати-
ческому плану издательства «Знание» на 1970 год (№№ с 162
по 167),
Издательство «Знание»
ЧТО ТАКОЕ
ТЕОРИЯ ЕЛ ОЖИГОВА
ЧИСЕЛ