10] ПРОСТЫЕ ЧИСЛА 35

простых. Пусть простые в (Ь) перенумерованы: qi q2 начиная с qi = 3, Рассмотрим число TV, определенное равенством

N = 4{qiq2...qn)-1

Это число также имеет вид Ax - l. Каждый простой множитель TV не может иметь вид 4j; + 1, потому что произведение чисел вида Ах + 1 само является числом такого же вида:

{4х + 1){4у + 1) = 4:{4ху + х + у) + 1.

Значит, число TV имеет простой множитель вида Ах - 1. Этот множитель не может равняться ни одному из чисел qi q2 ..., qn ибо при делении на каждое из них число TV дает остаток - 1. Значит в ряду (Ь) найдется простое число, отличное от qi 5 • • • 5 Qn- Этим высказанное утверждение доказано. Проведенное рассуждение неприменимо для доказательства бесконечности простых в ряду (а), ибо число вида 4; + 1 может не иметь ни одного простого множителя такого вида. Однако для доказательства этого можно воспользоваться другим методом. Обозначим простые ряда (а) через ri, г2, ... и рассмотрим число

М= (г1г2...Г)2 + 1.

Позднее (П1, 3) мы увидим, что любое число вида + 1 имеет простой множитель вида Ax + l (число + 1 полностью состоит из множителей вида 4; +1 и, быть может, множителя 2). Число Tlf, очевидно, не делится ни на одно из простых ri, г2, ..., Гп] отсюда, как и раньше, следует, что прогрессия (а) содержит бесконечно много простых чисел.

Аналогичная ситуация возникает при рассмотрении прогрессий вида 6j; + 1 и 6j; - 1. Эти прогрессии включают все числа, не деляш;иеся на 2 или на 3, и поэтому каждое простое, большее 3, входит в одну из этих прогрессий. Методами, аналогичными только что использованным приемам, можно доказать бесконечность простых в каждой из этих прогрессий. Но такими методами нельзя решить вопрос об обш;ей арифметической прогрессии. Эта прогрессия состоит из всех чисел ах + Ь, где а и b фиксированы, а = О, 1, 2, ..., т. е. из чисел вида

Ь, Ь + а, Ь + 2а, ... Если а и Ь имеют обш;ий множитель, то каждый член прогрес-

СИИ имеет такой же множитель и, значит, не является простым (за исключением, быть может, первого числа Ь). Поэтому нужно предположить, что а и b взаимно простые. Кажется правдоподобным, что такая прогрессия будет содержать бесконечно много простых, т. е. что если а и b взаимно просты, то существует бесконечно много простых вида ах + Ь.

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

О представимости простых другими выражениями известно мало. Предполагается, например, что имеется бесконечно много простых вида j; + 1; вот несколько первых из них:

2, 5, 17, 37, 101, 197, 257, ... Но в доказательстве этого утверждения не было достигнуто ни малейшего успеха, и вопрос этот до сих пор остается безнадежно трудным. Дирихле доказал тем не менее, что любая квадратичная форма от двух переменных, т. е. любая форма вида ах + Ьху + су, в которой коэффициенты а, Ь, с взаимно просты, представляет бесконечно много простых.

В более позднее время был глубоко исследован вопрос о том, как часто встречаются простые, т. е. вопрос о том, сколько простых имеется в ряду целых чисел 1, 2, ..., X при большом X. Это число, зависяш;ее, конечно, от X, обозначается обычно через 7г(Х), Первая гипотеза о величине 7г(Х) как функции от X, по-видимому, была сделана независимо Лежандром и Гауссом около 1800 года. Она состояла в том, что 7г(Х) примерно равно Х/\пХ, Здесь 1пХ обозначает натуральный (так называемый неперов) логарифм X, т. е. логарифм X по основанию е. Это

10] ПРОСТЫЕ ЧИСЛА 37

предположение было, вероятно, основано на вычислениях. Например, при X = 1000 000 найдено, что (1000 000) = 78 498, в то время как величина Х/ЫХ (округленная до ближайшего целого) равна 72 382, их отношение равно 1,084... . Вычисления такого рода могут, конечно, ввести в заблуждение. Но здесь предполагаемый результат оказался верен в том смысле, что отношение 7г(Х) и Х/ЫХ стремится к 1 при X, стремяш;емся к бесконечности. Это составляет содержание известного асимптотического закона распределения простых чисел, впервые независимо доказанного Адамаром и Валле-Нуссеном в 1896 году с помош;ью новых и сильных аналитических методов.

Здесь невозможно перечислить многие другие теоремы, связанные с распределением простых. Теоремы, доказанные в девятнадцатом столетии, являются лишь несовершенными приближениями к асимптотическому закону; результаты, полученные в двадцатом веке, включают различные усовершенствования этой теоремы. Имеется, однако, один недавний результат, о котором следует упомянуть. Мы уже говорили, что доказательство теоремы Дирихле о простых в арифметических прогрессиях и доказательство асимптотического закона были аналитическими и использовали внешние по отношению к теории чисел методы. Сами же утверждения относятся непосредственно к натуральным числам, и казалось разумным искать доказательства, не используюш;ие чуждых теории чисел идей. Поиски элементарных доказательств этих двух теорем были безуспешными до самого последнего времени. В 1948 году А. Сель-берг нашел первое элементарное доказательство теоремы Дирихле, а затем с помош;ью П. Эрдеша он нашел и первое элементарное доказательство асимптотического закона распределения простых чисел. Под «элементарным» доказательством здесь подразумевается доказательство, которое оперирует только с натуральными числами. Такое доказательство не обязательно просто; оба этих доказательства весьма трудны.

Упомянем еш;е об одной известной проблеме, связанной с простыми, которая была предложена Гольдбахом в письме к Эйлеру в 1742 году. Гольдбах предположил (в несколько других терминах), что всякое четное число, большее 6, представляется как сумма двух простых, отличных от 2, например