В. СЕРПИНСКИЙ
что мы
ЗНАЕМ
ЧЕГО НЕ
ЗНАЕМ
ПРОСТЫХ
ЧИСЛАХ

WACLAW SIERPINSKI
CO WIEMY,
A CZEGO NIE WIEMY
О LICZBACH PIERWSZYCH
WARSZAWA
PANSTVVOWE ZAKLADY WVDAWNICTW SZKOLNVCH

В. СЕРПИНСКИЙ
ЧТО МЫ ЗНАЕМ
И ЧЕГО НЕ ЗНАЕМ
О ПРОСТЫХ ЧИСЛАХ
Перевод с польского
И. Г. МЕЛЬНИКОВА
ГОСУДАРСТВЕННОЕ ИЗДАТЕЛЬСТВО
ФИЗИКО-МАТЕМАТИЧЕСКОМ ЛИТЕРАТУРЫ
МОСКВА. 1963 • ЛЕНИНГРАД

517-1
С 33
АННОТАЦИЯ
В книге выдающегося польского математика
Вацлава Серпинского собраны наиболее важные,
интересные и доступные широкому кругу чита-
читателей результаты, относящиеся к теории простых
чисел. Приводятся многочисленные указания на
нерешенные проблемы.
Доказательства теорем даются лишь в тех
случаях, когда они элементарны и не очень уто-
утомительны. В основном книга имеет информаци-
информационный характер. Она может быть использована
учащимися старших классов средней школы, имею-
имеющими склонность к математике, студентами
и учителями. Последние найдут в этой книге
большой материал пля занятий математического
кружка.

517. 1
С 33
АННОТАЦИЯ
В книге выдающегося польского математика
Вгщлава Серпинского собраиьт наиболее важные,
интересные и доступные широкому кругу чита-
читателей результаты, относящиеся к теории простых
чисел. Приводятся многочисленные указания на
нерешенные проблемы.
Доказательства теорем даются лишь в тех
случаях, когда они элементарны и не очень уто-
утомительны. В основном книга имеет информаци-
информационный характер. Она может быть использована
учащимися старших классов средней школы, имею-
имеющими склонность к математике, студентами
и учителями. Последние найдут в этой книге
большой материал пля занятий математического
кружка.

ВАЦЛАВ СЕРПИНСКИЙ
(К восьмидесятилетию со дня рождения)
14 марта 1962 г. исполнилось 80 лет со дня рожде-
рождения выдающегося польского математика Вацлава Сер-
пинского.
Интерес к математике и незаурядные способности
обнаружились у Серпинского еще в школьные годы.
В 1900 г. он поступил в Варшавский университет на
физико-математический факультет, где в то время ра-
работал один из крупнейших представителей петербург-
петербургской школы теории чисел Г, Ф. Вороной.
Свою первую научную работу Серпинский посвятил
теоретико-числовой проблеме, которую сформулировал
Вороной в качестве темы для конкурсных студенческих
сочинений. В 1904 г. Серпинский представил сочинение
<
«О суммировании ряда 2х (л)/(д) при условии, что
п>а
i(n) представляет число разложений п на сумму квад-
квадратов двух целых чисел». В том же году Варшавский
университет на основании отзыва Вороного присудил
Серпинскому за эту работу золотую медаль и присвоил
ученую степень кандидата математических наук. С это-
этого времени теория чисел становится излюбленным
предметов занятий Серпинского. Число его арифмети-
арифметических работ быстро растет.
В 1905 г. Серпинский после забастовки учащейся
молодежи, в которой он принимал участие, переезжает
в Краков и поступает в Ягеллонский университет. Здесь
ему была присвоена степень доктора.
В 1907 г. Серпинский получил свой первый резуль-
результат по теории множеств. С этого момента начинается
его исключительно плодотворная деятельность в области
3 В СерпиискиЯ ?

теории множеств и ее приложений к топологии, теории
функций действительного переменного и другим обла-
областям математики. Серпинский быстро приобретает из-
известность. В 1908 г. он начал преподавать во Львов-
Львовском университете и вскоре получил там профессуру.
В 1911 г. Краковская Академия наук награждает Сер-
пинского за работы, опубликованные им в 1909—
1910 гг. на польском языке. Спустя два года эта же
академия присуждает ему премию за «Очерк теории
множеств», а в 1918 г. — за монографию «Теория чи-
сел>.
Во время первой мировой войны Серпинский был
интернирован. Четыре года он провел в Москве и Вят-
Вятке. Здесь он продолжал свою научную деятельность и
имел полезные контакты с Н. Н. Лузиным и другими
русскими математиками.
Весной 1917 г. Краковская Академия наук избрала
Серпинского своим членом-корреспондентом.
С 1919 г. Сер пинский — профессор Варшавского
университета- Уже в следующем году он с профессо-
профессорами С. Мазуркевичем и 3. Янишевским основал
в Варшаве журнал «Fundamenta Mathematicae», кото-
который сыграл большую роль в развитии современной
математики. Этот журнал продолжает выходить и в на-
настоящее время.
В 1921 г. Серпинский был избран действительным
членом Польской Академии наук. Необычайная творче-
творческая активность, выдающиеся педагогические, литера-
литературные и организационные способности Серпинского
ставят его во главе польской математической школы.
Университеты различных стран и континентов присваи-
присваивают ему звание почетного профессора, степень док-
доктора honoris causa. Ряд академий и научных обществ
избирают его своим членом-корреспондентом и почет-
почетным членом. Имя Серпинского приобретает огромную
популярность. В обиход математиков входят термины:
«Универсальная кривая Серпинского», «Треугольная
кривая Серпинского», «Ковер Серпинского» и др.
В годы второй мировой войны Серпинский ие пре-
прекращал научную работу и даже преподавая в под-
подпольном университете. После освобождения Польши,
с февраля 1945 г. Серпинский некоторое время работал
в Ягеллонском университете в Кракове, a odete»*) 1945 г.
в

вернулся в Варшаву. И снова большой труд по вос-
восстановлению университета, снова, как и в предвоенные
годы, лекции в различных университетах Европы, Ин-
Индии, Канады, США.
В 1949 г. Серпинский был награжден в Польше
первой Государственной премией за научную деятель-
деятельность. В 1951 г. он был избран вице-президентом Поль-
Польской Академии наук.
В апреле 1957 г. Серпинский принял участие в юби-
юбилейной научной сессии АН СССР, посвященной 250-ле-
250-летию со дня рождения Л. Эйлера. В том же году Сер-
Серпинский возобновил издание международного журнала
«Acta Arithmetica», посвященного вопросам теории
чисел.
Список работ, опубликованных Серпинским, содер-
содержит свыше 600 названий. Среди них около 30 универ-
университетских учебников и монографий. Серпинский — член
II иностранных академий и многих научных обществ.
Более 20 его учеников являются в настоящее время
профессорами в Польше и в других странах. Недавно
степень доктора получил его ученик — молодое талант-
талантливый математик Андрей Шинцель, работы которого
в области теории чисел уже приобрели широкую из-
известность, Вацлав Серпннскнй — старейший академик
Польши — по праву считается отцом польской школы
математиков.
И. Г. Мельников
ОТ ПЕРЕВОДЧИКА
Настоящий перевод книги польского академика
Вацлава Серпинского несколько отличается от ориги-
оригинала, появившегося летом 1961 г. на польском языке.
В последнее время наши познания о простых чис-
числах немного пополнились. В связи с этим в марте
1962 г. автор прислал мне ряд поправок и дополнений
к книге. Все они учтены в настоящем издании.
Я весьма признателен редактору книги Н. М. Розен-
гауз, внесшей ряд улучшений в рукопись перевода.
И. Мельников
3*

ПРЕДИСЛОВИЕ
Цель этой книги — сообщить в наиболее доступной
форме о том, что мы знаем и чего не знаем о простых
числах. С простыми числами мы встречаемся уже в
элементарной арифметике, но они играют важную роль
и в других разделах математики, главным образом в
теории чисел и алгебре.
Математика считается, и справедливо, наукой де-
дедуктивной. Тем не менее не следует умалять роль, ко-
которую сыграла в математике индукция, и притом не
так называемая полная индукция, а индукция, основан-
основанная на наблюдении большого числа случаев и ведущая
от них к предполагаемым общим теоремам. Особенно
это относится к учению о Простых числах, где именно
таким путем было открыто много важя»х теорем, до-
доказательства которых были найдены лишь позднее. Но
этот путь часто приводил и к ошибочным предполо-
предположениям. Известны также различные предположения,
которые для многих частных случаев проверены, но
о которых до сих пор неизвестно, истинны они или нет.
Обо всем этом будет идти речь в данной книге.
Книга не является учебником по теории простых чи-
чисел; она имеет в основном информационный характер.
В книге доказываются лишь некоторые теоремы, именно
те, доказательства которых совершенно элементарны и
не очень громоздки. Читателя, желающего познако-
познакомиться с доказательствами других теорем и углубить
свои знания о простых числах, отсылаю ко второй ча-
части моей книги «Теория чисел»1), где указывается и
дополнительная литература.
Варшава, март 1961 г. Вацлав Сергищский
') См W. Sierpinski, Teoria liczb. II, Wtraiawa, 1959.
(Прим. перев)
10

1. Что такое простые числа?
К понятию простых чисел приводят уже самые про-
простые задачи, которые возникают в связи с таким эле-
элементарным арифметическим действием, как умножение
натуральных, т. е. целых положительных чисел.
Как известно, произведение двух натуральных чисел
всегда является числом натуральным, Следовательно,
существуют натуральные числа, представляющие собой
произведения двух натуральных чисел, больших еди-
единицы» Но существуют также натуральные числа, боль-
большие единицы, которые не являются произведениями
двух натуральных чисел, ббльших единицы, например
числа 2, 3, 5 или 13. Именно такие числа мы называем
простыми.
Итак, простым числом мы называем каждое нату-
натуральное число, большее единицы, которое не является
произведением двух натуральных чисел, ббльших едиг
ницы.
Напрашивается вопрос, имеем ли мы возможность
относительно каждого натурального числа п > 1 уста-
установить, простое оно или нет. Оказывается, само опре-
определение простых чисел позволяет ответить на этот
вопрос.
Действительно, если натуральное число п > 1 не
является простым, то оно представляет собой произве-
произведение двух натуральных чисел а и Ь, ббльших единицы,
т. е. п = ab, где а > 1 и Ь > 1, откуда тотчас же сле-
следует, что п > а и п> Ь. Натуральное число п > 1, не
являющееся простым, есть, таким образом, произведе-
произведение двух натуральных чисел, меньших п. Такое число
мы называем составным. Если число п составное,
то п = ab, где а и Ь — числа натуральные >1 и <п.
Частное п:а = Ь является натуральным числом,
Н

следовательно, а есть делитель «атурального числа п,
больший 1 и меньший чем п. Поэтому, чтобы убедиться
в том, что натуральное число п > 1 является простым,
достаточно убедиться, что оно не имеет натурального
делителя >1 и <п. Для этого достаточно выполнить
п — 2 делений числа п поочередно на числа 2, 3, ...,
п — 1. Если ни на одно из них число п не делится без
остатка, то в этом и только в этом случае число п яв-
является простым.
Итак, по крайней мере теоретически, мы всегда
сумеем (при помощи конечного числа делений) убе-
убедиться, является ли данное натуральное число п про-
простым или нет. На практике описанный способ может
порождать значительные трудности, когда п большое
число. Так, до сих пор мы не можем, ввиду длинноты
необходимых вычислений, применить этот способ
к числу 2101 — 1, имеющему тридцать одну цифру (в де-
десятичной системе счисления), хотя другим путем дока-
доказано, что это число является составным. Впрочем, до
сих пор неизвестно ни одного разложения этого числа
в произведение двух натуральных чисел, больших еди-
единицы (хотя мы и знаем, что такое разложение суще-
существует). Также неиавестно, является лн число 22" + 1
(имеющее 39 457 цифр) простым или нет.
2. Простые делители натуральных чисел
Докажем теперь несколько несложных теорем о про*
стых числах. <'
Теорема 1. Каждое натуральное число п > 1 имеет
по меньшей мере один простой делитель.
Доказательство. Пусть п — натуральное число
>1. Это число имеет делители, большие единицы, на-
например само п. Среди делителей числа п, больших еди-
единицы, существует наименьший. Обозначим его через р.
Если бы число р не было простым, то, согласно опре-
определению простых чисел, р было бы произведением двух
натуральных чисел, больших единицы: р-= ab> а.
В этом случае а было бы делителем числа р, а значит,
и числа л, большим единицы и притом меньшим р, что
противоречит определению числа р. Теорема 1 дока-
доказана.
12

Теорема 2. Каждое составное число п_ имеет по
меньшей мере один простой делитель -^Vn.
Доказательство. Если п есть составное число,
то п = ab, где а и ft — натуральные числа > 1 и <л.
Мы можем, очевидно, предположить, что а<^Ь. Тогда
п = ab ~^> аг, и, следовательно, а < У~п. Но а есть число
>1. Поэтому, согласно теореме 1, число а имеет про-
простой делитель р, который, очевидно, -^а и, следователь-
следовательно, <^Vn- Но р как делитель делителя а числа п яв-
является делителем и числа п. Таким образом, число п
имеет простой делитель р<|Л«. Итак, теорема 2 до-
доказана.
3. Сколько существует простых чисел?
Чтобы ответить на этот вопрос, мы докажем следую-
следующую теорему.
Теорема 3. Если п — натуральное число >2, то
между п и пГ содержится по меньшей мере одно про-
простое число.
Доказательство. Так как п > 2, то целое число
N = п\ — 1, очевидно, >1 и, согласно теореме 1, имеет
простой делитель р, который ^N, а следовательно, и
<л!. Если допустить, что р^п, то р будет одним из
сомножителей произведения nl = 1 »2«3 ... п и, значит,
будет делителем числа п\. Но, будучи также делителем
числа N, р будет делителем разности этих чисел, или
числа п!—N = 1, что невозможно. Таким образом,
р > п, а так как уже выяснено, что р < п\, то имеем
п <р <п\, нк значит, теорема 3 доказана.
Итак, для каждого натурального числа существует
простое число, большее его. Отсюда следует, что про-
простых чисел бесконечно много, об этом знал
уже Евклид. В частности, отсюда следует, что суще-
существует простое число, имеющее (в десятичной системе
счисления) по крайней мере тысячу цифр. Однако ни
одного такого числа еще в I960 г. мы не знали. Наи-
Наибольшее известное тогда простое число 2*ш — 1 имело
969 цифр. (Подробнее об этом числе будет сказано
в § 25.) '
13

Стоит подчеркнуть, что в течение последнего десяти-
десятилетия здесь наблюдался значительный прогресс. К на-
началу 1951 г. наибольшим известным простым числом
было число 2127—1, имеющее 39 цифр (то, что это
число простое, было доказано уже в 1876 г.). В на-
настоящее же время наибольшим известным простым
числом является число 24423—1, имеющее 1332 цифры.
В связи с теоремой 3 заметим, что в 1850 г. П. Л. Че-
бышев ддказал более сильную теорему (так называе-
называемый постулат Бертрана), согласно которой для нату-
натуральных л>3 между п и 2п— 2 содержится хотя бы
одно Простое число. Отсюда следует, что в теореме 3
число лТ можно заменить числом 2л. В настоящее время
имеется элементарное доказательство этой теоремы, ио
оно довольно длинное1). Можно также доказать, что
для натуральных л > 5 между л и 2л содержатся по
меньшей мере два простых числа2).
Из теоремы Чебышева легко вывести, что для ка-
каждого натурального числа s существует по крайней
мере три простых числа, имеющих по s цифр каждое.
Действительно, каждое из чисел 108-1, 2'Ю8-1, 4 - 10s—t
и в-Ю8 имеет s цифр, а в силу теоремы Чебышева
для s > 1 существуют простые числа р, q и г такие, что
КГ1 <р < 2 • 1(Г' < q < 4 • 1(Г' < г < 8 • 1(Г\
и, следовательно, каждое из чисел р, q, г имеет по s
цифр.
Для s = 1 мы имеем четыре однозначных простых
числа: 2, 3, 5 и 7. Двузначных простых чисел имеется
21, трехзначных — 143. Существуют хотя бы три про-
простых числа, имеющие по сто цифр каждое. Недавно
Р. М. Робинзон нашел такие числа: 81-2824+1, 63 X
X 2326+ 1, 35-2е27 + 1.
До сих пор мы не знаем ни одного простого числа,
имеющего тысячу цифр, хотя известно, что существуют
по меньшей мере три таких числа.
') См., например, W. Sierpinski, Arytmetyka teoretyczna,
Wyd. 2, Warszawa, 1959, str. 88—94.
!) Cm, W. Sierpinski, Teoria Hczb, II, Warszawa, 1959,
str. 400,
14

4. Как можно найти все простые числа,
меньшие данного числа?
Способ, о котором будет идти речь, известен был
уже "в древности: он носит название решета Эра-
Эрато с ф ен а.
Предположим, что мы хотим найти все простые
числа, не превосходящие некоторого натурального чис-
числа а. С этой целью выпишем все последовательные на-
натуральные числа от 1 до а и будем вычеркивать из этой
последовательности все числа, которые не являются
простыми: прежде всего число 1, а затем для каждого
натурального числа п > 1 все числа, большие чем п и
делящиеся на п. Легко видеть, что таким путем ка-
каждое составное число окажется вычеркнутым и оста-
останутся только простые числа.
Итак, из последовательности 1, 2, 3, 4, ..., а мы вы-
черкием число 1, затем числа, большие чем 2 и деля-
делящиеся на 2, далее числа, большие чем 3 и делящиеся на
3. Чисел, делящихся на 4, вычеркивать нам уже не
придется, так как они вычеркнуты как числа >2 и де-
делящиеся на 2. Таким образом, далее мы будем вычер-
вычеркивать числа, большие чем 5 и делящиеся на 5 и т. д.
При этом мы можем уже не вычеркивать ни одно из
чисел > V а. Действительно, если п — составное число
>У а и <!а,то, согласно теореме 2, число п_ имеет про-
простой_ делитель p-^Y п, следовательно, -^ у а, и число п
окажется вычеркнутым как число, большее р и деля-
делящееся на р.
Так, например, желая получить все простые числа
<:100, вычеркнем из последовательности 1, 2, 3, ..., 100
число 1, затем числа >2 и делящиеся на 2, далее числа
>3 и делящиеся на 3, затем числа >5 и делящиеся на
5 и, наконец, числа >7 и делящиеся на 7. Все числа,
оставшиеся в нашей последовательности, будут про-
простыми. Таким путем мы получим следующую последо-
последовательность (в которой все простые числа выделены
жирным шрифтом):
1,- 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18,
19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34,
35, 36, 37, 38, 39, 40, 4J, 42, 43, 44, 45, 46, 47, 48, 49, 50,
51,-52, 53, 54. 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66.
4 В. СерпнвскиЯ 15

67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82,
83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98,
99, 100.
Обозначим n-e по порядку простое число через р«.
Тогда р, = 2, р2 = 3, р3 = 5, р4 =■ 7, ps=-U, р„> *= 29,
р25 = 97. Легко можно подсчитать, что рюо *■ 541.
В 1909 г. были изданы таблицы простых чисел, мень-
меньших 10 миллионов1), в которых для каждого нату-
натурального числа <10170 000, не делящегося на 2, 3, 5
или 7, дается его наименьший простой делитель.
В 1951 г. были опубликованы таблицы простых чисел
до 11-го миллиона2).
Якуб Филипп Кулик A793—1863 гг.) составил таб-
таблицы простых чисел, содержащихся в первых ста мил-
миллионах3). Эти таблицы после проверки были исиоль-
зоваиы при составлении таблиц простых чисел 11-го
миллиона, изданных в 1951 г. Недавно A959 г.)
К- Л. Бейкер и Ф. Ю. Груибергер составили микро-
микрофильм, содержащий все простые числа <р«оо»ооо =
= 104 395 3014).
5. Простые числа близнецы
Относительно бесконечной последовательности по-
последовательных простых чисел, т. е. последовательно-
последовательности
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, ....
возникает ряд вопросов. Лишь на некоторые из них
удается легко дать ответ.
Так, например, два наименьших простых числа 2 и
3 являются последовательными натуральными числами.
Напрашивается вопрос, существуют ли другие после-
последовательные натуральные числа, которые оба были бы
') D. N. Lehmer, Factor table for the first ten millions, Wa-
Washington, Carnegie Institution, 1909.
Ъ J. P. Kulik, L. Poletti, R. J. Porter, Liste des nombres
premiers du onzieme million (plus precisement de 10006 741 a
10 999 997), Amsterdam, 1951.
*) Неопубликованная рукопись Я. Ф. Кулика хранится в Ав-
Австрийской Академии наук в Вене.
4) The first six million prime numbers, The RAND Corporation,
Santa Monica, published by the Microcard Foundation, Madison,
Wisconsin, 1959.
16

простыми. Легко доказать, что таких чисел иет. В са-
самом деле, из каждых двух последовательных натураль-
натуральных чисел одно является четным, и, значит, если оно
>2, то оно составное.
Однако существует много пар последовательных ие-
четиых чисел, которые оба являются простыми, напри-
например пары 3 н 5, 5 и 7, 11 и 13, 17 и 19, 29 и 31, 41 и 43.
Такие пары мы называем парами чисел близне-
близнецов. До 30 миллионов имеется 152 892 таких пар.
Уже.давно поставлен вопрос, существует ли беско*
нечно миотсПхар простых чисел близнецовТ~На этот во*
прос мы не знаем ответа. Итак, мы не знаем, предста-
вимо ли число 2 бесконечным числом способов в виде
разности двух простых чисел.
Высказано предположение, что каждое ^четное число
можно бесконечным числом способов представить в виде
разности двух последовательных простых чисел. Одна-
Однако мы ие можем доказать даже того, что каждое чет-
четное число предстдвшж н таком рцде хотя бы одним
способом, что проверено для многих последовательных
четных чисел, например, 2 = 5 — 3, 4=11 — 7, 6 =
= 29 — 23, 8 = 97 — 89, 10 - 149—139, 12 = 211 — 199,
14 = 127—113, 16=1847—1831, 18 = 541 — 523, 20 =
= 907 — 887. Более тогот мы не можем доказать даже
того, что кяждое_зетное число представляет собой раз-
разность двухлшостыхлисел (хотя бы и иепоследователь-*
ных).
Но мы можем найти все нечетные числа, предста-
представляющие собой разность двух простых чисел. Действи-
Действительно, еели натуральное нечетное число п является
разностью двух простых чисел, п = р — q, то одно из
этих простых чисел должно быть четным, а другое не-
нечетным, следовательно, одно из чисел р и q, и как лег-
легко видеть, именно число q, должно быть равно 2.
Таким образом, имеем п = р — 2, где р — простое не-
нечетное число. Итак, все натуральные нечетные числа,
которые являются разностью двух простых чисел,
меньше простых нечетных чисел на 2, следовательно, это
числа 1, 3, 5, 9, 11, ... Таких чисел бесконечно много.
Однако существует бескоиечио много и таких не-
нечетных- лзде^л,нкоторые нё~авляются рЗапОСТью двух
простых.„чисел, например все числи вида ёк+ 1, где
* — натуральное"" чйслбГ БГ~самом деле, равенство
4* " I?

6fe + 1 = p — 2, где p — простое число, невозможно, так
как из него следует, что р — 6& + 3 = 3B& + 1), т. е.
что р есть составное число.
6. Гипотеза Гольдбаха
В 1742 г. Хр. Гольдбах высказал предположение, что
каждое четное число >2 является суммой двух про-
простых чисел. Это предположение до сИХ пор не доказано
и не опровергнуто. Оно проверено для всех четных чи-
чисел вплоть до 100 000. Была аыскааана и более силь-
сильная гипотеза, а именно, что каждое четное число >6
является суммой двух различных простых чисел. Эту
гипотезу С. Голашевскии проверил для всех чисел
<50 000.
Можно доказать, что последняя гипотеза равно-
равносильна ухвержлению, что каждое натуральное Тйсло
>17 является суммой трех различных простых чисел.
А. Шинцель доказал, что из гипотезы ГШ1ьдб"аха сле-
следует, что каждое нечетное число >17 является суммой
трех различных простых чисел.
Из гипотезы Гольдбаха следует также, что нечетное
число >7 является суммой трех простых нечетных чи-
чисел. Действительно, если л есть натуральное число и
2л + 1 > 7, то 2л + 1 — 3 = 2(п — 1) > 4. Согласно ги-
гипотезе Гольдбаха, четное число 2(л—1) >4 есть сум-
сумма двух простых чисел р + q, причем р и q не могут
быть четными, так как наше число >4. Таким образом,
числа р и q являются нечетными, и, значит, число 2л +
+ 1 = 3 + р + q есть сумма трех простых нечетных
чисел.
Мы не знаем, является ли каждое нечетное число
>7 суммой трех простых нечетных чисел, однако для
достаточно больших нечетных чисел это было доказано
И. М. Виноградовым в 1937 г. Мы даже знаем такое
число а (а = 33"), что каждое нечетное число >а яв-
является суммой трех простых Нечетных чисел.
Таким образом, решению вопроса, является ли ка-
каждое нечетное число >7 суммой трех простых нечет-
нечетных чисел, препятствует лишь громоздкость необходи-
необходимых для этого вычислений, так как здесь достаточно
исследовать только нечетные числа >7 и -<а, а для ка-
18

ждого данного нечетного числа можно при помощи ко-
конечного числа простых арифметических действии ре-
решить, является оно суммой трех простых нечетных чи-
чисел или нет.
Иначе обстоит дело с гипотезой Гольдбаха: здесь
мы не можем сказать, что решению вопроса, верна
или нет эта гипотеза, мешает только громоздкость не-
необходимых вычислений.
Доказано, что каждое натуральное число >1 есть
сумма двадцати или менее простых чисел.
Доказано, что каждое натуральное число >П есть
сумма дзух или более различных простых чисел. На-
Например, 12 = 5 + 7, 13 = 2+11, 17 = 2 + 3 + 5 + 7,
29 = 3 + 7 + 19. А. Монковский же доказал, что ка-
каждое натуральное число >55 есть сумма различных
простых чисел вида 4А + 3, и доказал три аналогичных
теоремы о суммах простых чисел каждого Из видов
4/г + 1, 6k + 1 и 6k + 5.
Из гипотезы Гольдбаха следует, что каждое целое
нечетное число (положительное или отрицательное)
может быть бесконечным числом способов представлено
в виде р + q — г, где р, q, r — простые нечетные числа.
Действительно, для каждого целого числа k суще-
существует простое нечетное число г такое, что 2k — 1 + г >
> 4 (в качестве г можно взять любое достаточно боль-
большое простое число). Но тогда 2k — 1 +г есть четное
число >4 и, следовательно, согласно гипотезе Гольд-
Гольдбаха, 2k — 1 + г = р + q, где р и q — простые нечет-
нечетные числа. Таким образом, 2k — 1 = р + q — г, причем
простое число г может быть произвольно большим. От-
Отсюда вытекает предложение, сформулированное выше.
Интересно отметить, что последнее предложение
было доказано Дж. Г. ван дер Корпутом в 1923 г. Од-
Однако его доказательство весьма сложно1).
В связи с гипотезой Гольдбаха заметим, что каждое
натуральное число > 11 есть сумма двух составных чи-
чисел. Действительно, если п > 11 является числом чет-
четным, то п — 4' есть четное число >2, следовательно,
число составное, и, значит, п есть сумма двух состав-
составных чисел: 4 и п — 4. Если же п> 11 является числом
нечетным, то п — 9 есть четное число >2 и, следова-
') См. J. G. van der Cor put. Acta Mathematica, 44, 50.
10

тельно, составное, и, значит, п есть сумма двух состав-
составных чисел: 9 и п — 9. Отсюда, однако, нельзя сделать
вывод, что исследование составных чисел легче, чем
исследование простых чисел. Так, мы не можем, напри-
например, дать ответ на вопрос, существует ли среди чисел
/гв = 22"+1, где я = 1, 2, 3, ..., бесконечно много со-
составных (до сих пор мы знаем только 37 таких состав-
составных члсел, среди которых наибольшим является F^s).
Г. Г. Гарди и Дж. Е. Литтлвуд высказали предпо-
предположение (до сих пор не доказанное), что каждое до-
достаточно большое натуральное число, не являющееся
квадратом, есть сумма квадрата целого числа и про-
простого числа. Легко доказать, что существует бесконечно
много квадратов натуральных чисел, которые являются,
а также таких, которые не являются суммой квадрата
целого числа и простого числа.
Действительно, с одной стороны, если р есть про-
р-4-1
стое нечетное число, то J—A— является натуральным
числом, и мы имеем
m=HPir+*
с другой же стороны, если п = Zk + 2, где k — нату-
натуральное число, то равенство
при целом неотрицательном х и простом р невозможно,
так как из него следовало бы, что п > х и
р = п? — х3 = (л — х) (я + х),
откуда, принимая во внимание, что р есть простое чис-
число, п — х = 1 нл + * = рн, значит,
что при натуральном h исключено.
Другая теорема Гардн — Литтлвуда, согласи» кото-
которой каждое достаточно большое натуральное число есть
сумма двух квадратов целых чисел и простого числа,
была доказана в 1969 г. Ю. В. Лннняком.

7. Гипотеза Гильбрайта
Н. Л. Гильбрайт высказал в 1958 г. следующее пред-
предположение.
Если мы выпишем последовательные простые числа,
затем в первой строке — разности последовательных
простых чисел, во второй — абсолютные величины раэ-
ностей последовательных чисел первой строки, в треть-
третьей — абсолютные величины разностей последовательных
чисел второй строки и т. д., то в каждой строке пер-
первым числом будет 1.
Так, например, первые 17 строк (следующих за по-
последовательностью простых чисел) выглядят следую-
следующим образом:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61
12242424626424632
1022222244222204
120000020200024
12000022220022
12000200*2020
1 20022002222
12020202000
1222222200
100060020
10000022
1 0 6 « 0 2 О
10 0 0 2 2
10 0 2 0
10 2 2
1 2 0
1 2
1
Гипотеза Гильбрайта цроверена для первых 63 418
строк. Однако мы не знаем общего доказательства ее
истинности.

Обозначим для натуральных я через а„ наименьшее
натуральное число такое, что (а„ + 1)-е число я-й стро-
строки является первым числом этой строки, которое >2.
Таким образом, мы имеем, например, а.\ = 3, ач — 8,
а3= 14. Подсчитано, что а4 = 14, а$ = 25, а6 = 24, а? =•
= 23, а8 = 22, а9 = 25, а10 == 59, а,4 - 97, ai5 - 174, а22 *=
= 280, а2з = 740, 024 = 874, а34 = 866, aJ5~2l8Q, а64 =»
= 5940, ass = 23 266, аЭ4 =* 31 533.
Если бы можно было доказать, что ап > 2 для нату-
натуральных я, то отсюда легко можно было бы установить
истинность гипотезы Гильбрайта.
8. Разложение натурального числа
«а простые сомножители
Опираясь на теорему 1, докажем следующую тео
рему.
Теорема 4. Любое натуральное число > 1 является
произеедением, каждый сомножитель которого есть
простое число.
Доказательство. Пусть п — данное натураль-
натуральное число >1. Согласно теореме 1, число я имеет (по
крайней мере один) простой делитель р\ и мы можем
предположить, что р' есть наименьший простой делитель
числа я. Итак, имеем п = р'п', где я' — натуральное
число.
Если я'=1, то п = р' и я является произведением,
составленным только из одного простого сомножителя.
Если же я'> 1, то п' имеет простой делитель р", о ко-
котором мы можем предположить, что он есть наимень-
наименьший простой делитель числа я'. Одновременно он яв-
является простым делителем числа п, причем из опреде-
определения числа р' следует, что р'<р".
Таким образом, п' — р"п", и либо я" = 1, и тогда п
есть произведение двух простых чисел р' и р" (не обя-
обязательно разных), либо я" > 1, и тогда с числом я" мы
можем поступить, как ранее с числами я и я' и т. д.
Так как я = р*ц' и р' > 1, то имеем я' < я. Аналогично
найдем, что я" р'ит. д. Поэтому натуральные числа
п, я', я", ... образуют убывающую последовательность,
которая не может содержать более чем я членов. Сле-
Следовательно, при некотором натуральном k число ФУ
22

будет последним членом этой последовательности. Но
в таком случае п<*> = 1, ибо в случае п№ > 1 мы могли
бы положить
и получили бы дальнейший член «(*+') нашей последо-
последовательности. Итак, имеем п = р'п', п' = р"п", ...,
СЧ (%(*> ф) — ], откуда найдем
п=р'р"рт .../**>, A)
где р', р", ..., p(ft) — простые числа, причем можно
предполагать, что р'<р"<р'"< ...<p<h> (если для
каждого из чисел п, я', ... мы будем определять его
наименьший простой делитель).
Среди сомножителей произведения A) могут быть
равные. Формулу A) можно записать в виде:
n = qa^...qa/. B)
где s — натуральное число, qu qz, ,.., q&—различные
простые числа, расположенные в порядке возрастания,
п\, й2, ..., а,— натуральные показатели степени.
Формула B) называется каноническим разло-
разложением числа п на простые сомножители.
Итак, мы не только доказали теорему 4, но и ука-
указали способ нахождения для каждого натурального чи-
числа п > 1 его канонического разложения на простые
сомножители. Таким образом, нахождение этого разло-
разложения для любого данного натурального числа я > 1
теоретически всегда возможно. Однако на практике оно
может потребовать проведения утомительных вычисле-
вычислений, которые для некоторых чисел оказываются столь
длинными, что в настоящее время их невозможно осу-
осуществить даже при помощи самых лучших вычислитель-
вычислительных машин. Например, мы не знаем разложения на
простые сомножители числа 2101 — 1 (имеющего 31
цифру); доказано только, что оно является произведе-
произведением двух различных простых сомножителей, меньший
из которых (впрочем, до сих пор неизвестный) имеет
не менее 11 цифр. Мы не знаем также разложения на
простые сомножители числа F\j = 22" + 1, о котором
неизвестно да,же, является ли оно простым или нет.
Зато для числа Ртъ = 22"* + 1, имеющего более
23

чем 10582 цифр (ибо 219*5 = 32 • 219« - 32 • B10)т >"
> 30 • A03IМ = 3 • 10583, откуда FM5 > 23 • '«•" =
-_ B1(>K-1Й6М > Ю9-10""), несколько лет назад был най-
найден наименьший простой делитель. Этим делителем
является число 5»21947 + 1, имеющее 587 цифр. Но мы
не знаем разложения числа F1945 на простые сомножи-
сомножители и даже не знаем других простых делителей этого
числа (см. § 22).
Напрашивается вопрос, является ли разложение B)
числа я > 1 на простые сомножители единственным
(если числа <7ь <7г, • • •. Я» составляют возрастающую
последовательность). Доказательство однозначности
разложения опирается на несколько несложных теорем
о простых числах.
Теорема 5. Простое число р имеет только два на-
натуральных делителя 1 и р.
Доказательство. Если бы число р, кроме дели-
делителей 1 и р, имело еще делитель а, то, очевидно, было
бы 1 < а < р и р — ab, где Ъ — натуральное число > 1,
ибо если 6 = 1, то р ~ а, что противоречит предполо-
предположению относительно а. Таким образом, число р было
бы произведением двух натуральных чисел, больших
единицы, а это противоречит предположению о том, что
р есть простое число. Итак, теорема 5 доказана.
Как легко видеть, справедлива также теорема, со-
согласно которой натуральное число р, имеющее точно
два натуральных делителя, является простым. Действи-
Действительно, в этом случае должно быть р > 1. Далее, если
бы р не было простым числом, то р являлось бы про-
произведением двух натуральных чисел а и Ъ, больших
единицы. Но из того, что р = ab и b > 1, следовало бы,
что 1 < а <р, т, е. а было бы делителем числа р, от-
отличным от 1 и р, и, значит, число р имело бы по мень-
меньшей мере три различных натуральных делителя.
Таким образом, имеет место
Теорема 6. Для того чтобы натуральное число
было простым, необходимо и достаточно, чтобы оно
имело точно два натуральных делителя (очевидно, еди-
единицу и самого себя).
Докажем теперь следующую теорему.
Теорема 7. Если а и Ь — натуральные числа и про-
произведение ab делится на простое число р, то по крайней
мере одно из чисел а и Ь делится на р.
24

Доказательство. Если бы теорема 7 не была
справедлива, то существовало бы наименьшее простое
число р, для которого она не верна. Для такого просто-
простого числа р существовало бы наименьшее произведение
ab двух натуральных чисел а и Ь, делящееся на р, не-
несмотря на то, что ни один из сомножителей а и Ь не де-
делится на р. Покажем, что тогда числа а и b были бы
меньше, чем р. В самом деле, если, например, оказа-
оказалось бы, что а > р, то мы имели бы равенство а — kp +
+ аи где а\ < р и at > 0, ибо а не делится на р. От-
Отсюда ab ~ {kp + щ)Ь = kpb + atb, и так как числа ab
и kpb делятся на р, то и аф делится на р. Но а\ < р <
< а и at не делится на р, причем ai6 < аи, что противо-
противоречит предположению относительно произведения ab.
Итак, доказано, что а < р. Подобным же образом мы
докажем, что b < р и, значит, ab < р2.
Далее, поскольку ab делится на р, имеем ab = lp,
где /—натуральное число, большее 1, так как иначе
было бы р = ab, где а > 1 и 6 > 1 (ибо числа а и 6 не
делятся на р).
С другой стороны, на основании неравенства ab < р2
получаем / < р. Число /, будучи натуральным числом
> 1, имеет простой делитель q^.l<p. Учитывая те-
теперь определение числа р, а также то, что произведение ab,
делящееся иа /, делится также на простое число q < р,
мы заключим, что хотя бы один нз сомножителей а и
b должен делиться на q. Если, например, а делится на
q, то а — а'ц. Но / делится и а щ, следовательно, I — tq,
где t — натуральное число. А так как ab == lp, то
a'qb = tqp, откуда a'b = tp, причем, учитывая, что a =
= a'q, имеем а' < а, откуда a'b < ab, что противоречит
предположению относительно произведения ab. Итак,
предположение о том, что теорема 7 неверна, приводит
к противоречию.
Из доказанной теоремы при помощи индукции мож-
можно получить следующее
Следствие. Если at, аз, ..., От — натуральные
числа, произведение которых делится на простое число
р, то по крайней мере одно из чисел at> а% ..., ат
должно делиться на р.
Доказательство. Это следствие справедливо
для m =* 2. Предположим, что оно справедливо для
m чисел, и пусть числа at, a^, ..., am, am+i являются
25

натуральными. Если произведение п\аг...ататН делится
на простое число р, то, согласно теореме 7, по крайней
мере одно из двух чисел а,а2 ... ат и ато+1 делится на р.
Если число uiu2 ... ат делится на р, то в силу пред-
предположения, что следствие справедливо для т чисел,
заключаем, что хотя бы одно из чисел щ, а2, . .^, а^
делится на р. Итак, из справедливости следствия для
т чисел следует его справедливость для т + 1 чисел.
Предположим теперь, что существуют натуральные
числа, имеющие два различных канонических разложе-
разложения на простые сомножители. Среди таких натуральных
Чисел существует, очевидно, наименьшее. Пусть это бу-
будет число п, которое кроме канонического разложения,
« = ##•••# B)
обладает разложением
ге = гХ>...г»<, C)
где г\, г2, ..., rt — возрастающая последовательность
простых чисел, а Ь\, Ьч bt—числа натуральные.
Согласно B), число п делится на t/y, и поэтому, в силу
C) и следствия теоремы 7, во крайней мере одно из
чисел Г\. гч, ..., rt должно делиться на q\. Очевидно,
это будет число rt, так как q\ — наименьший простой
делитель числа C). Но, согласно теореме 5, простое
число гх имеет только два натуральных делителя: 1 и ru
поскольку же простое число q\ также является делите-
делителем числа гу, то должно быть Г\ = qt. Заменив в фор-
формуле C) г\ на tfu мы, ввиду B), получим для числа и',
где п = Ц\п', следующее равенство:
Так как число п' меньше чем п, то, в соответствии с
предположением относительно числа п, число п' имеет
только одно каноническое разложение на простые со-
сомножители, откуда уже легко следует, что должно быть
s = t, г2 = <7г, ^3 = <7з, • • •, г, ~ qa, at ?= bt, a2 = fe2, ...,
as~bs. Таким образом, вопреки предположению, раз-
разложения B) и C) оказались идентичными. Следова-
Следовательно, предположение, что существуют натуральные
числа, имеющие два различных канонических разложе-
разложения на простые сомножители, приводит к противоречию.
26

Итак, доказана
Теорема 8. Каждое натуральное число п > 1 дает
только одно разложение на простые сомножители, если
не обращать внимания на порядок сомножителей.
9. Какими цифрами могут начинаться
и заканчиваться простые числа?
Последняя цифра простого числа, имеющего более
чем одну цифру, не может быть четной, так как тогда
число было бы >2 и четным и, следовательно, было бы
составным; последняя цифра не может быть и 5, так
как в этом случае число было бы >5 и делилось бы на
5 и, значит, было бы составным. Таким образом, послед-
последней цифрой простого числа >10 может быть только 1,
3, 7 или 9.
Ничего больше о цифрах простых чисел, превосхо-
превосходящих 10, в частности о комплексах нескольких послед-
последних или нескольких первых цифр простых чисел, сооб-
сообщить нельзя, так как имеет место следующая теорема:
Если имеются две произвольные конечные последо-
последовательности цифр (в десятичной системе счисления) ait
«2, •.., am и bu b2, ..., bn, где bn = 1, 3, 7 или 9, то
существует достаточно большое простое число р, у ко'
торого первыми m цифрами будут последовательно а\.
«2. ..., am, a n последними цифрами будут последова-
последовательно by, b2, ..., bn ')•
Из этой теоремы, в частности, следует, что суще-
существуют простые числа, имеющие в начале и в конце до-
достаточно большое число цифр, равных 1 (в средней ча-
части числа могут быть цифры, отличные от 1). Но
существует ли бесконечное множество простых чи-
чисел, все цифры которых являются единицами, мы
не знаем. Мы знаем лишь несколько простых чисел,
все цифры которых суть единицы, например, 11 и
11111111111111111111111 = Ш839~1 . Доказательство
простоты последнего числа (предложенное М. Крайчиком)
') Доказательство этой теоремы см. W. §ierpinski, Sur les
norobres premiers ayant des chiffres initiaux et finals donnes, Act a
Arithmetica, 5, 1959, 265—266.
27

сложно. Зато легко доказать, что если число, все циф-
цифры которого суть единицы, простое, то число его цифр
также должно быть простым. Это условие-, однако, ие
является достаточным, так как, например,
111 = 3-37, 11111 = 41.271, 1111111=239-4649.
Число —«р—, имеющее 37 цифр, также составное.
Найдены простые числа, составленные не только из
одних цифр 1, которые остаются простыми при каждой
перестановке их цифр. Среди двузначных таковыми яв-
являются числа: 13 и 31, 17 я 71, 37 и 73, 79 и 97, среди
трехзначных — числа: 113, 131, 311; 199, 919, 991; 337,
373, 733. Мы не знаем других таких чисел и не знаем,
конечно ли их число. X. Е. Ряхерт доказал, что для
3<и<6-10175 нет таких чисел, имеющих п цифр, кро-
кроме простых чисел, все цифры которых суть единицы.
Л. Мозер нашел все простые числа < 100000, не ме-
някмцие своего значения, если их цифры выписать в об-
обратном порядке. Их оказалось 102. Вот все такие
числа <1000: 101, 131, 151, 181, 313, 353, 373, 383, 727,
757, 787, 797, 919, 929. Неизвестно, существует ли бес-
бесконечно много таких простых чисел.
Мы не знаем, существует ли бесконечное множе-
множество простых чисел, первая и последняя цифры которых
суть единицы, а остальные — нули, как, например, число
101. Легко доказать, что такие простые числа должны
быть вида 102" + 1, где п — натуральное число, однако
это условие не является достаточным, так как, например,
1022+ 1 = 73-137.
Нам известно много простых чисел, среди цифр ко-
которых нет ни одного нуля, но мы не знаем, конечно илн
нет множество таких чисел. Можно доказать, что для
всякого натурального числа т существуют простые числа,
среди цифр которых имеется более чем т нулей. Мы
не знаем, существует ли для всякого натурального
числа т такое число а, что сумма всех цифр всякого
простого числа р, большего а, будет больше чем т.
10. Число првстых чисел,
не превосходящих данное число
Для данного числа х обозначим через тс (х\ число
простых чисел, не превосходящих х. Например, мы
имеем: тсA) = 0, тсB) = 1, тсC> = 2„ тсD> = 2, я|5) - 3,
2В

•ЫЩ - 4, тс>A00) = 25, тсA0ОО) « 168, тA0000) - 1229,
icA0«) = 5 761455, тсA0») - 50847534, uA010) -
= 455 052 512.
Л. Лохер-Эрнст заметил, что для п > 50 выражение
/(л) = -j j р р
дает достаточно хорошее приближенное значение числа
тс(п). Например, тсA0») - 168, a fA0») = 167,1. Для
п = 10* отношение тс (и) : f (п) равно 1,007, а для и =»
= 10я* оно составляет 1,005.
Можно доказать элементарно {хотя доказательство
будет длинным и сложным), что отношение ic(n) :f(n)
стремятся к единице, когда п возрастает неограниченно.
При больших п вычисление выражения f{n) пред-
представляет значительные трудности. Однако известны дру-
другие приближенные выражения для тс (и), например вы-
выражение -|—- (где In n обозначает натуральный лога-
логарифм числа п). Ж. Адам ар и Ш. де ла Валле-Пуссен в
1896 г. доказали, что отношение тс(я) к -п—- стремится
к единице, когда п неограниченно возрастает. Отсюда
следует, что отношение л-го простого числа рп к п In n
стремится к едивдще, когда п неограниченно возра-
возрастает1). Можно доказать, что миллиардное простое
число (т. е. число рю*) имеет 11 цифр.
Легко доказать, что для натуральных п > 1 имеет
Я (Л— 1) _. Я (Л)
место неравенство — _.- < —*-*■, если п есть про-
стое число, и неравенство ——р1 > —-—. если п —
число составное. Можно доказать, что отношение тс (я) к
п стремится к нулю, когда п неограниченно возрастает.
Вполне очевидно, что тс(рп) = « для натуральных п.
Легко доказать, что существуют сколь угодно длин-
длинные последовательности, составленные нз последова-
последовательных натуральных чисел, которые не содержат ни
одного простого числа. Примером последовательности,
*) Си. W. SierplftskI, Teoria ficzb, II. Warszawa, 1989,
str. 415.
29

состоящей из nt таких чисел, может служить последова-
последовательность
(т + 1I+2, (т + 1)! + 3, (т + 1)! + 4, ....
..., (т + 1)! + (т + 1),
ибо первое из чисел этой последовательности делится
на 2, второе на 3 и т. д., последнее на т + 1 и, таким
образом, все они являются числами составными.
Для т = 100 это были бы огромные числа, однако
уже между простыми числами 370 261 и 370373 лежат
1.11 последовательных составных чисел. Среди ста по-
последовательных чисел от 1 671 800 до 1 671 900 нет ни
одного простого числа
Труднее было бы доказать, что существует простое
число, которое с обеих сторон окружено произвольно
большим числом составных чисел, т. е. что для каждого
натурального числа т существует простое число р та-
такое, что каждое из чисел р — k и р + к, где k=*
«= 1, 2, .... m, является составным.
Также трудным является доказательство теоремы
Э. Ландау о том, что для достаточно больших натураль-
натуральных чисел п мы имеем itBn) < 2it(n), или, иначе го-
говоря, что для таких п простых чисел </г больше, чем
простых чисел, лежащих между п и 2/г.
Мы не знаем, для всех ли натуральных х > 1 и у >'
>1 выполняется неравенство тс(а: + у) <.ic(a:) + ic(«/).
11. Некоторые свойства л-го
по порядку простого числа
Согласно теореме X. Ж. Шерка, доказанной им в
1830 г., для натуральных п при соответствующем вы-
выборе знаков + или — имеем следующие формулы:
Р2п — 1 ± рх ± р2 ± ... ±/
/»8«+1 = 1 ± А ± Л ± • • • ±
Так, например,
Рб=
A—
или 13= 1 +2 — 3 — 5 + 7+ 11, 17 = 1+2 — 3 —&
+ 7 — 11+2-13.
30

Можно также доказать, что для натуральных п при
соответствующем выборе знаков + или — имеем
=±Pt±P,±...± p2n-t
Например, рг ~ р\ + рг — р3 — Pi + Рь + Рб, или 17 =
= 2 + 3 — 5 — 7+ 11 + J3.
А. Шинцель доказал, что если а и b — положитель-
положительные числа, причем а<Ь, то существуют простые уисла
р и q такие, что а < -^ < Ь.
Можно доказать, что для каждого вещественного
положительного х последовательность с общим членом
Ас(лг)
—-— стремится к х, когда п неограниченно возрастает.
Доказано, что существует бесконечное множество
простых чисел р таких, что последующее простое число
ближе к числу р, чем простое число, предшествующее
ему, а также таких, что предшествующее простое число
ближе к числу р, чем простое число, следующее после
р. Иными словами, доказано, что существует бесконеч-
бесконечное множество натуральных чисел п таких, что
Pn+i —Рп < Р„ —Pn-v т. е. рп > Ря^Ря+1 . а также,
что существует бесконечно много натуральных чисел п
таких, чторп< Рп-* +
Но мы не знаем, существует ли бесконечное множе-
множество таких я, для которых Р„= Pn-l~^Pn+l . Выска-
Высказано предположение, что ответ на этот вопрос должен
быть положительным. Так, например, мы имеем
Pn = Issd±£n±L дЛЯ я =16, 37, 40, 47. 55, 56. 240, 273.
П. Эрдеш и П. Туран доказали, что существует бес-
бесконечно много натуральных чисел п- таких, что
Р\>Рп-\Рп+\, и бесконечно много п таких, что рп<
<Pn-lPn+l-
Доказано, кроме того, что pn+i < Pn-i + Рп для п —
-. 3, 4, 5, ...
Для последовательных простых чисел имеет место
также следующая теорема (доказательство которой
хотя и не трудное, но довольно длинное):
31
5 В Серпииский

Для каждого натурального m существует натураль-
натуральное число п такое, что
± + ±+...+±>т.
Р\ Рг Рп
(Уже для т = 10 и составляло бы несколько десятков
тысяч.)
Ау>жяо указать четыре последовательных простых
числа, дающих две пары чисел близнецов, например
11, 13, 17, 19 ил'и 179, 181, 191, 193. Если такой комп-
комплекс составлен из простых чисел р, р + 2, р + 6 н р +
+ 8, то мы говорим, что имеется четверка. В первом
из указанных здесь примеров мы имеем четверку, а во
втором нет. Друтие примеры четверок мы получаем для
р = 5, 101, 191, 821, 1481, 3251. Высказано предположе-
предположение, что четверок существует бесконечно много.
В первых десяти миллионах, как подсчитал В. А. Го-
Голубев в 1959 г., имеется 899 четверок, в первых же пят-
пятнадцати миллионах — 1209. Самая далекая четверка,
известная в настоящее время, была указана А. Ферье.
Она получается при р = 2863308731.
12. Многочлены и простые числа
Напрашивается вопрос, существует ли многочлен
f(x) от переменной х с целыми коэффициентами, кото-
который для каждого натурального значения х дает простое
число f(x). Докажем, что такого многочлена нет. Пусть
есть многочлен степени т с целыми коэффициентами
at, at, ..., От, где оо Ф 0. Если бы мы взяли сц, <0, то
для достаточно больших х было бы f (х) < 0, поэтому
будем предполагать, что а9 > 0. Тогда, как известно,
существует такое целое число -к©, что п = f(x0) > 1 и
f Iх) > f&o) для х > xq.
Докажем, что при любом натуральном k число
f(xo + kn) будет составным. Пусть х и h — натураль-
натуральные числа, тогда при всяком натуральном * число
(x+h)*—xi делится на (x+h) — x = h, откуда следует,
что числа, щ(х + Л)**~* — щх"-* для i = 0,1,2, ,.., т
делятся на h и, зяачят, число f{x + h) — f(x) также
делится на Л. Но в таком случае f(Xo k/
32

делится на kn, или f(xa~+kn)—л = in, . что дает
/(*в+&я)= (t+l)n и доказывает, что число }(Хо+кп),
которое, как мы знаем, >f(x&) = nt делится на нату-
натуральное число п > 1 и, следовательно, является состав-
составным, что и требовалось доказать.
Итак, мы доказали, что если f(x) есть многочлен с
целыми коэффициентами, где коэффициент при высшей
степени х — число положительное, то для бесконечного
множества натуральных чисел х число f(x) является
составным.
Однако мы знаем такие многочлены, которые для
многих последовательных натуральных чисел х прини-
принимают значения, являющиеся простыми числами. Приме-
Примером такого многочлена может служить многочлен Эй-
Эйлера х2 + х + 41, который для х — 0, 1, 2, ..., 39 дает
разные простые числа. Высказано предположение, что
существует бесконечно много натуральных чисел х, для
которых х2 + х + 41 есть простое число.
Мы не знаем, существует ли такое натуральное число
а > 41, чтобы каждое из чисел хг + х + а для х =
= 0, 1, 2, ..., а — 2 было простым. Во всяком случае
таких чисел а <Л0® не существует.
Многочлен х2 — 79х + 1601 дает простые числа для
х — 0, 1, 2, ..., 79, однако эти числа не все разные.
Возникает вопрос, существуют ли многочлены, ко-
которые для натуральных значений переменной дают
бесконечное множество простых чисел. Очевидно, суще-
существуют такие многочлены первой степени, например
многочлен 2х+1, но мы не знаем ни одного такого много-
многочлена степени >1. Мы не знаем, является ли таким дву-
двучлен х2 + I, дающий простые числа для х — 1, 2, 4, 6,
10. Подсчитано, что для я <110 000 есть 842 простых
числа вида х2 + 1 (где х — натуральное число); для х-^
< 100000 есть 6656 таких чисел, для .* < 180000 их
11 223. Высказано предположение, что для каждого на-
натурального числа k существует бесконечно много про-
простых чисел вида х2 + k, где х есть натуральное число.
Существует, очевидно, только одно простое число
вида х3 + 1, где х — натуральное число, однако выска-
высказано предположение, что существует бесконечно много
простых чисел вида х3 + 2, а также вида х3 — 2, где
х — натуральное число (простые числа получаем при
х = 1, 3, 5, 29 и х — 9, 15, 19, 27 соответственно).

В 1962 г. Б. М. Бредихин доказал, что существует
бесконечно много простых чисел вида х2 + у2 + 1, где
х и у — целые числа. Можно доказать (хотя это и труд-
трудно), что существует бесконечиое множество простых чи-
чисел вида x2 + y2 + z2+\, где х, у, г — натуральные
числа. Позднее (в § 19) мы докажем, что существует
бесконечно много простых чисел вида х2 + у2, где х и
у — натуральные числа. Мы не знаем, существует ли
бесконечное множество простых чисел, являющихся
суммами кубов трех целых чисел.
13. Арифметические прогрессии,
образованные из простых чисел
Доказано, что существует бесконечно много арифме-
арифметических прогрессий, образованных из трех разных про-
простых чисел. Мы знаем много прогрессий, образованных
из трех различных простых чисел, первыми членами ко-
которых является число 3, например: 3, 7, 11; 3, 11, 19; 3,
13, 23; 3, 17, 31; 3, 23, 43; 3, 31, 59; 3, 37, 71; 3, 41, 79;
3, 43, 83. Однако неизвестно, существует ли их беско-
бесконечно много.
Легко доказать, что не может быть арифметической
прогрессии, образованной из трех разных простых чи-
чисел, первым членом которой было бы число 2 (так как
третий член последовательности был бы четный >2).
Высказано предположение, что существует бесконечно
много арифметических прогрессий, образованных из
трех простых чисел, первым членом которых является
любое простое нечетное число.
Существует только одна арифметическая прогрессия
с разностью 2, составленная из трех простых чисел,
именно: 3, 5, 7 (так как из трех последовательных не-
нечетных чисел одно всегда делится на 3), а также толь-
только одна такая арифметическая прогрессия с разностью
4, именно: 3, 7, 11. Очевидно, не может быть арифмети-
арифметических прогрессий, составленных из трех простых чисел,
с нечетной разностью. Высказано предположение, что
существует бесконечно много прогрессий с разностью 6,
образованных тремя простыми числами. Таковыми яв-
являются, например, прогрессии: 5, 11, 17; 11, 17, 23; 17,
23, 29. Имеется также прогрессия с разностью 6, обра-
34

зованная из пяти простых чисел: 5, 11, 17, 23, 29. Одна-
Однако она является единственной, так как в каждой про-
прогрессии с разностью 6, составленной из пяти натураль-
натуральных чисел, один из членов должен делиться на пять.
Напрашивается вопрос, существует ли арифметиче-
арифметическая прогрессия, состоящая из любого числа разных
простых чисел. Среди известных нам наибольшую дли-
длину имеет прогрессия, состоящая из 12 членов. Эта про-
прогрессия была найдена В. А. Голубевым, ее первый член
23143, а разность 30030.
Мы не знаем, существует ли арифметическая про-
прогрессия, образованная из ста разных простых чисел.
М. Кантор доказал, что в арифметической прогрессии,
составленной из п > 1 простых чисел, больших я, раз-
разность прогрессии должна делиться на каждое простое
Число <;«. Отсюда следует, что если существует ариф-
арифметическая прогрессия, образованная из ста разных про-
простых чисел, то разность ее должна быть огромным чис-
числом, имеющим по крайней мере несколько десятков
цифр.
Высказано предположение, что если г есть нату-
натуральное число, делящееся на каждое простое число <и
(где п — заданное натуральное число > 1), то суще-
существует бесконечно много арифметических прогрессий с
разностью г, "образованных из и последовательных про-
простых чисел. Например, 47, 53, 59 есть арифметическая
прогрессия с разностью 6, образованная тремя после-
последовательными простыми числами. Другими такими про-
прогрессиями являются 151, 157, 163; 167, 173, 179. Мы
знаем также арифметические прогрессии с разностью 6,
образованные из четырех последовательных простых
чисел, например, 251, 257, 263, 269 или 1741, 1747, 1753,
1759.
14. Малая теорема Ферма
Теорема 9. Если р— простое число, то для каж-
каждого целого числа а число up — а делится на р.
Доказательство. Пусть р — данное простое чи-
число. Теорема, очевидно, справедлива для числа а = 1
Предположим, что она справедлива для некоторого
35

натурального числа а. Согласно формуле Ньютона для
двучлена, имеем
0)
где для k = I, 2, ..., р — 1
p{p-D(p-2)...(p-k+l)
1-2... ft
причем, как известно, числа (£] являются целыми. От-
Отсюда мы заключаем, что число 1 • 2 ... k • (£\ делится
на р и, следовательно, согласно следствию теоремы 7,
по крайней мере одно нз чисел 1, 2, ..., *>(^} должно
делиться на р. Но так как к < р, то ни одно из чисел
1, 2, ..., k не делится на р, следовательно, на р должно
делиться число (^1- Отсюда, учитывая A), мы заклю-
заключаем, что число (а + \)р — аР— 1 делится на р. При-
Прибавив к нему число а? — а, делящееся на р (так
как мы предполагаем, что теорема справедлива для
числа а), мы обнаружим, что число (а + 1)р— (а + 1)
делятся на р, т. е. что теорема справедлива для числа
а+ 1.
Таким образом, мы доказали посредством индукции,
что теорема справедлива для каждого натурального
числа а. Для числа 0 она, очевидно, также верна.
Если а — целое отрицательное число, то при р = 2
имеем а2 — а = а (а— 1), и так как из двух последова-
последовательных целых чис^л а — 1 и а одно всегда четное, то
всегда 2Ia2-^-a'). Далее, прн р простом нечетном имеем
(—а)р = —аР, и поэтому (—а)р—(—а) =—(а? — а).
Следовательно теорема справедлива и для целых отри-
отрицательных чисел а. Таким образом, теорема 9 доказана
полностью.
В качестве частного случая теоремы 9, для а = 2,
мы получаем теорему, согласно которой для любого
простого числа р число 2р — 2 делится на р. Возникает
■) Символ r/s означает, что число $ делится на г. Читается так:
«■ делит s».
36

вопрос, будет ли верна обратная теорема, т. е. если я —■
натуральное число > 1, такое, что я|2п— 2, то должно
ли п быть простым числом?
Для многих предполагаемых теорем, относящихся к
простым числам, производилась проверка на большом
числе частных случаев. Если бы мы проверили, напри-
например, все последовательные натуральные числа >1 и
■< 300, то обнаружили бы, что каждое такое натуральное
число п, для которого 2П — 2 делится на я, является
простым числом. Быть может, именно этот путь при-
привел китайцев 25 веков назад к теореме, согласно кото-
которой, если для натурального числа п > 1 число 2" — 2
делится на я, то число я простое. Однако эта теорема
оказалась ложной, ибо число 2341 — 2, как мы сейчас
покажем, делится на 341, а число 341 = 11-31 является
составным.
В том, что число 2341 — 2 делится на 341, мы можем
убедиться следующим образом. Очевидно, 2341 — 2 =
= B31I1 —2"+ 211 —2. Число 210— 1 = 1023 = 3-341
делится на 341. Значит, и число B10K—1 также де-
делится на 341 (так как для натуральных а, Ь, и k число
ак — bh, как известно, делится на а — Ь). Числа 2" — 2=»
= 2B'°—1) н 231 —2 = 2[B10K —1] делятся на 341,
откуда следует, что и число B31I1 — 2" делится на 341.
Отсюда, в силу нашего равенства для числа 2341 — 2,
тотчас же получаем, что это число делится на 341, что
и требовалось доказать.
Естественно, возникает вопрос, существует ли бес-
бесконечно много натуральных чисел я, для которых ки-
китайская теорема неверна. Чтобы доказать, что ответ на
этот вопрос является утвердительным, достаточно (имея
в виду, что составное нечетное число 341 не удовлетво-
удовлетворяет теореме) доказать, что для каждого составного
нечетного числа я, не удовлетворяющего указанной тео-
теореме, существует составное нечетное число, большее а
также не удовлетворяющее ей.
Итак, предположим, что нечетное составное число
п = ab, где а и b — натуральные числа >1, не удовле-
удовлетворяет китайской теореме и, значит, я|2п — 2. Число
т — 2П — 1 = B°)ь — 1 есть нечетное составное, так
как оно делится на число 2°—1, большее 1 (ибо а>
i>1) и меньшее чем m (ибо Ь > 1), причем т> п
[(ибо я>1). Таким образом, достаточно еще только
37

показать, что т]^ — 2. Мы имеем я|2п — 2, но я есть не-
нечетное число, следовательно, Я12"-1—1, т. е. 2п~1 — 1 =>
■= kn, где k — натуральное число. Отсюда 2*"-' *=
=22B"~1-1)=» 22Й» => B»)». Число 2"»-1 —1 =» B«)»— I,
таким образом, делится на число 2" — 1 =« т. Следова-
Следовательно, и число 2т — 2 делится на т, и, значит, состав-
составное число т не удовлетворяет китайской теореме, что
и требовалось доказать.
Возникает также вопрос, существуют ли составные
четные числа, не удовлетворяющие китайской теореме.
Только в I960 г. Д. X. Лемер нашел такое число: 161 038.
Нахождение этого числа было очень сложным делом,
проверить же, что оно является делителем числа
216Ю38 — 2, нетрудно. Легко проверить, что 161038 =
= 2-73-1103, 161 037 = 32-29-617, 29—1 -7-73, 229 —
— 1 = 1103-486 737, откуда следует, что число 2161037 —
— 1 делится на 29— 1 и 2е— 1, а значит, также на 73
и 1103. Таким образом, число 2161038 — 2 делится на 2,
73 и 1103, а так как эти числа являются разными про-
простыми числами, то 2161038 — 2 делится на их произведе-
произведение, т. е. на число 161 038, что и требовалось доказать.
В 1951 г. Н. Г. В. X. Биджер доказал, что суще-
существует бесконечно много четных чисел я, для которых
число 2П — 2 делится на я.
Доказано также, что существует бесконечно много
пар разных простых чисел р и д таких, что число 2?' —
— 2 делится на pq. В 1958 г. А. Шинцель доказал, что
для любого целого числа а и любого натурального m
существуют разные простые числа р > т и q > m та-
такие, что pq\aP4 — а.
В связи с ложностью китайской теоремы напраши-
напрашивается вопрос, существуют ли составные числа я такие,
что для каждого целого а число ап—а делится на п.
Такие составные числа я мы называем абсолютно
псевдопростыми1). Высказано предположение
(до сих пор не доказанное), что таких чисел имеется
бесконечно много. Наименьшее из них есть число 561 =
= 3-1Ы7.
Чтобы доказать, что число 561 есть абсолютно псев-
псевдопростое, достаточно доказать, что для всех целых а
') Название псевдопростые оставлено для составных чи-
чисел п, для которых число 2" — 2 делится на п.
38

число а561 — а делится на каждое из простых чисел
3, 11, 17.
Число а581 — а, очевидно, делится на 3, если а де-
делится на 3. Если же а не делится на 3, то а есть число
вида 3£±1, откуда а2 — 1 «. Ck ± IJ — 1 = 3C* ±
±2)*, следовательно, 3|а2—1; отсюда 3|а2280—1,
а значит, и 31а581 — а.
Число а561 — а, очевидно, делится на 11, если число
а делится на 11. Согласно теореме Ферма, для всех це-
целых а имеем 11\аи — а = а(а10 — 1), так что если число
а не делится на И, то отсюда вытекает, что 11|а10 — 1
и, следовательно, 111а10'58—1, откуда уже заключаем,
что 11|а561—а.
Число а581—а делится на 17, если число а делится
на 17. Согласно теореме Ферма, для всех целых а имеем
17|а" — а. Поэтому если число а не делится на 17, то
отсюда вытекает, что 17|а16 — 1, откуда 17|а16>35—1
и, значит, 17|аИ1 — а (ибо 16-35+ 1 =561). Итак, мы
доказали, что число 561 является абсолютно псевдо-
псевдопростым.
Числами абсолютно псевдопростыми являются также
5-29-73, 7-13-31, 7-23-31, 7 • 31 • 73.
13-37-61, 5-17-29-113-337-673-2689;
известно и много других таких чисел.
Из малой теоремы Ферма вытекает, что если р—
простое число >2, то число 2р~1 — 1 делится на р. Воз-
Возникает вопрос, существуют ли простыв числа р, для ко-
которых 2р~1 — 1 делится на р2. Мы знаем только два та-
таких простых числа р, именно 1093 и 3511, и зиаем, что
нет других таких простых чисел />< 100000; но мы не
знаем, существуют ли такие числа, превосходящие
100 000, и конечно ли их количество. Мы не знаем так-
также, существует ли бесконечно много простых чисел та-
таких, для которых число 2р-' — 1 не делится на р2.
Из теоремы Ферма легко вытекает, что если р —
простое число, то число I?-1 + 2р-'+ Зр-1-f-... +
+ (р — 1) р-' + 1 делится на р. Г. Джуга высказал
в 1950 г. предположение, что эта делимость имеет ме-
место только для простых чисел, и проверил его для всех
чисел ^10100°

15. Доказательство теорем, согласно которым имеется
бесконечно много простых чисел каждого из видов
4Л + 1, 4Л+3 и 6Л + 5
Пусть п означает любое натуральное число >1. То-
Тогда число га! есть число четное, а нечетное число (я?J +
+ 1 как число, большее единицы, согласно теореме 1,
имеет простой делитель р, очевидно, нечетный и, сле-
следовательно, имеющий вид 4k + 1 или 4k + 3 (где k —
целое число), причем р > га. Предположим, что р =
= 4£ + 3. Очевидно, мы имеем (га!J +J\(n\)Wh+» + 1,
ибо, как известно, для натуральных а и нечетных т
число ат + 1 делится на а + 1 (причем ат + 1 = (а +
,+ 1) (а1»-1 — а™-2 + ... — а + 1). Так как 2B* + 1) =
= 4£ + 2 = р— 1, то, учитывая, что pl(n!J+l, мы
можем заключить, что р1(я!)Р~' + 1 и, следовательно,
р\(п\)р + п\. Но, согласно теореме Ферма, р|(и!)р — га!.
Отсюда р|2л!, что невозможно, так как р есть простое
нечетное число >«. Следовательно, р должно быть
числом вида 4& + 1. Таким образом, мы доказали, что
для каждого натурального числа п > 1 существует про-
простое число >я, имеющее форму 4k +. 1 (и что таким
числом является каждый простой делитель числа
(я!J + 1). Тем самым доказана
Теорема 10. Простых чисел вида 4k + I имеется
бесконечно много.
В связи с нашим доказательством напрашивается
вопрос, для каждого ли простого числа р вида 4й + 1
существует натуральное число п такое, что p|(n!J+ U
(Например, имеем: 5|B!J + 1, 13|F!J+1). Можно
показать (см. § 19), что если р есть простое число вида
4k + 1, то р\ [(нг^)!]2 + 1- Следовательно, 17|(8!J +,
+ 1, 29|A41)».+1, 37|A8!J+; 1.
Возникает также вопрос, сколько имеется простых
чисел вида 4k + 3. Доказательство того, что их беско-
бесконечно много, опирается иа следующую лемму.
Лемма. Каждое натуральное число вида 4k + 3
имеет по меньшей мере один простой делитель того же
вида.
Доказательство. Пусть я = 4k +■ 3. Это число
имеет, очевидно, натуральные делители вида 4t+3 (где
40

t есть целое число), так как само является одним из
них. Обозначим через р наименьший из таких делите-
делителей. Ясно, что р> 1. Если бы р было числом состав-
составным, мы имели бы р = ab, где а и Ь были бы натураль-
натуральными числами > 1 и меньшими р, причем нечетными,
так как р, будучи числом вида 4k + 3, есть число нечет-
нечетное. Оба числа а и Ь не могут быть вида 4t + 1, так как
тогда их произведение р = ab = Dti + 1) Dt2 + 1) =
= 4D/i^2 + *i + *г) + 1 было бы вида М + 1, что ис-
исключено. Следовательно, по крайней мере одно из чи-
чисел о и 6 есть число вида 41 + 3. Так как делители р
являются одновременно делителями я, то п будет иметь
натуральный делитель вида М + 3, меньший р, что про-
противоречит определению числа р. Итак, р — простое
число. Таким образом, лемма доказана.
Пусть теперь п обозначает любое натуральное чис-
число. Число 4я! — 1 есть, очевидно, натуральное число
вида 4k + 3. Согласно лемме, оио имеет по крайней
мере один простой делитель р вида М + 3. Здесь долж-
должно быть р > л, так как число 4я! — 1, делясь на р, оче-
очевидно, ие делится ни на одно натуральное число >1 и
<7i. Итак, мы доказали, что для каждого натурального
числа п существует простое число >я, имеющее вид
4k + 3.
Таким образом, доказана
Теорема 11. Простых чисел вида 4k + 3 имеется
бесконечно много.
Обозначим для вещественного числа х через tci(jc)
число простых чисел вида 4k + 1, не больших чем х,
а через тсз(х) — число простых чисел вида 4& + 3, не
больших чем х. Например, tci(IO) = 1; тсзA0) =2;
и,A7) =язA7) -3; u,A00) = 11, «3A00) = 13. Прове-
Проверено, что wi(jc) <из(л:) для х<26861. Однако было бы
ошибочно думать, что всегда тс\(х) <из(х), ибо, как
установил Дж, Лич в 1957 г., для х — 26 861 tci(jc) =
= 1473, а я3(х) = 1472.
Уже в 1914 г. Литтлвуд доказал, что существует
бесконечное множество натуральных чисел х, для кото-
которых тц(х) >т3(х), а также бесконечное множество на-
натуральных х, для которых ui(x) <тсз(х). Мы видим,
таким образом, какими ненадежными могут быть ги-
гипотезы относительно простых чисел, если они выдви-
выдвигаются даже иа основании большого числа наблюдений.
41

Теоремы 10 и 11 можно сформулировать следующим
образом.
Каждая из арифметических прогрессий
1, 5, 9, 13, 17, 21, ...
3, 7, 11, 15, 19, 23, ...
содержит бесконечно много простых чисел.
В связи с этим напрашивается вопрос: какие бес-
бесконечные арифметические прогрессии, составленные из
натуральных чисел, содержат бесконечно много про-
простых чисел?
Пусть дана бесконечная арифметическая прогрес-
прогрессия
а, а + г, а + 2г
у которой первый член а и разность г — натуральные
числа.
Если а и г имеют общий делитель d> 1, то, оче-
очевидно, каждое из чисел нашей последовательности бу-
будет делиться иа d и поэтому, как легко видеть, ни один
член прогрессии, кроме, быть может, первого члена, не
будет простым числом. Отсюда следует: для того что-
чтобы арифметическая прогрессия с первым членом а и
разностью г содержала бесконечное число простых чи-
чисел, необходимо, чтобы а и г не имели общего дели-
делителя, большего 1. Как доказал еще в 1837 г. П. Г. Ле-
жен Дирихле, это условие является также и доста-
достаточным.
Доказательство теоремы Дирихле, хотя позднее и
было упрощено различными авторами, является слож-
сложным и длинным. Не менее сложно доказательство тео-
теоремы о том, что в каждой арифметической прогрессии,
первый член и разность которой суть натуральные
числа, не имеющие общего делителя, большего еди-
единицы, найдется по крайней мере одно простое число.
Можно было бы подумать, что последняя теорема сла-
слабее теоремы Дирихле, однако нетрудно доказать, что
она равносильна ей. ">
Некоторые частные случаи теоремы Дирихле (так
называемой теоремы об арифметической прогрессии)
могут быть доказаны просто. Дадим, например, дока-
42

зательетво для случая и — 5, г — 6, для чего рассмот-
рассмотрим следующую лемму.
Лемма. Каждое натуральное число вида 6ft H-5
имеет по крайней мере один простой делитель того же
вида.
Доказательство этой леммы совершенно аналогично
доказательству леммы о числах вида 4ft + 3, с той
лишь разницей, что вместо формы 4£ + 3 берем форму
6ft -f 5, а затем иепользуем замечание, что число вида
6* + 5, как. не делящееся на 2 и 3, может иметь дели-
делители только вида Ы + 1 или Ы + 5, а также что произ-
произведение двух чисел вида Ы + 1 есть число того же вида.
Для доказательства самой теоремы возьмем какое-
нибудь натуральное число п. Тогда число &п\ — 1 бу-
будет, очевидно, вида 6ft -f 5 и, согласно лемме, будет
иметь простой делитель р того же вида, причем, как
легко показать, р> п. Итак, для каждого натурального
числа п существует простое число р> п, имеющее
форму 6ft + 5. Отсюда следует '
Теорема 12. Простых чисел вида 6ft + 5 имеется
бесконечно много.
Итак, арифметическая прогрессия 5, 11, 17, 23, 29,
35, ... содержит бесконечно много простых чисел. Сле-
Следовательно, арифметическая прогрессия
2, 5, 8, 11, 14, 17, 20, ....
включающая в себя все члены первой прогрессии, и по-
подавно содержит бесконечно много простых чисел, т. е.
существует бесконечное множество простых чисел вида
ЗА: + 2.
Существуют еще некоторые другие арифметические
прогрессии, относительно которых можно легко дока-
доказать, что они содержат бесконечно много простых чи-
чисел. Таковой является, например, прогрессия 8ft + 1
(где k = 1, 2, 3, ...).
16. Некоторые гипотезы относительно простых чисел
Пусть теперь п — данное натуральное число >1.
Расположим натуральные числа 1, 2, 3, ..., п2 в п строк
43

по « чисел в каждой строке, т. е. составим таблицу
1, 2, ..., k, ..., а,
. .... 2я,
, .... 3»,
(n— l)n -f- 1, ..., (п—1)п + Л, ..., л2
Столбцы этой таблицы образуют арифметические про-
прогрессии (с га членами). А. Шницель высказал предпо-
предположение, что если k есть натуральное число <я, не
имеющее общего с п делителя >1, то k-й столбец на-
нашей таблицы содержит по меньшей мере одно простое
число. А. Горжелевский проверил это предположение
для всех натуральных чисел л<100.
В. Серпинский высказал предположение, что ка-
каждая строка рассматриваемой таблицы (где п > 1) со-
содержит по меньшей мере одно простое число. Это пред-
предположение было проверено А. Шницелем при помощи
таблиц А. Вестерна и Д. X. Лемера для всех п-<4500.
Первая строка таблицы (для п > 1) содержит всегда
простое число 2. Утверждение о том, что вторая строка
таблицы содержит по крайней мере одно простое число,
как легко видеть, равносильно теореме Чебышева и,
следовательно, справедливо. Доказано также, что для
я>-3 третья строка таблицы содержит по крайней мере
одно простое число, иными словами, что (для гО>3)
между 2п и 3/г лежит хотя бы одно простое число (что
справедливо также для п = 2). Вообще доказано, что
для п^-9 каждая из девяти первых строк таблицы со-
содержит по крайней мере одно простое число.
Так как двумя последними строчками таблицы
являются
(tt-lf, (Я-1J+1 ГР — П,
п2 — п-\-\, п.2 — я + 2, ..., п2,
то из предположения В. Серпинского вытекает, что ме-
между каждыми двумя последовательными квадратами
натуральных чисел лежит по меньшей мере два про-
простых числа. Далее, так как легко доказать, что если
44

m — натуральное число, то существует натуральное
число п такое, что
/гс3<(я—IJ и да<(да+1У»,
то из предположения В. Серпинского следует, что ме-
между каждыми двумя последовательным» кубами нату-
натуральных чисел содержится по крайней мере два про-
простых числа. Мы не знаем, справедливо ли это, однако
доказано, что для достаточно больших натуральных чи-
чисел m между т3 и (т + IK содержится произвольно
много простых чисел.
Упомянем здесь еще о том, что, как заметил Лади-
слав Скуля, из предположения относительно рассмат-
рассматриваемой таблицы (для л = 2, 3, ...) следует, что как
(я + 1)-я, так и (п -ь2)-я строки содержат хотя бы по
одному простому числу (или что для натуральных л >
> 1 каждая из последовательностей я2 + 1, я* + 2, ...,
п7 + п и л2 + л + 1, я2 + л + 2, ..., п г + 2п содержит
по крайней мере одно простое число). Для (л + 3)-и
строки это, вообще говоря, неверно. Например, при я =
= 2 или при л = 4 получаются последовательности 9,
10 н 25, 26, 27, 28, не содержащие ни одного простого
числа.
Из предположения относительно рассматриваемой
таблицы можно также легко вывести, что если все на-
натуральные числа выписывать последовательно в строчки
по я чисел в и-й строке, т. е. если составить бесконеч-
бесконечную треугольную таблицу
1
2
4
7
11
3
5
8
12
6
9
13
10
14 IS
то в каждой строке этой таблицы, начиная со второй,
найдется по крайней мере одно простое число. Мы не
знаем, справедливо ли это утверждение.
17. Теорема Лагравжа
Теорема 13. Если р — простое число и
1х'"-Ч- ... -\-an.lX-\-an A)
45

есть многочлен степени «>1 с целыми коэффициента-
коэффициентами, где коэффициент а0 при высшей степени х не де~
лится на р, то среди чисел
х = 0, 1, 2, 3 р — \ B)
существует не более чем п таких, для которых число
f(x) делится на р.
Доказательство. Теорема справедлива для мно-
многочленов степени 1. В самом деле, если бы среди чисел B)
было по меньшей мере два различных числа х\ и х2 >
> х\ таких, что p\f{x\) и p\f(x2), то мы. имели бы
P\f(*2) — f(*i), а так как f(x) = айх + а\, то мы имели
бы р\ао(х2 — Xi), где дс2 — хи будучи разностью двух
различных чисел последовательности B) и, значит,
меньших р, не делится на р. Следовательно, р было бы
делителем произведения двух натуральных чисел, не де-
делящихся на р, что противоречит теореме 7.
Пусть теперь п — некоторое натуральное число >1.
Предположим, что теорема справедлива для многочле-
многочленов степени п— 1, и допустим при этом, что для некото-
некоторого многочлена A) степени п теорема Лагранжа не-
неверна, т. е. что существует набор целых чисел хи х2, ■ ■.,
*п+ь где 0<*i <х2 < ... <*n+i <р, таких, что
p\f{xt) для i = 1, 2 п+ 1.
Имеем/(*)-/(*,) = а0(*«-*?)-М,^"-1-*«-')+ ...
... -\-ап-\(х — JC]). Отсюда, так как хк — х* = (я—я,) X
X^-' + Jt,**-2-!- ... +х*-Ч + х*-1) для £=2, 3, .... л.
то мы легко найдем, что
/(*)-/(*,) = (*-*,)/!(*), C)
где fi(x) —многочлен степени п— 1с целыми коэффи-
коэффициентами (зависящими от а0, аи ..., ап и xi), причем
коэффициентом при дс" будет ао, т. е. число, не деля-
делящееся на р.
На основании тождества C), мы получим
) D)
для i = 2,3, .,., п+1.
Но из того, что p\f(Xi) для i = 1, 2, .'.., п + 1, сле-
следует, что
P\f(xd— /C*i) Аля i=z2> 3» •••»
46

значит, согласно D), имеем:
p\(Xi — jc,)/,(.x,) для i = 2, 3, ...,
а так как числа х{— х, для i = 2, 3, .... п+1 не де-
делятся на р, то, в силу теоремы 7, должно быть
p\A(xt) для 1 = 2, 3, .... д+1,
вопреки предположению, что теорема справедлива для
многочленов степени п—1.
Следствие. Если р есть простое число, а A) —
многочлен степени п с целыми коэффициентами, и если
существует более чем п натуральных чисел х < р, для
которых f(x) делится на р, то see коэффициенты много-
многочлена A) делятся на р.
Доказательство. Предположим, что многочлен
A) удовлетворяет условию следствия, но не все коэф-
коэффициенты его делятся на р. Пусть ап_ь есть первый по
порядку коэффициент, не делящийся на р. Предполо-
Предположим, что k > 0. Для каждого натурального х, для кото-
которого f(x) делится на р, очевидно,
также делится на р. Таким образом, для многочлена
g(x) степени k существует более чем п и, так Как &<п,
более чем k натуральных чисел х < р, для которых
p\g(x), что противоречит теореме Лагранжа (примени-
(применимой, так как ап-к не делится на р). Итак, предположим,
что &=0, т.е. что все коэффициенты многочлена A), кро-
кроме ап, делятся на р. Но тогда, поскольку существует число
х, для которого f (x) делится на р, мы, исходя из форму-
формулы A), должны будем заключить, что р\ап. Таким об-
образом, предположение, что наше следствие несправед-
несправедливо, в каждом случае приводит к противоречию.
18. Теорема Вильсона
Дадим теперь одно важное применение доказанного
в § 17 следствия. Пусть р — простое число и пусть
47

есть многочлен степени р— 2 с целыми коэффициента-
коэффициентами. Для *= 1, 2, .... р — 1, согласно теореме Ферма,
мы имеем р\хр — х = х(хр~1 — 1), откуда р\хР~1 — \-
Но для х = 1, 2, ..., р—1 мы, очевидно, также
имеем
р\(х-\){х~2) ... (х-р + \),
так как для таких х один из сомножителей рассматри-
рассматриваемого произведения равен нулю. Учитывая, что раз-
разность двух чисел, делящихся на р, делится на р, мы за-
заключаем, что p\f(x) для х = 1, 2, .... р— 1.
Таким образом, согласно следствию теоремы Ла-
гранжа (для п = р— 2), мы можем заключить, что все
коэффициенты нашего многочлена, а значит, и его сво-
свободный член делятся на р.
Но для нечетных р (так как (—I)*" = 1) свобод-
свободным членом многочлена {(х) является число 1-2-3 ...
... (р—1) + 1 или (р—1)! + 1. Следовательно, если
р есть простое нечетное число, то р|(р— 1)! + 1, что,
впрочем, справедливо и для р = 2, так как 11 + 1=2.
Таким образом, доказана
Теорема 14 (Вильсона). Для каждого простого
числа р число (р —1I + 1 делится на р.
Следует заметить, что если для натурального числа
п > 1 число (п— 1)! + 1 делится иа п, то п должно
быть простым числом. Действительно, если бы п было
составным, то в силу того, что п = ab, где а и Ь — на-
натуральные числа >1 и <п, число а было бы одним из
сомножителей произведения 1-2... (п—1) и, следо-
следовательно, число (п—1)! + 1 при делении иа а давало
бы в остатке 1, между тем как, делясь иа п, оно и по-
подавно должно делиться на а. Полученное противоречие
доказывает, что число п должно быть простым.
Итак, для того чтобы натуральное число п > 1 было
простым, необходимо и достаточно, чтобы число (п —
— 1)! + 1 делилось на п.
Таким образом, теоретически мы можем при помо-
помощи только одного деления выяснить, является данное
число простым нлн нет. Однако практически пользо-
пользоваться этим способом неудобно, так как уже для трех-
трехзначных п число (п —1I + 1 имеет более чем сто цифр.

В связи с теоремой Вильсона возникает вопрос, воз-
возможны ли такие простые числа р, для которых (р —
— 1I + 1 делится на р2. Оказывается, для р^ЗОООО
имеется три таких числа: 5, 13 и 563. Мы не знаем, су-
существует ли бесконечно много таких чисел р.
Теоремы Ферма и Вильсона можно соединить в
одну следующую теорему:
Если р — простое число, то для любого целого чи-
числа а число аР + (р — 1)!а делится на р.
В самом деле, если р—простое и а — произвольное
целое число, то, согласно теореме Ферма, число а? — а
делится на р, а так как, согласно теореме Вильсона, чи-
число а + (р—1)!а = [1 + (р — 1)!]а делится на р, то и
сумма этих чисел, т. е. число а? + (р — 1)!а также де-
делится иа р. С другой стороны, если ар + (р— 1)!а де-
делится на р при любом целом а, то при а — 1 мы полу-
получаем отсюда теорему Вильсона, из которой следует, что
при любом целом а р\(р—1)\а + а, а так как р|ар +
+ (р—1)!а, то р\аР + (р— 1)!а — [(р— 1)!а + а), т. е.
p\av — а, что дает теорему Ферма.
Легко также доказать, что теоремы Ферма и Виль-
Вильсона можно соединить и в следующую теорему:
Если р — простое число, а — целое число, то число
(р— 1)\ар + а делится на р (Лео Мозер).
Из теоремы Вильсона вытекает
Теорема IS (Лейбница). Для того чтобы натураль-
натуральное число р > 2 было простым, необходимо и достаточ-
достаточно, чтобы число (р — 2) I — 1 делилось на р.
Доказательство. Если число р > 2 является
простым, то, согласно теореме Вильсона, число (р —
>—1)!+ 1 делится на р. Учитывая, что (р—1)! = (р—•
■—2)! (р — 1), мы имеем (р—1)! + 1 «= (р —2)!р —
— [(р — 2)! — 1], откуда видно, что число (р — 2)!—L
делится на р.
С другой стороны, если р\(р — 2)! — 1, то р\(р~-
— 1)!—(р—1) и поэтому р|(р—1)! + 1, откуда (на-
(напомним, что р >2), как было уже доказано выше, сле-
следует, что р должно быть простым числом. Таким обра-
образом, теорема Лейбница доказана.
Если р есть простое число >3, то (р — 1)!>р, ибо
тогда (р—1)!>2(р— 1) = р + (р — 2)>р. Поэтому
число (р—1)! + 1, как число, большее р и, согласно

теореме Вильсона, делящееся на р, является числом со-
составным.
Итак, если р>3 есть простое число, то (р— 1)! + Г
есть число составное. Отсюда следует, что существует
бесконечное множество натуральных чисел п, для ко-
которых число п! + 1 является составным. Существует ли
бесконечное множество натуральных п, для которых
число п\ + 1 является простым, мы не знаем.
Простыми являются числа 1! + 1 = 2, 2! + 1=3,
3! + 1 = 7; следующим простым числом того же вида
является 11! + 1 =39916801. Мы не знаем, являетсй ли
простым число 27! + 1.
На основании теоремы Лейбница можно легко за-
заключить, что существует бесконечное множество нату-
натуральных чисел п, для которых число п\ — 1 является
составным. Но мы не знаем, существует ли бесконечное
множество натуральных п, для которых число п\ — 1
является простым (простыми являются числа 3! — 1 =
= 5, 4! — 1 = 23, 6! — 1 = 719). Мы не знаем также,
существует ли среди чисел каждого из видов р! + 1 и
р! — 1, где р — простое число, бесконечное множество
составных чисел.
Мы не знаем ответа на вопрос, существует ли бес-
бесконечное множество натуральных п, для которых число
Pip2... рп + 1 является простым (рп естб n-е простое
число), а также на вопрос, существует ли бесконечное
множество таких натуральных чисел п, для которых
число pip2... рп + 1 является составным.
Числа pi + 1 = 3, рхр2 +1=7, pip2p3 + 1=31,
Р1Р2РЗР4 + 1 =211, р1ргрзр4Р5 + 1 =2311 являются про-
простыми, но числа рфг... рп + 1 для п = 6, 7 и 8 являют-
являются составными, делящимися соответственно на 59, 19
и 347.
Докажем еще (следуя идее А. Шинцеля), что для
натуральных п > 3 произведение Qn всех простых чи-
чисел, меньших п, будет больше чем п.
Допустим, что при некотором натуральном п > 3
Qn<«. Тогда мы имели бы Qn— I <n. Число Qn — 1
не делится ни на одно простое число <п (так как та-
такие числа являются делителями Qn), поэтому, учиты-
учитывая, что п > 4, мы заключаем, что число Qn — 1 >•
;> Q4 — 1 = 5 > 1 имеет простой делитель р, который
должен быть ^. п. Но тогда Qn — 1 ^- п, что приводит
50

к противоречию. Таким образом, Qn > n для п>3, что
и требовалось доказать.
Относительно произведения Рп всех простых чисел
<л можно доказать, что для натуральных п имеет ме-
место неравенство Рп < 4", а для натуральных п >■ 29 не-
неравенство Рп > 2".
Доказано также, что для натуральных п > 2 сумма
всех простых чисел <и будет
19. Разложение простого числа на сумму двух квадратов
Пусть теперь р обозначает простое число вида 4k +
+ 1. Принимая во внимание четность числа ^-д——2k,
найдем, что число
при делении на р дает, очевидно, такой же остаток,
как число
Но последнее число, если его сомножители записать
в обратном порядке, можно представить в виде
поэтому, если мы его умножим на Н-^—)'• и заметим,
что ^—=2 1" ' т0 наиДем> чт0 получившееся
число (р + I)! дает при делении на р такой же оста-
остаток, как |""J Jl .А так как (р—I)! + I, согласно
теореме Вильсона, делится на р, то и число (-^—J! +
-f-1 также делится на р. Таким образом, доказана
Теорема 16. Если р есть простое число вида 4k +
+ 1, то число у—ц—И +1 делится на р.
Для вывода следствия из этой теоремы нам понадо-
понадобится следующая
51

Лемма. Если р — простое число и, а — целое чис-
число, не делящееся на р, то существуют натуральные чис-
числа x<Y~p и, у <Vp такие, что при соответствующем
знаке + или — число ах ± у делится на р.
Доказательство. Пусть р — данное простое
число и пусть пг обозначает наибольшее натуральное
число <У7>, так что ot+1>Vр и, следовательно,
(пг + 1J>р. Рассмотрим целые числа ах — у, где х и
у принимают значения 0, 1, 2, ..., пг. Таких чисел
имеется (ш + 1J>р, а так как при делении их на р
различных остатков может быть не более чем р, то при
двух разных системах чисел х\, у\ и Х2, у% где, напри-
например, х\ ^ х2, числа а*! — у\ и ах2 — yj должны при де-
делении иа р давать одинаковые остатки и, значит, число
ахх — у\ — (ах2 — у2) = а (дс, — х2) — (f/i — у2) должно
делиться на р. Равенство х\ = х2 здесь исключено, так
как в этом случае число у\ — у% делилось бы на р, что,
ввиду 0-<yi<:/7t<:Vrp <Р и аналогично 0^Су2<р,
невозможно, поскольку системы х\, у\ и дсг, у2 предпо-
предполагаются разными. Исключено также и равенство у\ =
= i/2, так как в этом случае число а(х\—х2) делилось
бы на р, откуда, согласно определению числа а, сле-
следовало бы, что число Х\ — х2 делится на р, а это невоз-
невозможно (в последнем убеждаемся так же, как и в слу-
случае разности у\ — уа). Далее, так как х\~^хч и х\фх2,
то число Х\ — х2 является натуральным, число же у\—•
— у2 целое, отличное от нуля, следовательно, при соот-
соответствующем знаке, число у = ± (j/i — у?) также яв-
является натуральным. Теперь замечаем, чтох = х1 — х2^.
^ xt <Cm<; Yp> следовательно, х < У~р> ибо равен-
равенство хг = р невозможно, поскольку р — простое число.
Аналогично у < Vp. При этом число ах ± у, которое
при соответствующем знаке равно числу а(хх—х2) —
— (id — У2), делится на р. Таким образом, лемма дока-
доказана.
Пусть теперь р — простое число вида Ak + 1 и пусть
а =\~2 )! есть число, не делящееся на р (согласно
следствию теоремы 7, как произведение нескольких на-
натуральных чисел, меньших р). Тогда, в силу нашей
леммы, существуют натуральные числа х < Yp, У <

< Vp такие, что при соответствующем знаке + или —
число ах ± у делится на р. Таким образом, в любом
случае число а2х2 — у2 — (ах,+ у) (ах — у) будет де-
делиться на р. Но, на основании теоремы 16, число а2 + 1
делится на р, следовательно, и число а2х2 + х2 делится
на р. Поскольку же числа а2х2 + х2 и а2х2 — у2 делятся
на р, то и их разность х2 + у2 делится на р и, следова-
следовательно, х2 + у2 = kp, £де k — натуральное число. Так
как х < Vp и у < Vp, то х2 + у2 < 2р, илн kp < 2р,
откуда k < 2, а так как k — натуральное число, то к =»
«= 1, т. е. х2 + у2 = р. Таким образом, доказана
Теорема 17 (Ферма). Каждое простое число вида
4k + 1 есть сумма двух квадратов натуральных чисел.
Так, например, 5 = I2 + 22, 13 = 22 + З2, 17 = I2 +
+ 42, 29 = 22 + 5*. 37 = I2 + б2, 41 = 42 + 52, 53 = 23 +
;+ 72, 61 = 52 + б2, 73 = З2 + 82.
Докажем теперь, что разложение простого числа на
сумму двух квадратов натуральных чисел единственно,
если не обращать внимания на порядок слагаемых.
Впрочем, мы докажем даже более общее предложение.
Теорема 18. Пусть а и Ъ — данные натуральные
числа, тогда ни одно простое число р нельзя предста-
представить двумя различными способами в форме р = ах2 +'
+ by2, где х и у — натуральные числа, если в случае
а = Ь = 1 не обращать внимания на порядок слагаемых.
Доказательство. Предположим, что простое
число р допускает два разложения:
р =
где х, у, xi, j/i — натуральные числа. Отсюда получаем
р2 = (аххх bJ b( J ( b[J
b
(y y)
Ho (axxl + byyi) (xyx + yx{) = (ax2 + by2)x{yi +'
'+ (ax*+ by\)xy = р(х\У\ + ху). Таким образом, по
крайней мере один из сомножителей левой части дол-
должен делиться на простое число р.
Если р\ахх\ + Ьууи то из первого выражения для р2
следует, что должно быть ху\ — ух\ = 0 и, следователь-
следовательно, jcj/i = ух\, р = аххх + Ьууи рх = (ах2 + by2)xi = рхи
откуда х = х\, а значит, н у = у\.
Если же р\ху\ + yxi, то из второго выражения для
р2 следует, что ахх\ — Ьуу\=*О и р2 = аЬ(ху{ + ух\J,
S3

причем последнее, если учесть, что числа х, у, х\ и (/»
являются натуральными, возможно только, тогда, когда
а = Ъ = 1. Поэтому имеем р = ху\ + ухх и хх\ — уу\ =
= 0, что дает нам равенство рх = (х2 + j/2)t/i = py\, от-
откуда х = ух и, следовательно (принимая во внимание,
что р =■ х2 + у2 = л:?Н- у?), (/ = х\. Таким образом, наши
разложения отличаются одно от другого только поряд-
порядком слагаемых. Теорема 18 доказана.
Из теоремы 18 тотчас же следует, что если нату-
натуральное число п можно представить хотя бы двумя
способами в виде суммы двух квадратов натуральных
чисел (при условии, что два разложения, отличаю-
отличающиеся только порядком слагаемых, не считаются раз-
различными), то п не является простым числом. Поэтому,
например, из того что 2501 = I2 + 502 = Ю2 + 492, мы
заключаем, что число 2501 не является простым.
Пусть тип — натуральные числа. Имеем т4 +]
.+ 4п* = (т2J + Bп2J - (т2 —2п2J + BтпJ.
Если т — п или т = 2п, то наши разложения на
суммы квадратов одинаковы, но тогда мы имеем либо
т4 + 4п4 = 5п4, что является простым числом только
для т = п — 1, либо т* + 4п4 = 20п\ что является чис-
числом составным. Если же т Ф п и т Ф 2п, то, как легко
доказать, наши разложения отличаются друг от друга
не только порядком слагаемых, и, значит, число т* +
+ 4п* — составное. Следовательно,
Если тип — натуральные числа, из которых по
крайней мере одно отлично от единицы, то число гп* +
■+■ 4п4 является составным.
В частности (для m = 1), отсюда следует, что все
числа вида 4п4 + 1, где п — натуральное число >1, яв-
являются составными.
Если мы имеем два разложения данного натураль-
натурального числа на суммы двух квадратов (отличающиеся
друг от друга не только порядком слагаемых), то не-
нетрудно показать, что можно найти представление этого
числа в виде произведения двух натуральных чисел,
больших единицы.
В частности, совершенно элементарно можно полу-
получить следующее разложение на множители
т4 + 4п* ш* (т2 + 2шп + 2я2) (т2— 2гпп + 2п2),
54

Заметим, однако, что если натуральное число допу-
допускает только одно разложение на сумму двух квадра-
квадратов натуральных чисел, то отсюда еще не следует, что
оно должно быть простым числом. Например, как легко
убедиться, числа 10, 18, 45 дают каждое только одно
разложение: 10 = I2 + З2, 18 = З2 + З2, 45 = З2 + б2.
Но можно доказать, что если натуральное нечетное
число п дает только одно разложение на сумму двух
квадратов целых чисел >. 0 (если не считать различ-
различными разложения, отличающиеся только порядком сла-
слагаемых), причем в этом разложении слагаемые не
имеют общего делителя >1, то п является простым чис-
числом. Основываясь на этом, при помощи электронной
вычислительной машины ЕМС, находящейся в Варшав-
Варшавском политехническом институте, удалось показать,
что число 239 — 7 есть простое; произведенное исследо-
исследование показало, что существует только одно разложе-
разложение этого числа на сумму двух квадратов, именно
2а» — 7 = 64 045* + 738 6842,
причем в этом разложении слагаемые не имеют общего
делителя >1.
О числах 2П — 7 для п = 4, 5, .... 38 известно, что
они являются составными. В 1956 г. П. Эрдеш поставил
вопрос, все ли числа 2" — 7 для натуральных п > 3 со-
составные. Ответ на этот вопрос, как мы видим, отрица-
отрицателен.
Числа 2" — 7 являются составными для п = 40,41, ...
..., 50, ибо они, как это было подтверждено, делятся
соответственно на 3, 5, 3, 107, 3, 5, 3, 11, 3, 61, 3. Таким
образом, среди чисел 2П — 7 для натуральных п, где
3 <я<50, имеется только одно простое (для п = 39).
Легко доказать, что среди чисел 2р — 7, где р —
простое число, имеется бесконечно много составных.
Действительно, согласно теореме 10, существует беско-
бесконечно много простых чисел вида 4А + 1, а для каждого
такого простого числа р, в силу того, что 5|24— 1, имеем
5|24ft —1, откуда 5|24ft+1 — 2, а значит, также 5|2р —7.
Мы не знаем, существует ли бесконечное множество
натуральных чисел п, для которых число 2" — 7 яв-
является простым.
55

В связи с теоремой 17 напрашивается вопрос, что
можно сообщить о разложениях других простых чисел
на суммы двух квадратов.
Число 2 имеет, очевидно, только одно представле-
представление в виде суммы двух квадратов натуральных чисел:
2 = I2 + I2. Таким образом, остается еще исследовать
простые числа вида 4k + 3 (где k = О, 1, 2, ,..). Легко
доказать, что ни одно натуральное число этого вида
не может быть представлено в виде суммы двух квад-
квадратов целых чисел. Действительно, поскольку это число
нечетное, то в случае 4k + 3 = х2 + у2 целые числа х
и у не могли бы быть оба четными или же нечетными.
Таким образом, одно из них должно быть четным, а дру-
другое нечетным. Но квадрат четного числа при делении
на 4 дает в остатке нуль, квадрат же нечетного — еди-
единицу. Следовательно, сумма х2 + у2 при делении на 4
дала бы в остатке 1, в то время как число 4k + 3 дает
в остатке 3. Формула 4k + 3 = х2 + у2, таким образом,
оказывается невозможной при целых k, x и у.
Итак, среда простых чисел только число 2 и простые
числа вида 4k + 1 разлагаются на суммы двух квадра-
квадратов натуральных чисел, причем каждое из них дает
только одно такое разложение (если не считать различ-
различными разложения, отличающиеся только порядком сла-
слагаемых). ч
Труднее ответить на вопрос, какие натуральные чис-
числа являются суммами двух квадратов натуральных чи-
чисел. Можно доказать, что для того чтобы натуральное
число п было суммой двух квадратов натуральных чи-
чисел, необходимо и достаточно, чтобы в его разложении
на простые сомножители сомножители вида 4k + 3, если
они встречаются, входили в степенях с четными показа-
показателями и, кроме того, чтобы либо число 2 входило с не-
нечетным показателем, либо число п имело по крайней
мере один простой делитель вида 4& + 1.
Исследован также вопрос, сколько данное натураль-
натуральное число п дает разложений на суммы двух квадратов
натуральных чисел. Оказывается, это зависит от раз-
разложения числа п на простые сомножители. Можно до-
доказать, что существуют натуральные числа, дающие
произвольно много разложений на суммы двух квадра-
квадратов натуральных чисел. Число 65 дает два разложения
на суммы двух квадратов: 65=12 + 82=42+72; чис-
56

ло 1105 дает четыре таких разложения: П05 =
+ 33» - 92 + 32* - 12» + 312 = 232 + 242.
20. Разложение простого числа
на разность двух квадратов и другие разложения
Напрашивается вопрос, какие простые числа и
сколькими способами могут быть представлены в виде
разности двух квадратов натуральных чисел.
Предположим, что простое число р разлагается на
разность двух квадратов натуральных чисел: р = хг—
— у2, где х и у — натуральные числа, причем, очевид-
очевидно, х > у. Отсюда р = (х — у) (х + у) и, значит, х — у
и х + у являются натуральными делителями числа р,
причем первый меньше второго. Но так как р — про-
простое число, то х — у = 1, х+у = р и, следовательно,
х— р~£ , у = р~ . Таким образом, число р должно
быть нечетным, и в этом случае мы имеем единствен-
единственное разложение
Итак, доказана
Теорема 19. Каждое нечетное . простое число пред-
ставимо в виде разности двух квадратов натуральных
чисел и притом только одним способом.
Легко доказать, что для того чтобы натуральное
число п > 1 было разностью двух квадратов натураль-
натуральных чисел, необходимо и достаточно, чтобы при деле-
делении на 4 оно не давало в остатке 2.
Можно доказать, что существуют числа, допускаю-
допускающие достаточно большое число разложений на разность
двух квадратов. Из теоремы 19 следует, что натураль-
натуральное число, допускающее более чем одно разложение на
разность двух квадратов натуральных чисел, не яв-
является простым.
Впрочем, легко также доказать, что если нечет-
нечетное число имеет только одно разложение иа разность
двух квадратов целых чисел, то оно является простым.
В самом деле, предположим, что нечетное число
57

n — составное и, значит, n = ab, где а и Ь — натураль-
натуральные числа > 1. Очевидно, имеем
причем если, например, а^-Ь, то л—1 = ab—1>
> а — Ъ (так как Ь > 1), и, следовательно, наши разло-
разложения являются различными.
Таким образом, нечетное составное число дает по
крайней мере два различных разложения на разность
двух квадратов целых чисел. Заметим, однако, что
имеются нечетные составные числа, представимые един-
единственным способом в виде разности двух квадратов на-
натуральных чисел, например число 9. (Можно доказать,
что такими числами являются квадраты простых нечет-
нечетных чисел.)
Перейдем теперь к вопросу о разложении простых
чисел на суммы трех квадратов натуральных чисел.
Можно доказать, что существует бесконечно много
простых чисел, являющихся суммами трех квадратов
натуральных чисел, а также бесконечно много простых
чисел, не являющихся такими суммами. Среди простых
чисел < 100 суммами трех квадратов натуральных чи-
чисел являются только следующие:
3=12+12+1*, Ц = 12+12 + 32, 17 = 22 + 22 + 32,
39 = I2 + З2 + З2, 29 = 22 + З2 + 42, 41 = I2 + 22 + б2 =
= З2 + 42 + 42, 43 = 3* + З2 + 52, 53 = I2 + 42 + б2,
59 = I2 + З2 + 72, 61 = З2 + 42 + б2, 67 = З2 + З2 + 72,
73 = I2 + б2 + б2, 83 = I2 + I2 + 92 = З2 + 52 + 72, 89 =
= 22 + 22 + 92 = 22 + б2 + 72 = З2 + 42 + 82, 97 = 52 +
,+ б2 + б2.
Мы видим также, что существуют простые числа,
имеющие более чем одно разложение на сумму трех
квадратов натуральных чисел, например числа 41, 83
и 89.
Легко доказать, что каждое целое число можно
представить бесконечным числом способов в виде х2 +
+ у2 — z2, где х, у, z — натуральные числа. Для этого
достаточно заметить, что для целых k и t имеют место
тождества:
2£ —1 *= BtJ+ (k — 2PJ— (k — 2P—\)\
2k = B1+ 1J+ (k — 2*2 — 202— (k — 2t2—2t—\)\
58

Что же касается разложений простых чисел на сум-
суммы четырех квадратов натуральных чисел, то можно
доказать, что такие разложения имеют все простые
числа, за исключением чисел: 2, 3, 5, 11, 17, 29 и 41.
Можно также доказать, что единственными просты-
простыми числами, которые не представимы в виде суммы
пяти квадратов натуральных чисел, являются числа 2,
3 и 7 и что для каждого натурального числа т > 3 су-
существует только конечное число простых чисел, не яв-
являющихся суммами т квадратов натуральных чисел.
И. Човла высказал предположение, что если число 1
считать простым (как это прежде иногда делали), то
каждое натуральное число является суммой восьми или
меньшего числа квадратов простых чисел. Это прове-
проверено для натуральных чисел <288 000.
В связи с теоремой 17 напрашивается вопрос, какие
простые числа могут быть представлены в форме х2 4
4 2у2, или в форме х2 4 Ъу2, где х и у — натуральные
числа. Здесь имеет место следующая теорема.
Для того чтобы простое число р можно было пред-
представить в виде хг 4 2у2, где х и у—-натуральные числа,
необходимо и достаточно, чтобы р было вида 8k 4 1
или 8k 4 3. Каждое простое число этих видов дает
только одно разложение вида х2 + 2у2 (что вытекает из
теоремы 18).
Так, например,
3=14-2 • I2, 11 = 34-2 • I2, 17=34-2 • 22, 19=14-2 • З2.
Высказано предположение, что существует беско-
бесконечно много простых чисел р вида 8k 4 1 и также вида
8& 4 3 таких, что р = I2 + 2у2, где у — натуральное
число, а также бесконечно много таких, что р = х2 +
4 2-12, где х — натуральное число. Например, 73 =
= I2 4 2- б2, 83 = 924 2- I2.
Для того чтобы простое число р можно было пред-
представить в виде хг 4 Ъу2, где х и у — натуральные числа,
необходимо и достаточно, чтобы р было вида Gk 4 1.
Каждое простое число этого вида дает только одно раз-
разложение вида х2 4 Ъу2.
Так, например, 7 = 22 4 3-I2, 13=124 3-22, 19 =
= 42 4 3 • I2, 31 = 22 4 3 • З2, 37 = 52 4 3 • 22. Высказано
предположение, что существует бесконечна много про-
простых чисел р вида 6k 4 1 таких, что р = I2 4 Ъу2, где
59

у — натуральное число, а также бесконечно много та-
таких, что р = х2 + 3 • I2, где х — натуральное число.
Имеем, например, 67 = 82 + 3 • I2, 103 = 102 + 3 • I2,
109= 12 + 3-62.
Из теоремы 17 непосредственно следует, что для
того чтобы простое число р можно было представить
в виде х2 + 4у2, где х и у — натуральные числа, необ-
необходимо и достаточно, чтобы р было вида 4k + 1.
Доказана также следующая теорема:
Для того чтобы простое нечетное число р можно
было представить в виде х2 — 2у2, где х и у —натураль-
—натуральные числа, необходимо и достаточно, чтобы р было чис«
лом одного из видов: 8k + 1 или 8k + 7').
Займемся теперь вопросом, какие простые числа яв-
являются суммами двух кубов натуральных чисел. На
этот вопрос можно легко дать ответ. Действительно,
если простое число р является суммой двух кубов на-
натуральных чисел, р = х3 + у3, то х + у\р, и если хотя бы
одно из чисел х, у оказалось бы больше единицы, то
было бы х + у <Сх3 + у3 = р, т. е. число р имело бы
натуральный делитель х + у, больший единицы и мень-
меньший р, что невозможно. Таким образом, должно быть
х = у = 1 и, следовательно, р = 2.
Итак, ни одно простое число, кроме числа 2 = I3 +]
+ I3, не является суммой двух кубов натуральных чи-
чисел.
Какие же простые числа являются разностями двух
кубов натуральных чисел? Если р — простое число и
р = х3 — у3, где х и у — натуральные числа, то х > у,
и имеем р = хг — у3 = (х — у) (х2 + ху + у2). Так как
здесь второй сомножитель больше первого, то должно
быть х — у = 1 и х2 + ху + у2 = р, откуда р — хг—
_(х_1)з = 3х2 — Зх + 1.
Таким образом, простое число р является разностью
двух кубов натуральных (и притом последовательных)
чисел тогда и только тогда, когда оио имеет вид Ъх(х—<
— 1) + 1, где х — натуральное число, большее единицы.
Высказано предположение, что таких простых чисел
существует бесконечно много. Для х «= 2, 3, 4, 5 мы по-
получаем здесь простые числа 7 = 23—I3, 19 = З3—23,
') См. W. Sierpinski, Teoria liczb, II, Warszawa, 1953,
str, 338, 446,
60

37 = 4s — З3, 61 =53 — 43; для х = 6 получаем состав-
составное число 9! = 1 • 13; для х — 7 — простое число 127 =
— 73 — б3; для х = 8 и х = 9 — составные числа 169 =•
= 13* и 217 = 7-31; для х = 10, И, 12—простые числа
271 = 103 —93, 331 = 113— 10», 397 = 123— II3; для
х = 13 — составное число 469 = 7-67; для х = 14 и
15 —простые числа 547 = 143 — 133 и 631 == 153— 143;
для* = 16 и х= 17 — составные числа 721 =7* 103 и
817 = 19-43; для х = 18 — простое число 919=183 —
-173.
Итак, все простые числа <1000, являющиеся разно-
разностями двух кубов натуральных чисел, суть следующие:
7, 19, 37, 61, 127, 271, 331, 397, 547, 631 и 919.
Легко можно доказать, что существует бесконечное
множество простых чисел, не являющихся разностями
двух кубов натуральных чисел. В самом деле, мы до-
доказали, что каждое простое число, являющееся раз-
разностью двух кубов натуральных чисел, есть число вида
Ъх(х—1) + 1, где х — натуральное число >1. Но из
двух последовательных натуральных чисел х — 1 ил
одно всегда четное. Следовательно, наше простое число
должно быть вида 66 4- 1. Но, согласно теореме 12, су-
существует бесконечно много простых чисел вида 6& + 5,
ни одно из которых, очевидно, не является числом вида
6& + 1 и, следовательно, не является разностью двух
кубов натуральных чисел. Заметим, однако, что имеются
составные числа вида 66 + 5, являющиеся разностями
двух кубов натуральных чисел, например число 215 =■
= 6 -35 + 5 = б3 — I3. Можно также доказать, хотя это
было бы труднее, что существует бесконечно много про-
простых чисел вида 6& + 1, не являющихся разностями
двух кубов натуральных чисел. Таковыми будут, напри-
например, простые числа 31, 67, 103, 139, 157.
Высказано предположение, что простых чисел, яв-
являющихся суммами трех кубов натуральных чисел, су-
существует бесконечно много. Высказано даже более силь-
сильное предположение, что уже простых чисел вида х3 +'
+ 2 = лс9 +. Is + I3, где х — натуральное число, имеется
бесконечно много. Таковы, например, простые числа
3=13 + 2, 29 = Зэ +2, 127 = 53 + 2, 24 391 =29»+ 2.
Можно доказать, что существует бесконечно много про-
простых чисел, не являющихся суммами трех кубов целых
чисел.
61

Легко доказать, что ни одно простое число >2 не
является суммой двух их степеней натуральных чисел,
где п есть нечетное число, большее единицы (доказа-
(доказательство аналогично изложенному выше для случая
п = 3). Заметим еще, что К. Ф. Рот в 1951 г. доказал,
что каждое достаточно большое натуральное число яв-
является суммой восьми кубов натуральных чисел, из ко-
которых по крайней мере семь — кубы простых чисел.
21. Квадратичиые вычеты
Если р— простое число, то квадратичным вы-
вычетом для числа р называется каждое целое число г,
для которого существует целое число х такое, что число
х2 — г делится на р. Другими словами, целое число г
называется квадратичным вычетом для р, если суще-
существует квадрат целого числа, дающий при делении на
р такой же остаток, как и г. Целые числа, не являю-
являющиеся квадратичными вычетами для р, называются
квадратичными невычетами для р.
Для числа 2, очевидно, каждое целое число является
квадратичным вычетом, так как если г — нечетное чис-
число, то 2|12 — г, если же г —четное число, то 2|02 — г.
Пусть теперь р — простое нечетное число. Выясним,
сколько в последовательности 1, 2, 3, ...,/? —1 имеется
квадратичных вычетов для р.
Обозначим через гх остаток от деления числа х2 на
р. Для целых х числа гх будут, очевидно, всеми квад-
квадратичными вычетами для р (так как р\х3 — гх). Значит,
в частности, квадратичным вычетом для р будет ка-
каждое из чисел
Г,, Г2, . . ., Гр-^ A)
2
(число ^к натуральное, так как мы предположили,
что р является простым нечетным числом). Числа по-
последовательности A), очевидно, отличны от нуля (так
как ни одно из чисел I2, 22, ..., (—^—) не делится на
р) и, следовательно, являются числами последователь-
последовательности 1, 2, 3, ..., р — 1. Покажем, что они все различ-
различные. Предположим, что для некоторых натуральных i
и /, где i <j-^.p~Z - > мы имеем Г{ = Г}. Это означает,
62

что числа i2 и /2 дают при делении на р одинаковые
остатки и, следовательно, число j2 — i2 = (/' — t) (j + t)
делится на р. Но, в силу неравенства для i и j, числа
/ — t и / + i являюгся натуральными, причем оба они
меньше р (так как / + t < 2/ < р — 1 < р). Таким об-
образом, число р должно быть делителем произведения
двух натуральных чисел, меньших р, что невозможно.
Итак, мы доказали, что гь4=г^ для t</-<"^ •
Следовательно, среди чисел последовательности 1, 2,
р — 1
..., р — 1 мы имеем по крайней мере £-^— квадратич-
квадратичных вычетов для р. Докажем теперь, что в этой после-
последовательности никаких других квадратичных вычетов
для р, кроме чисел A), не содержится. Предположим
для доказательства, что г есть число из последователь-
последовательности 1, 2, ..., р—1, являющееся квадратичным выче-
вычетом для р. Тогда существует целое число а такое, что
р\а2 — г. Отсюда следует, что р\(а?) 2 —г 2 , т. е.
Ezl
p\a"-l — r 2 .
Далее, так как число г не делится на р, то и число а
не делится на р. Поэтому, согласно теореме Ферма,
имеем р\ар1—1. Следовательно, р\(а"~1 — l) —
( l\ ±
— \а" ' — г 2 j, т. е. p\r l — 1. Таким образом, имеем
p\rt2 —1 для /==1, 2, ..., *—2—• Но, согласно тео-
реме Лагранжа, многочлен х 2 — 1 не может делиться
на р для более чем ^— различных значений х из по-
последовательности 0, 1, 2, ..., р— 1. Отсюда следует, что,
кроме ^~2— чисел A), в последовательности 1,2, ...,
р— 1 нет других чисел г, для которых р\г 2 —1, т. е.
в этой последовательности нет других квадратичных вы-
вычетов для р. Таким образом, доказана
Теорема 20. Если р есть простое нечетное число, то
в последовательности 1, 2, 3, ..., р— 1 мы имеем точно
£~2— квадратичных вычетов для р (и, очевидно, столько
63

же квадратичных невычетов для р, так как р—1 —
2 ~" 2 )'
Из доказательства теоремы непосредственно следует,
что для получения всех чисел последовательности 1,2,...
..., р—1, являющихся квадратичными вычетами для
простого нечетного числа р, достаточно определить
остатки от деления на р чисел
12 О2 З2
Таким путем мы найдем, например, что всеми квадра-
квадратичными положительными вычетами для 13, меньшими
13, являются числа 1, 4, 9, 3, 12, 10 и, следовательно,
невычетами для 13 (среди чисел >0 и <13) будут чис-
числа 2, 5, 6, 7, 8 и 11.
Как мы уже доказали выше, число г из последова-
последовательности 1, 2, ..., р—1 является квадратичным выче-
вычетом для простого нечетного р тогда и только тогда, ко-
р-\
гда число г 2 — 1 делится на р. Таким образом, если
число а из указанной последовательности является
квадратичным невычетом для р, то число а 2 — 1 не
делится на р. Но, согласно теореме Ферма, число
_, / 1=1 \
а?~1 — 1 делится на р, а так как**1*"—1=\а 2 —1/Х
( — Л
X Va 2 + v> причем первый сомножитель правой ча-
части ие делится на р, то должен делиться второй сомно-
житель, т. е. р\а 2 -+-1.. Следовательно, число а из по-
последовательности 1, 2, .... р — 1 является квадратичным
вычетом для простого нечетного числа р, если
р-»1 р-1
р\а 2 —1, н невычетом, если р\а 2 -\-\.
Заметим, что для составных чисел дело обстоит ина-
иначе. Например, для п = 15 среди натуральных чисел <15
только пять (следовательно, меньше чем —ц— = 7) яв-
являются квадратичными вычетами для числа 15, именно
числа 1, 4, 6, 9 и 10, а остальные 9 чисел являются
квадратичными невычетами для числа 15. Среди нату-
натуральных чисел <8 только два, именно числа 1 и 4 яв-
являются квадратичными вычетами для числа 8.
64

Заметим еще, что А. Вале Вине нашел теорему, со-
согласно которой нечетное числоп является простым гогда
и только тогда, когда ни одно из чисел 22, З2, 43, ...
• ■ • \~2 ) пРи делении на п не дает в остатке ни О,
ни 1.
Для простых чисел изучены также вычеты кубиче-
кубические, биквадратичные и высших степеней. Можно дока-
доказать, что для каждого нечетного числа п существует
бесконечно много простых чисел р, для которых каждое
целое число является вычетом я-й степени. Так, напри-
например, для чисел 5 и 11 каждое целое число является ку-
кубическим вычетом, для чисел же 5 и 7 каждое целое
число является вычетом 5-й степени.
Доказательство того, что каждое целое число яв-
является вычетом 5-й степени для простого числа 7, вы-
вытекает непосредственно из следующих формул, которые
легко можно проверить:
7@5 —О, 7{15-Ь 7|45 — 2, 7|55 — 3, 712s —4,
7I35 —5, 7|6S — 6.
Можно доказать, нто для простых чисел 5 и 17 ка-
каждое целое число является вычетом любой нечетной
степени. Можно также доказать, что для того чтобы
для простого числа р каждое целое число было выче-
вычетом любой нечетной степени, необходимо и достаточно,
чтобы простое число р было вида 2** + 1, т. е. чтобы
оно было простым числом Ферма.
22. Числа Ферма
Числами Ферма называются числа вида F& =
= 22*+1, где k = 0, 1, 2, ... Знаменитый математик
XVII века П. Ферма предполагал, что все такие числа
являются простыми. Это справедливо для k — 0, 1, 2,
3, 4, но Л. Эйлер в 1732 г. обнаружил, что число
F5 = г25 + 1 = 4 294 967 297,
имеющее 10 цифр, является составным: оно делится иа
641. В настоящее время мы знаем уже 37 составных
чисел Fk, именно для k.= 5, 6, 7, 8, 9, 10, 11, 12, K, 14,
15, 16, 18, 23, 36, 38, 39, 55Г 58, 63, 73, 77, 81, 117, 125,
144, 150, 207, 226, 228, 260, 267, 268, 284, 316, 452, 1945.
65

Среди этих 37 составных чисел Fh имеются такие,
для которых нам известны их разложения на простые
сомножители (Например, Fs и гв), имеются такие, для
которых мы не знаем этих разложений, но знаем раз-
разложения в произведения двух целых чисел >1 (напри-
(например, F1945), наконец, имеются и такие, для которых мы
не знаем ни одного разложения в произведение двух
целых чисел >1, хотя и знаем, что такое разложение
существует (F7, Fg, Fl3 и Fh).
Начнем с наибольшего из известных составных чисел
Ферма, т. е. с числа Fi945- Оно имеет более чем 10582
цифр, и поэтому все их невозможно выписать. Однако,
как уже было сказано ранее (§ 8), мы знаем наимень-
наименьший простой делитель этого числа: т = 5-21947 + 1. На-
прашиваются здесь два вопроса: 1) как найден этот де-
делитель и 2) как можно убедиться, что число т, имею-
имеющее 587 цифр, является делителем числа Fioa, все
цифры которого невозможно выписать.
Мы здесь, очевидно, не будем ни производить деле-
деления числа Fi945 на число т, ни находить частное от это-
этого деления. Совершенно иным путем мы убедимся, или,
скорее всего, выясним, как можно убедиться в том, что
число F1945 при делении на т дает в остатке нуль.
Обозначим для целого числа t через t остаток от де-
деления t на т. Из определения числа Гследует, что для
каждого целого числа t будет m\t — /. Определим те-
теперь последовательность rh {k = \, 2, ...) посредством
условий _
r, = 22, rft+1 = f| для k=l, 2, ... A)
Докажем при помощи индукции, что
т\22к — гк для А=1, 2, ... B)
Формула B), очевидно, справедлива для k = 1, так
как 22'—г\ = 0. Предположим, что она справедлива
для некоторого натурального числа k. В таком случае,
согласно B), и подавно /ге|22*+1 — г\. _Учитывая же,
что m\t— 1 для t = rl, имеем т\г\ — г\. Затем на-
находим /ге|22*+1 —г\. Следовательно, согласно A),
т\%2*+х — п+\. Итак, формула B) доказана посредством
индукции. Для k = 1945 имеем
^1^1945 ^1945 Ь
66

откуда следует, что число Fi945 при делении на т дает
такой же остаток, как и число г]945 + 1. Поэтому, чтобы
исследовать, делится ли число Fms на т, достаточно
исследовать, делится ли на т число г]945 + I. Осмыслим
теперь, какие действия нужно будет выполнить, чтобы
подсчитать число ri945- Из формул (,1) следует, что чис-
числа г 2, г г, ... как остатки от деления на т все будут
меньше т, так что каждое из них имеет не более чем
587 цифр. Таким образом, из формул A) вытекает, что
для вычисления числа Г1945 необходимо осуществить
1944 возвышений в квадрат чисел, имеющих не более
чем 58? цифр, и столько же делений этих квадратов
(следовательно, чисел, имеющих не более чем 1175
цифр) на число т, имеющее 587 цифр. Это — действия,
которые современные электронные машины в состоянии
выполнить. Таким путем было подтверждено, что число
F1945 делится на /п = 5'21947 + 1, а так как F}§45 > m,
что легко можно проверить, то заключаем, что число
Fi345 является составным.
Перейдем теперь к вопросу, как можно найти про-
простой делитель т числа Fm5. Известна теорема, согласно
которой каждый натуральный делитель числа Fn дол-
должен иметь вид 2n+2k + 1, где k — целое неотрицатель-
неотрицательное число. Для п = 1945 отсюда следует, что делителями
числа F1945 могут быть только числа, принадлежащие
арифметической прогрессии 21947& + 1, где k = 0, 1,
2, ... Для k — О мы получаем тривиальный делитель 1.
Для k=\ число 2п+2+1 = 21947 + 1 не является про-
простым, так как, очевидно, делится на 3. Для k = 2 число
2»+2.2 + 1 = 21948 + 1 = B4L87 + 1 делится на 2* + 1 и,
следовательно, не является простым. Для k = 3 число
2и+2.3 + 1 = 21947-3 + 1 является составным, делящим-
делящимся на 5. В самом деле, 5|24— 1, откуда 5|21944— 1. Ум-
Умножив правую часть последней формулы на 23»3, най-
найдем, что 5|21947 • 3 — 24, откуда также 5|21947-3 + 1. Для
k = 4 число 2п+2-4 + 1 = 21949 + 1 делится на 3, следо-
следовательно, является составным.
Таким образом, разыскивая простой делитель числа
.Fip45, мы должны делить его на 21947 • 5 + 1 = т. Как
уже отмечалось, деление выполняется без остатка, и
так как т — наименьшее целое число >1, являющееся
Делителем числа Fms, то т — число простое.
67

Подобным образом можно исследовать другие числа
Ферма. Исследование десятизначного числа F$, отно-
относительно которого Ферма был убежден, что оно яв-
является простым, выполняется весьма просто. Делители
числа Fa, как мы знаем, должны быть вида 27 • k + 1»
или \28k + 1. Для k = 1 мы получаем число 129, деля-
делящееся иа 3, и следовательно, составное; для k = 2 по-
получаем простое число 257, которое не является делите-
делителем числа Fs, в чем легко можно убедиться непосред-
непосредственным делением. Для k = 3 мы получаем число 385,
делящееся на 5 и, стало быть, составное. Для k — 4 по-
получаем число 513 = 29 + 1, делящееся на 3 и, следова-
следовательно, также составное. (Иначе, число 232 = 416 =
«= C + II6 = E— II6 при делении и на 3, и на 5 дает
в остатке 1, а значит, число Fs дает в остатке 2, т. е. чи-
число Fs ие делится ни на 3, ни на 5 и поэтому не делится
также ни на одно из чисел 129, 385 и 513.) Для k = 5
получаем простое число 641, относительно которого не-
непосредственным делением легко Можно убедиться, что
оно является делителем числа F&. Таким образом, толь-
только при помощи двух делений мы убеждаемся, что 641
является наименьшим простым делителем числа F5.
Разделив число F5— 4294967297 на 641, мы получим
в частном 6700417. Делители этого числа, будучи дели-
делителями числа F5, должны быть вида 27k + I. Если это
число составное, то .оно имеет простой делитель, не
больший, чем корень квадратный из него, и, значит,
<2600. Таким образом, для k мы имеем здесь неравен-
неравенство 128/г + 1 < 2600, откуда £<21, а с другой сто-
стороны, мы знаем, что должно быть k > 4, ибо наимень-
наименьшим простым делителем числа F& является 641. Таким
путем при помощи немногих делений подтверждено, что
число 6 700417 является простым, и, следовательно, по-
получена разложение числа Fj в произведение двух раз-
различных простых сомножителей.
Для числа fe найден делитель 28- 1071 + 1 и, таким
образом, подтверждено, что оно является составным.
Разыскать простой делитель числа Fn среди чисел
арифметической прогрессии 2п+2& + 1 практически воз-
возможно только в том случае, если число Fn обладает не
слишком большим простым делителем. В противном
случае, подставляя вместо k даже очень много последо-
последовательных натуральных чисел, мы не натолкнемся на
68

такой делитель. Это имеет место, например, для чисел
Ft и F», из которых первое содержит 39, а второе
78 цифр. Мы не знаем ни одного простого делителя этих
чисел, а также ни одного разложения их в произведения
двух натуральных чисел, б&льших единицы. Однако
Дж. К. Морхед в 1905 г. доказал, что число Fi являет-
является составным, а в 1909 г. он же и А. Е. Вестерн доказали,
что число Fs также является составным. Доказатель-
Доказательство основывалось иа следующей теореме.
Теорема 21. Если число Fn является простым., то
число З22 "' + 1 делится на Fn-
Докажем вначале следующее предложение.
Лемма. Если k есть целое неотрицательное число и
если число р = 12* + 5 является простым, то число
Збл+г + 1 делится на р.
Доказательство. Лемма, очевидно, справедлива
для k — 0, поэтому далее мы можем считать, что *
является числом натуральным. Пусть р = \2k + 5. Возь-
Возьмем произведение первых 6* + 2 натуральных чисел,
делящихся на 3, и разобьем сомножители этого произ-
произведения на три группы, отнеся к первой группе первые
2k сомножителей, ко второй — следующие 2k + 1 со-
сомножителей и к третьей — остальные 2k + 1 сомножи-
сомножителей.
Сомножители первой группы дают произведение
3-6-9 ...6*.
Сомножители второй группы, если, записать их в по*
рядке убывания, дают произведение
A2*4-3) - 12* - A2* — 3) ... F*4-6)F*4-3),
которое, учитывая, что р =* 12* + 5, можно написать в виде
Так как число сомножителей здесь нечетное Bk + 1),
то последнее произведение после развертывания и объ-
объединения слагаемых, делящихся на р, даст нам число
ри — 2*5-8... Fk+2), где и есть некоторое целое
число.
Сомножители третьей группы дают произведение
A2*+6)A2*4-9)A2*-f-12) ... A8*4-6) =
- • • (/>4-6*4- 0=
1-4- 7 ... F*4-1),
где о — натуральное число.

Таким образом, имеем 3-6-9 ... A8£ + 6) = 3-
•6-9 ... ш-[ри — 2-5-8 ... (Gk + 2)][pv + 1-4-7 ...
... F& + 1)] = pw — I • 2-3-4 -5-6 ... F& +1) • F6-f-
+ 2) — pw — F& + 2) !, где w — целое число.
Но 3 • 6 • 9 ... (Ж + 6) = F& + 2)!36"+2. Отсюда мы
заключаем, что число pw делится на F& + 2)!, следова-
следовательно, pw = Fk + 2) \t, где t есть целое число. Но
6k + 2 < 12& + 5 = р, и Поэтому число F£ + 2)! не де-
делится на р. Поскольку же произведение F& + 2)!£ де-
делится на р, то t должно делиться нар, t = ps, откуда
да = F& + 2)!s, где s есть целое число. Таким образом,
имеем 36ft+2 = ps — 1, откуда следует, что число 36ft+2 +
+ 1 делится на р, что и требовалось доказать.
Перейдем теперь к доказательству теоремы 21.
Доказательство. Пусть п есть некоторое нату-
натуральное число. Тогда имеем 2п = 2/п, где т — нату-
натуральное число, Fn— 1 = 4m, откуда следует, что число
гп — 5 делится на 4. С другой стороны, имеем Fn — 1 =
= 4m = C + l)m = 3f f 1, где( t — натуральное число.
Отсюда Fn—5 — 3(t— 1), так что число Fn — 5, делясь
на 4, оказывается делящимся и на 3, следовательно, это
число делится на 12, и поэтому Fп — \1k + 5, где k —
целое число. Таким образрм, согласно нашей лемме,
если число Fn простое, то число 36*+2-r-1 =s 3^л^8-4-
-f-l = 322 ~'-f-l делится на Fn.
Итак, теорема 2.1 доказана. Заметим попутно (хотя
далее это нам и не понадобйтсй), что можно доказать
и теорему, обратную теореме 21.
Воспользуемся теперь теоремой 21 для доказательства
того, что число F7 является составным. Для этой цели
достаточно показать, что число З2'" + 1 не делится на чи-
число F7 = 340 282 366 920 938 463 463 374 607 431 768 211 457.
Значит, достаточно вычислить остаток от деления чи-
числа З2'2' на Ft. Число З2"" столь велико, что мы не можем
выписать все его цифры, однако, чтобы подсчитать оста-
остаток, который оно дает при делении на F7, можно посту-
поступить следующим образом. Число З2' имеет 61 цифру,
следовательно, его мы можем написать и подсчитать
остаток г, который получается при делении этого числа
на F7 (теперь это уже нетрудно сделать, если прибег-
прибегнуть к помощи электронной вычислительной машины,
но для Морхеда в 1905 г. это было очень трудно, хотя
70

и возможно). Остаток гк от деления Числа г2'на число
Ft есть, очевидно, остаток от деления числа З2' иа число
Ft. Подобным же образом остаток гч от деления числа
г\ на число fV есть остаток от деления числа З2' на F7,
Продолжая этот процесс далее, дойдем до остатка г^о
от деления числа З2'" на F7. Таким путем найдем, что
г 120 Ф Fj — 1, откуда следует, что число З2'2' -+• 1 не де-
делится на F7 и, значит, согласно теореме 21, ^исло Ft не
является простым.
Аналогичным образом убеждаемся, 4to и число Fg
не является простым. Для каждого же из чисел Fn(n =
= 9, 10, 11 и 12), которые являются составными, мы
знаем их простые делители, именно: '
216-37-fH/v 212 • 11131 +1[F1O, 213-39+ljFH,
2"-74-l|F12.
На основании теоремы 21, при помощи электронных
вычислительных машин доказано, что Fi3, имеющее
2467 цифр, и Fu, имеющее 4933 цифры, являются чис-
числами составными. Никаких простых делителей этих чи-
чисел мы не знаем.
Доказано, что числа F]5 и Fie также составные, при-
причем найдены их простые делители: 221 • 573 + l|Fis,
2'8-3150-Ь 1|F16.
Число Fn имеет более 30 тысяч цифр. Существую-
Существующие же в настоящее время вычислительные машины не
в состоянии выполнять десятки тысяч делений чисел,
имеющих несколько десятков тысяч цифр, на числа,
имеющие более 30 тысяч цифр. Таким образом, мы, пока
все еще лишены возможности применить теорему 21
к исследованию чисел Fn и Fi9.
В 1953 г. для числа FI6 был найден наименьший
простой делитель 218 • 3150 + 1 и тем самым была опро-
опровергнута гипотеза, согласно которой все числа беско-
бесконечной последовательности
являются простыми (составное число Fi6 — пятый член
этой последовательности). Мы не знаем, однако, имеет-
имеется ли в этой последовательности бесконечно много про-
простых чисел, а также имеется ли в ней бесконечно много
составных чисел.
, 7)

Заметим, что ни одно из чисел 22 +| + 1, где п — на-
натуральное, не является простым, так как оно больше 3
и делится на 3.
23. Простые числа видов л" + 1, я"" + 1
и некоторых других видов
В связи с числами Ферма напрашивается вопрос,
сколько существует простых чисел вида пп + I, где л —
натуральное число. Предположим, что п — натуральное
и что число пп + 1 является простым. Каждое натураль-
натуральное п есть, как известно, число вида п = 2hm, где k —
целое число >■ О, а т — нечетное. Если бы т оказа-
оказалось числом, большим единицы, то число пп + I =
= (п2*)т + I было бы >и2* + 1 и делящимся на я2* + I
и, следовательно, было бы составным. Таким образом,
должно быть m = I, а значит, п = 2*.
Если k — О, то п — I, и число пп + I — 2 является
простым. Если же k > 0, то k = 2rs, где г есть целое
число ^-0, a s — нечетное. Если бы было s> 1, то чис-
число и»-f l=22'";-f 1=B2Г")*Ч-1 как число, большее
чем 22 ™ —)— 1 и делящееся на это число, было бы состав-
составным. Таким образом, должно быть s = Ъ, следовательно,
k = 2r, n = 2f и, значит, «"■+-1 ^tf-*' +\ =2***' -\-
+ 1-V '
Итак, число пп + 1, где п — натуральное число >1,
тогда и только тогда является простым, когда л = 2 #
где г — целое число >• 0, и fr+2r есть простое число.
Для г = 0, так как число Fi = 5 есть простое, мы
получаем простое число 2г + 1=5. Для г— I, так как
число ^з = 257 есть простое, получаем простое число
44 + 1 = 257. Для г = 2, так как F%, как известно, есть
число составное, делящееся на 28'1071 + 1, мы ие по-
получим простого числа. Для г = 3 мы также не получим
простого числа, ибо Fn является числом составным, де-
делящимся на 213-39 + 1. Таким образом, если кроме чи-
чисел 2, 5 и 257 существует еще простое число видая" + 1,
то оно должно быть > F» > 2220 > 2l°6 > lO31»5, т. е.
должно быть числом, имеющим более чем триста тысяч
цифр.
72

Следовательно, среди чисел вида пп + I (где п —
натуральное число), имеющих не более чем триста ты-
тысяч цифр, содержится только три простых числа: I1 +
,+ 1 = 2, 22 + 1 = 5 н 44 + 1 = 257.
Принимая это во внимание, можно рискнуть выска-
высказать гипотезу о том, что не существует простых чисел
вида пп + I, где п — натуральное число, кроме трех:
2, 5 и 257. Следует, однако, заметить, что из этой гипо-
гипотезы вытекало бы, что существует бесконечно много чи-
чисел Ферма, являющихся составными: таковыми были
бы числа FT+2r для г = 4, 5, 6, ..., т. е. числа F2o, F37,
Fiu, Fas, ^2841 F521, f 1034, ... Ни об одном из этих чи-
чисел, однако, до сих пор не доказано, что оно является
составным.
Рассмотрим теперь, что известно о простых числах
вида »""-1-1. Имеем lll-)-l=2, 222-)-l = 17.Легко до-
доказать, что если число пп" + 1, где п — натуральное чи-
число >1, является простым, то при некотором целом
г>0 должно быть л = 22', следовательно, пп"-\-\ =
Для г = 0 мы получаем простое число F2 = 17, для
г = 1 — число F9, о котором известно, что оно является
составным, делящимся на 21в»37+ I. Для г = 2 полу-
получаем число Fee, которое, как легко можно доказать,
имеет более чем 1018 цифр. Отсюда следует, что
Среди чисел, имеющих не более чем миллиард мил-
миллиардов цифр, существует только два простых числа
вида пп" + 1, где п — натуральное число, именно 2 и 17.
Рассмотрим также, какие из чисел вида п»2п + 1,
где п = I, 2, 3 являются простыми (это так назы-
называемые числа Каллеиа). Кроме числа 3 (для
п = 1), мы знаем еще только одно такое простое
число для п = 141. Вопрос, сколько имеется таких про-
простых чисел, остается открытым.
Легко доказать, что не существует других простых
чисел вида 2п + 1, кроме простых чисел Ферма. Дей-
Действительно, если п = 2rm, где m — нечетное число >1,
то число 2" -|-1 = B*)т ~Ь 1 делится на меньшее число
22Г-{-1 > 1 и, следовательно, является составным. Из
простых чисел вида 2п + 1, где п = 1,2,..., мы знаем, та-
таким образом, только пять, именно для га = 1, 2, 4, 8, 16.
К»

наименьшее же число этого вида, о котором мы не знаем,
простое оно или нет, есть число 28192 + 1. Следователь-
Следовательно, мы знаем также только четыре простых числа вида
2-2rt+l, где п — натуральное число, именно для
п = 1, 3, 7 и 15. Зато мы знаем 19 простых чисел вида
3*2" + 1, именно для п = 1, 2, 5, 6, 8, 12, 18, 30, 36, 41,
66, 189, 201, 209, 276, 353, 408, 438, 534. Простых чисел
вида 4-2" + 1, где п = 1, 2, ..., мы знаем только три:
для п = 2, 6 и 14. Простых же чисел вида 5-2™ + 1, где
п = 1, 2 ..., мы знаем 12: для п = 1, 3, 7, 13, 15, 25, 39,
55, 75, 85, 127, 1947.
Дли каждого натурального числа &<!100, за исклю-
исключением к = 47 и k «= 94, мы знаем по крайней мере одно
натуральное число п такое, что число k • 2п + 1 является
простым. Однако можно доказать, что существует бес-
бесконечно много таких натуральных чисел к, для которых
каждое из чисел £ • 2П + 1 (п = 1, 2, ...) является со-
составным.
. Займемся теперь простыми числами вида 2т + 2п +
+ 1, где т и п — натуральные числа, т> п. Такими
числами являются, например, 22 + 2 + 1 = 7, 23 + 2 +
+ 1 =* 11, 2а + 22 + 1 = 13, 24 + 2 + 1 = 19.
Неизвестно, существует ли бесконечное множество
таких простых чисел. Зато легко доказать, .что суще-
существует бесконечно много составных чисел указанного
вида. Это вытекает, например, тотчас же из равенства
22?. + 2"+i + 1 = Bп + IJ для п = 2, 3, ...,, либо из
замечания, что для k =■ 1, 2, ... число 24ft+1 + 2+1
всегда делится на 5, число же 22h + 22г + 1 при нату-
натуральных k и I всегда делится на 3. Имеем также раз-
разложение 24ft + 22h + 1 - B2ft + 2" + 1) B2h —2" + 1).
А. Рюснер установил, что для га < 24 числа 2п + 3
являются простыми только для п = 1, 2, 3, 4, 6, 7, 12,
15, 16, 18. Легко доказать, что среди чисел 222я-|-3
имеется бесконечно много составных, а именно числа
222t3*+i, +3 длд £ = 0> ^ 2, ... все делятся на 19. Чи-
Числа же 222/!+14-3 Для k = 0, 1, 2, ... все делятся на 7<
Заметим также, что 1312^* — 3 для А=1, 2, 3, ....
следовательно, и каждое из чисел
2^ — 3, 2^ — 3, ...
делится на 13 и, значит, является составным.
74

Мы не знаем, имеется ли среди чисел
2 + 3, 2*4-3, 222 + 3, 2^+3,...
только конечное число простых. Зато легко можно до-
доказать, что среди чисел
нет ни одного простого, так как каждое из этих чисел
делится на 7. Действительно, для натуральных к число
22h = C + l)h при делении на 3 дает в остатке 1, сле-
следовательно, 22h = 3* + 1, где t — натуральное число. От-
От2*
сюда 224-5 = 23'+1-г-5 = G4-1)'-24-5, чт0> оче.
видно, делится на 7.
Неизвестно, существует ли такое натуральное число k,
для которого имеется бесконечно много простых чи-
чисел вида 2ni + 2'h-{- ... 4-2"*+1, Где пи п2 nh
суть натуральные числа.
Мы не знаем также, существует ли бесконечно много
простых чисел вида 2п + п2, где п — натуральное число.
Четырьмя наименьшими такими простыми числами яв-
являются 3 = 2' + I2,17 = 23 + З2,593 = 29 + 92 и 32 993 =
= 2'5 + 152.
Как заметил А. Монковский, существует только одно
простое число, именно число 5, вида 4П + п4, где п —
натуральное. В самом деле, если п> 1, то п не может
быть числом четным. Пусть п = 2k + 1, где k — нату-
натуральное. Но тогда 4П + л4 = 4B*L + и4 = B • 22* —
— 2h+in + л2) B • 22h + 2h+xn + и2) есть число составное.
А. Шинцель доказал, что для всякого натурального
числа а, где 2<а<227, существует по крайней мере
одно натуральное число п< 15 такое, что число а2" + 1
является составным. Если бы, опираясь на этот факт,
мы рискнули высказать гипотезу, что для всякого на-
натурального а > 1 существует по крайней мере одно на-
натуральное п такое, что число а2" + 1 оказывается со-
составным, то из этой гипотезы вытекало бы существова-
существование бесконечного множества составных чисел Ферма,
ибо для а = 22*(где k—l, 2, ...) имеем а2" + \ = Fn+k.
(Заметим, что для а = 221945эту гипотезу еще не удалось
подтвердить).
75

Легко доказать, что существует бесконечное множе-
множество натуральных чисел а, для которых все числа а2"+
+ 1, где п = 1, 2, ..., являются составными. Таковы,
например, все числа а = Ьт, где Ъ — натуральное число
>1, а т — нечетное число >1.
С другой стороны, мы не знаем ни одного натураль-
натурального числа а > 1, для которого мы могли бы доказать,
что среди чисел а2" + 1 (п — 1, 2, ...) существует бес-
бесконечно много простых.
Из гипотезы Шинцеля (о которой речь будет идти в
§ 30) вытекает, что для всякого натурального числа т
существует такое натуральное число а>\, что все т
чисел а2" + 1, где п = 1, 2 т, являются простыми.
Для т = 4 можно взять а = 2. Но трудно было бы най-
найти такое число а > 1 для т — 5.
24. Три ошибочных теоремы Ферма
П. Ферма в своем письме к Мерсенну от 1641 г. вы-
высказал следующие три теоремы:
1. Ни одно из простых чисел вида 12А + 1 не яв-
является делителем ни одного из чисел вида Зп -Ь 1.
2. И и одно из простых чисел вида 10& + 1 не яв-
является делителем ни одного из чисел вида 5" + 1.
3. Ни одно из простых чисел вида 10& — 1 не яв-
является делителем ни одного из чисел вида 5й + 1.
Доказано, что ни одна из этих трех теорем не яв-
является справедливой. Первая потому, что, например,
61|35-г-1, 24113*4-1» вторая потому, что бг^^+Ь
третья потому, что 29|57 + 1. Для каждой из этих
трех теорем, как доказал А. Шинцель, существует бес-
бесконечно много простых чисел, для которых они не-
неверны.
Таким образом, здесь положение несколько иное по
сравнению с теоремой Ферма о том, что каждое из чи-
чисел 22"H-1 (л—1, 2, ...) является простым, где мы
зиаем только конечное число примеров, опровергающих
эту теорему.
Кроме приведенных выше теорем, Ферма в указан-
указанном письме к Мерсенну сформулировал также теорему
о том, что ни одно простое число вида \2k — 1 не яв-
является делителем ни одного из чисел вида Зп + 1. Эта
теорема позднее была доказана.
76

25. Числа Мерсенна
Числами Мерсенна называются числа вида
Мп = 2П — 1, где п = 1, 2, 3, ... Они представляют ин-
интерес с двух точек зрения. Во-первых, наибольшие из-
известные нам простые числа являются числами Мерсен-
Мерсенна и, во-вторых, при помощи чисел Мерсенна мы нахо-
находим все так называемые совершённые четные числа.
(Совершенным числом называется натуральное чи-
число, равное сумме всех своих натуральных делителей,
меньших самого числа.) я-е число Мерсенна можно опре-
определить также как сумму п первых членов геометриче-
геометрической прогрессии 1, 2, 2*, 2s, 24, ...
Таким образом, имеем
М, = 1, М2 = 3, М3 - 7, Mt = 15, Мь = 31, М6 = 63,
М7 = 127, ...
Как легко доказать, если индекс п числа Мп есть
число составное, то и число Мп является составным.
В самом деле, если л = ab, где а и Ь — натуральные
числа >1, то 2а — 1>1 и 2п — 1 = 2аЬ — 1 > 2а— 1,
следовательно, число 2а*—1, делящееся на 2й—1, яв-
является составным.
Итак, если число М„, где п > 1, простое, то и число
п должно быть простым, но ие обязательно наоборот,
так как, например, Мп = 211 — 1 = 2047 = 23-89.
Доказано, что если р — простое число, то каждый
натуральный делитель числа Мр должен быть вида
2kp + 1, где k — целое число !>- 0. Поэтому, например,
делителями числа Мц являются числа 22Л + 1, где
k =0, 1, 4 и 93.
Точно так же делители числа Afioi = 2101 — 1 должны
быть вида 202& + 1. К сожалению, до сих пор не най-
найдено ни одного простого делителя числа Мт (очевидно,
число k здесь очень велико), хотя другим путем (о чем
речь будет идти позднее) доказано, что число Af 1Oi со-
составное и является произведением двух различных про-
простых, чисел.
Доказано, что если q есть простое число вида
8А + 7, то q\Mq-i. Это позволило показать, что среди
2
77

чисел Мр, где р — простое число, многие являются со-
составными. Например,
47|Ж23, 167|Л*Ю, 263|Л*И„ 359|М179, 383|Ж19„ 479|M,39-
Высказано предположение (до сих пор не доказанное),
что таких составных чисел существует бесконечно много.
Мы знаем пока только 20 простых чисел Мерсеина.
Это числа Мп для п = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89,
107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253 и 4423,
Восемь наибольших простых чисел Мерсенна были най-
найдены в последнее десятилетие при помощи электронных
вычислительных машин.
Покажем теперь, каким путем было доказано, что
эти весьма большие числа Мерсенна являются про-
простыми. Это стало возможным благодаря следующей тео-
теореме, доказанной ранее.
Теорема Люка—Д. X. Лемера. Число Мр, где
р — простое нечетное кисло, тогда и только тогда есть
простое, когда Мр является делителем (р — 1) -го члена
последовательности ип (я = 1, 2,...), определенной
условиями:
«i = 4, ttn+1 = «2 —2 для 71=1,2,...
(стало быть, последовательности, первыми членами ко-
которой являются числа 4, 14, 194, 37634, ...).
Легко доказать, что Мр\ир-} тогда и только тогда','
когда Мр является делителем (р — 1) -го члена последо-
последовательности гп(п = I, 2, ...), зависящей от Мр и опре-
определенной условиями: г} — 4, гп+\ является- остатком о Г
деления числа т\ — 2 на Мр.
Таким образом, при доказательстве того, что. число
Мр есть простое или составное, нам приходится иметь
дело только с возвышением в квадрат и последующим
делением на Мр чисел, меньших чем Мр. В частности,
для доказательства того, что число Afjoi, имеющее 31
цифру, является простым, нужно было бы убедиться в
том, что Мклкюо. После выполнения необходимых здесь
вычислений было установлено, что число гш не делится
на Af 101. Следовательно, число Mioi составное.
Чтобы доказать, что число М32п, имеющее 969 цифр,^
является простым, нужно. было установить, что'
Л^з217^з21в- Для этого потребовалось произвести несколь-(
ко тысяч возвышений в квадрат и затем делений' на'
78

з217 чисел, имеющих не более чем 969 цифр, что совре-
современные машины в состоянии выполнить1).
Высказано предположение, что если число Мерсенна
Мп является простым, то.и число Мм„ является про-
простым. Это справедливо для четырех наименьших про-
простых чисел Мерсенна, но уже для пятого простого чи-
числа Mi3 = 8191, как показал в 1953 г. Д. Ю. Уилер, это
неверно: число MMlt = ^m—1 (имеющее 2466 цифр)
является составным2). Заметим, что ни одного простого
делителя числа -Мм,, мы не знаем.
В 1957 г. доказано, что хотя числа Mi7 и М,9
простые, числа Мм17 и Мм19 являются составными,
делящимися соответственно на 1768B17—1) + 1 и
120B19— 1) + 1.
Высказано также предположение (до сих пор не-
опровергнутое), что числа д0, ди Цг, • • •, где до = 2, а
qn+\ = 2*« — 1 для п = 0, 1, 2, ..., являются все про-
простыми. Это справедливо для чисел qn, где л<4, но уже
для q5, имеющего, как легко подсчитать, более чем
1037 цифр, мы не в состоянии решить вопрос, простое
оно или составное.
Мы уже упоминали о связи чисел Мерсенна с совер-
совершенными четными числами. Еще Евклид указал сле-
следующий способ получения всех совершенных четных
чисел. Вычисляем последовательно суммы членов гео-
геометрической прогрессии 1, 2, 22, 23, ... Если такая сум-
сумма окажется простым числом, то, умножив ее на по-
последнее слагаемое, получим совершенное число.
С другой стороны, известно, что все совершенные
четные числа являются числами вида 2v~lMp, где Мр
есть простое число Мерсенна. (Справедливость этой
теоремы была доказана лишь в XVIII в. Л. Эйлером.)
Отсюда следует, что мы знаем столько совершенных
четных чисел, сколько мы знаем простых чисел Мерсен-
Мерсенна, т. е. в настоящее время 20 чисел.
') Для доказательства того, что число Man является простым,
шведская электронная вычислительная машина БЕСК в 1957 г. за-
затратила 5'/г часов.
2) Доказательство последнего факта (прн помощи теоремы
Люка—Лемера) потребовало ста часов работы электронной вычи-
вычислительной машнны.

Наименьшим совершенным числом является число
2М2 = 6, наибольшим известным совершенным чис-
числом — число 24422 B4423 — I). Чисел совершенных нечет-
нечетных мы не знаем. Известно только, что если они суще-
существуют, то являются весьма большими.
Упомянем еще об одной гипотезе, относящейся к
числам Мерсенна. Ф. Якобчик высказал предположение,
что если р — простое число, то число Мерсенна Мр не
делится ни на один квадрат простого числа. А. Шинцель
поставил вопрос, существует ли бесконечное множество
чисел Мерсенна, являющихся произведениями различ-
различных простых чисел.
26. Простые числа
в различных бесконечных лоследовательностях
Вопрос, содержит ли данная бесконечная последова-
последовательность, определенная даже несложным способом,
бесконечно много простых чисел, вообще говоря, весьма
труден. Как мы уже говорили, мы не знаем, содержат
ли последовательности п2 + 1, п\ + 1, п\ — 1, 2П + 1,
2п—1 (для п = 1, 2, ...) бесконечно много простых
чисел. Мы не знаем также, содержит ли бесконечное
множество простых чисел последовательность 1, 11, 111,
1111, ... Также обстоит дело и в случае так называе-
называемой последовательности Фибоначчи ип (я = 1, 2, ...),
определенной условиями
«i = иг = 1, un+t = ип + un+i (п. = 1, 2, 3, ...).
Первыми членами этой последовательности являются
числа «i = l, «2=1, «з = 2, щ = 3, и$ = 5, «6 = 8,
и7 = 13, ut = 21, ...
Доказано, что числа ип являются простыми для
п = 3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47. Других простых
чисел ип мы пока не знаем. Наибольшее известное про-
простое число ип есть число «47 = 2971 215073, имеющее
10 цифр. Можно доказать, что если п Ф4 и число ип
является простым, то и число п должно быть простым,
но не обязательно наоборот, так как, например,
а2= 1, «19 = 4181 =37- 113, «si = 1346269 = 557-2417.
Мы не знаем, имеется ли среди чисел ир, где р —
простое число, бесконечно много составных.
80

Рассмотрим также последовательность vn (n = I,
2, ...), определенную условиями
tfi = I, »а = 3, о„+2 = w» + o»+J (п = 1, 2, ...).
первыми членами которой являются числа 1, 3, 4, 7, 11,
18, ... Числа vn являются простыми для п = 2, 4, 5, 7,
8, 11, 13, 17, 19, 31, 37, 41, 47, 53, 61, 71. Наиболь-
Наибольшее известное простое число vn есть число Vi\ =
= 688846502588399. Мы не знаем, существует ли беско-
бесконечно много простых чисел vn.
Укажем здесь еще одну последовательность, которой
в последние годы занималось несколько математиков.
При ее построении исходим из последовательности всех
нечетных чисел: 1, 3, 5, 7, 9, И, 13, 15, ... Положим
и, = 1; наименьшее число последовательности, большее
и,, есть 3, его мы и примем за «2- Вычеркнем из нашей
последовательности каждое третье число (т. е. числа,
находящиеся на местах третьем, шестом, девятом
и т. д.). Таким путем мы получим иовую последователь-
последовательность: 1, 3, 7, 9, 13, 15, 19, 21, 25, 27, ... Наименьшее
число этой последовательности, большее и2, есть 7, его
мы и примем за щ. Вычеркнув теперь из последней по-
последовательности каждое седьмое число, получим по-
последовательность 1, 3, 7, 9, 13, 15, 21, 25, 27, ... Наи-
Наименьшее число этой последовательности, большее «з,
есть 9, его мы примем за щ. Из полученной последо-
последовательности будем вычеркивать теперь каждое девятое
число. Поступая так далее, получим бесконечную после-
последовательность «i, щ, ..., у которой членами, меньшими
ста, будут числа: 1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43,
49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99.
Числа нашей последовательности названы счаст-
счастливыми. Мы не знаем, имеется ли среди них бес-
бесконечно много простых. Подсчитано, что среди счаст-
счастливых чисел, меньших 98600, имеется 715 простых чи-
чисел.
27. Решение уравнений в простых числах
Мы знаем иного простых уравнений (даже первой
степени), относительно которых неизвестно, имеют ли
они бесконечное множество решений в простых числах.
81

Таково, например, уравнение х + у =* г. Легко дока-
доказать, что вопрос, имеет ли это уравнение бесконечно
много решений в простых числах х, у, г, равносилен во-
вопросу, существует ли бесконечно много пар простых чи-
чисел близнецов. В самом деле, если р, q и г — простые
числа такие, что р + q — г, то числа рае/, очевидно, не
могут быть оба нечетными (так как тогда сумма их была
бы числом четным >2 и, следовательно, составным).
Следовательно, одно из чисел р и q, например число q,
должно быть четным и потому равно 2. Но тогда числа
р- и г = р + 2 составили бы пару простых чисел близ-
близнецов. С другой стороны, если числа р и г = р + 2 со-
составляют пару простых чисел близнецов, то числа х =
— р, у = 2, z — р + 2 являются простыми и дают реше-
решение уравнения х + у = г.
Мы не знаем, имеет ли уравнение 2х + 1 = у или
уравнение 2х — у — 1 бесконечно много решений в про-
простых числах х, у (такое предположение высказано),
хотя и известно много таких решений. Например, для
уравнения 2х + 1 = у (х, у) = B,5), C,7), E,11), A1,
23), для уравнения же 2х—1—у (х,у) = B,3), C,5),
G,13), A9,37).
Дж. Г. ван дер Корпут доказал, что уравнение
х + у + 1 == z имеет бесконечное множество решений в
простых числах х> у, г (ср. стр. 19).
Доказано, что уравнение х + у = z + t имеет бес-
бесконечное множество решений в различных простых чис-
числах х, у, z, t, так же как и уравнение х + у2 = z2 + Р>
Например, 72 + 192 = IP + 172. Легко доказать, что
уравнение хг + у2 + г2 = Р не имеет ни одного реше-
решения в простых числах х, у, z, t.
Мы не знаем, существует ли бесконечное множество
прямоугольных треугольников таких, чтобы длины их
сторон были натуральными числами, из которых два —
простые. Можно доказать, что этот вопрос равносилен
вопросу, имеет ли уравнение р2 = 2q — 1 бесконечно
много решений в простых числах р и q. Примерами
таких треугольников являются треугольники со сторо-
сторонами C,4,5), E,12,13), A1,60,61), A9,180,181), B9,
240,241), F1,1860,1861).
Легко находятся все решения уравнения х2—2у2 =
= 1 в простых числах х, у. В самом деле, если нату-
натуральные числа х, у удовлетворяют уравнению х2 = 2у2 +j
82

r+ 1, то х, очевидно, число нечетное, х =s 2k + 1, где
k — целое число, откуда х2 = 4&а + 4k + 1, а следова-
следовательно, «/2 = 2fe(& 4- 1) и, стало быть, у есть число чет-
ное. Поэтому, если у является простым числом, то у =*=
= 2, откуда следует, что наше уравнение имеет одно
только решение в простых числах: х = 3, у — 2.
Мы не знаем, сколько решений в простых числах х,
у имеет уравнение х2 — 1уг =*—1. Такие решения из-
известны, например, х «= 7, у == 5 или х = 41, у = 29.
Легко доказать, что если я — натуральное число >1,
то уравнение рп + qn = г" не имеет решений в простых
числах р, q, г.
До сих пор не доказано предположение Ферма, со-
согласно которому если р — простое нечетное число, то
уравнение х? + у? — г? не имеет решений в натураль-
натуральных числах х, у, г. (Это доказано для простых нечет-
нечетных чисел р < 4002.)
28. Магические квадраты, составленные
из простых чисел
Магическим квадратом (в широком смысле) с п
строками мы называем таблицу, составленную из п2 раз-
различных натуральных чисел; выписанных в п строк (и
столько же столбцов), такую, что суммы чисел каждой
строки, каждого столбца и чисел, находящихся на ка-
каждой из главных диагоналей, одинаковы. Известны ма-
магические квадраты с тремя и четырьмя строками, со-
составленные из одних простых чисел. Например, квад-
квадраты
569
239
269
59
359
659
449
479
149
17
307
127
347
317
157
277
47
397
107
257
37
67
227
137
367

В первом из этих квадратов суммы, о которых идет
речь, все равны 1077; во втором — 798.
Высказано предположение, что для каждого нату-
натурального числа п ^ 3 существует бесконечно много ма-
магических квадратов (в широком смысле), составленных
из п2 различных простых чисел.
29. Несколько нерешенных задач,
касающихся простых чисел
1. Мы не знаем, существует ли бесконечно много
пар последовательных натуральных чисел, каждое из
которых имеет только один простой делитель (как, на-
например, пары 2 и 3, 3 и 4, 4 и 5, 7 и 8, 8 и 9, 16 и 17,
31 и 32). Нам известно только 26 таких пар, из кото-
которых наивысшей является пара 24423—1 и 24423 (ср. да-
далее 6).
Зато можно доказать, что уравнение рт— qn = 1,
где р и q — простые числа, а т н п — натуральные чис-
числа >1, имеет только одно решение: р = 3, q — 2, т —
= 2, п = 3.
2. Мы не знаем, существует ли бесконечное множе-
множество троек последовательных натуральных чисел, ка-
каждое нз которых является произведением двух различ-
различных простых чисел. (Примером такой тройки может
служить тройка чисел: 33 = 3 • II, 34 = 2 • 17, 35 = 5- 7,
а также тройка: 93 = 3-31, 94 = 2-47, 95 = 5- 19.) Вы-
Высказано предположение, что таких троек существует
бесконечно много.
3. Мы не знаем, существует ли бесконечно много
простых чисел р таких, что для каждого натурального
п < р — 1 число 2™ при делении на р дает остаток, от-
отличный от 1. (Такими являются, например, простые
числа 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83.) Выска-
Высказано предположение, что таких простых чисел р суще-
существует бесконечно много.
4. Мы не знаем, из каждого ли натурального числа
я^ 10 при изменении двух его цифр можно получить
простое число. (Для двузначных чисел это очевидно.
Для трехзначных чисел это вытекает, например, из
того, что простыми являются числа 101, 211, 307, 401,
503,601,701,809,907.)
84

5. Мы не знаем, справедлива ли гипотеза А. Шин-
целя, согласно которой для каждого вещественного
числа х !> 117 существует по крайней мере одно простое
число р, содержащееся между х и х + У~х. Эту гипо-
гипотезу А. Шинцель проверил для всех чисел х таких, что
117<*<2- 107.
6. Легко доказать, что среди любых шести последо-
последовательных натуральных чисел по крайней мере одно
имеет хотя бы два различных простых делителя (так
как всегда одно из них делится на 6 и, значит, имеет
простыми делителями 2 и 3).
Можно также доказать, что среди каждых трех по-
последовательных натуральных чисел >7 хотя бы одно
имеет по крайней мере два различных простых дели-
делителя. Но мы не знаем, среди каждых ли двух доста-
достаточно больших последовательных натуральных чисел
хотя бы одно имеет по крайней мере два различных
простых делителя. Иными словами, мы не знаем, су-
существует ли натуральное число т такое, что для п >.«
хотя бы одно из натуральных чисел и и п + 1 имеет по
крайней мере два различных простых делителя. Мы
знаем только, что если такое т существует, то должно
быть т > 2м23, ибо из чисел 24423 — 1 и 24423 каждое
имеет только один простой делитель. Доказано, что если
такое число т существует, то существует только конеч-
конечное число простых чисел Ферма и только конечное чис-
число простых чисел Мереенна.
30. Гипотеза А. Шинцеля
Многочлен от переменной х с целыми коэффициен-
коэффициентами мы называем неприводимым, если он не
является произведением двух многочленов с целыми
коэффициентами, степени которых меньше степени рас-
рассматриваемого многочлена.
Относительно многочлена f(x) с целыми коэффи»
циентами напрашивается вопрос, когда такой многочлен
при натуральных значениях х дает бесконечно много
простых чисел. Легко доказать, что необходимым усло-
условием этого является требование, чтобы многочлен был
неприводимым. Однако такое условие не является доста-
достаточным, ибо, как легко доказать, многочлен ж2 + х + 2
65

является неприводимым, но ни при одном натураль-
натуральном значении х не дает простого числа: для каждого
натурального х его значение есть число четное >2.
Легко также доказать, что кроме неприводимости
многочлен f(x) должен удовлетворять еще следующему
условию: не существует ни одного натурального числа
>1, которое являлось бы делителем числа f(x) при ка-
каждом целом значении х.
Являются ли эти условия достаточными для того,
чтобы многочлен с целыми коэффициентами, где коэф-
коэффициент при наивысшей степени х положителен, давал
бесконечно много простых чисел для натуральных х?
В прошлом веке В. Я. Буняковский высказал предполо-
предположение, что это так. Из данной гипотезы сейчас же сле-
следует, что существует бесконечно много простых чисел
вида х2 + 1, где х — натуральное число. Из нее же сле-
следует также, что существует бесконечно много натураль-
натуральных чисел х, для которых х2 + х + 41 является числом
простым.
Из гипотезы А. Шинцеля, о которой речь идет ниже,
следует, что для каждого натурального числа п суще-
существует бесконечно много натуральных чисел х, для ко-
которых все четыре числа ж2* + 1, х2" + 3, ж2" + 7, х2" +
+ 9 простые.
А. Шинцёль высказал следующую общую гипоте-
гипотезу Р.
Если s — натуральное число, f\(x), fi(x), ..., fs(x) —
многочлены с целыми коэффициентами, имеющие при
наивысших степенях х положительный коэффициент, не-
неприводимые и удовлетворяющие следующему усло-
условию S: не существует натурального числа > 1, которое
являлось бы делителем произведения ji(x)f2(x) ... fs(x)
для каждого целого значения х, — то существует беско-
бесконечно много натуральных чисел х, для которых каждое
из чисел fi(x), f2(x), .... fs(x) является простым.
Пусть, в частности, s =* 2, f\(x) = х, f2(x) ** х + 2k,
где 2k — данное натуральное четное число. Имеем здесь
Если бы существовало натуральное число d> 1 та-
такое, что d\U(x)h(x) для каждого целого числа х, то
должно было бы быть d\2k -^ 1 и d\2k +1, что невоз-

можно, ибо, как известно, два последовательных нечет-
нечетных числа 2k — 1 и 2k + 1 не имеют ни одного общего
делителя, большего единицы. Таким образом, условие S
здесь выполнено, и из гипотезы Р следует, что суще-
существует бесконечно много натуральных чисел х таких, что
числа fi(x) и f2(x) являются простыми, стало быть,
х — р, х + 2k — q, где р и q — простые числа, откуда
2k — q — р. Поэтому из гипотезы Р следует, что каждое
натуральное четное число может быть представлено
бесконечным числом способов в виде разности двух про-
простых чисел. В частности, для k — 1 отсюда следует су-
существование бесконечного множества пар простых чи-
чисел близнецов.
Из гипотезы Р А. Шинцеля можно вывести еще мно-
много других теорем о простых числах, которые до сих пор
не доказаны.

ИМЕННОЙ УКАЗАТЕЛЬ
Адамар (Hadamard J.) 29
Бейкер (Baker С. L) 16
Бертран (Bertrand J.) 14
Бнджер (Beeger N. G. W. Н)
38
Бредихин Б. М. 34
Буняковский В. Я. 86
Вале Вине А. 65
Валле-Пуссен (Vallee Poussin
de la Ch.) 29
Ван дер Корпут (Van der Cor-
put J. G) 19, 82
Вестерн (Western A. E.) 44, 69
Вильсон (Wilson J.) 47—51
Виноградов И. М. 18
Вороной Г. Ф. 7
Гарди (Hardy G. H.) 20
Гильбрайт (Gilbreath N. L.)
21, 22
Голашевский (Golaszewski S}
18
Гол>бев В. А. 32, 35 •
Гольдбах Хр. 18, 19
Горжелевский (Gorzelewski A.)
44
Грунбергер (Gruenberger F. J.)
16
Джуга (Giuga G.) 39
Дирихле (Dirichlet P. G. Leie-
une) 42
Евклид 13, 79
88
Каллен (Cullen J.) 73
Кантор (Cantor M.) 35
Крайчик (Kraitchik M) 27
Кулик (Kulik J. F.) 16
Лагранж (Lagrange J. L.) 45—
48, 63
Ландау (Landau E.) 30
Лейбниц (Leibniz G. W) 49, 50
Лемер Д. H. (Lehmer D N) 16
Лемер Д X. (Lehmer D H)
38, 44, 78, 79
Линник Ю. В 20
Литтлвуд (Littlewood J. E) 20,
41
Лич (Leech J) 41
Лохер-Эрнст (Locher-Ernst L.)
29
Лузин Н Н. 8
Люка (Lucas) 78, 79
Мазуркевич (Mazurkiewicz S ) 8
Мерсенн (Mersenne M) 76—80,
85
Мозер (Moser L ) 28, 49
Монковский (Mqkowski A.) 19,
75.
Морхед (Morehead J. C.) 69,
70
Ньютон (Newton I.) 36
Полетти (Poletti L.) 16
Портер (Porter R. J.) 16
Рихерт (Richert H E.) 28
Рихнер (Richner A.) 74

Робинзон (Robinson R. M? 14
рот (Roth К. F.) 62
Серпинский (Sierpinski W.) 7—
9 10, 14, 27, 29, 44, 45, 60
Скуля (Skula L.) 45
Туран (Turan P.) 31
Уилер (Wheeler D. J.) 79
Ферма (Fermat P.) 35, 39, 40,
48, 49, 53, 63—66, 68, 72, 73,
75, 76, 83, 85
Ферье (Ferrler A) 32
Фибоначчи (Fibonacci L.) 80
Чебышев П Л. 14, 44
Човла (Chowla I.) 59
Шерк (Scherk H. J.) 30
Шиицель (Schinzel A) 9, 18,
31, 38, 44, 50, 75, 76, 80,
85—87 .
Эйлер Л. 33, 65, 79
Эратосфен 15
Эрдеш (Erdos P.) 31, 55
Якобчик (ЛакбЬсгук F.) 80
Янишевский (Janiszewski Z.) 8

ОГЛАВЛЕНИЕ
И. Г. Мельников. Вацлав Серпинский (к восьмидесятиле-
восьмидесятилетию со дня рождения) 7
От переводчика 9
Предисловие 10
1. Что такое простые числа? 11
2. Простые делители натуральных чисел 12
3. Сколько существует простых чисел? 13
4. Как можно найти все простые числа, меньшие данного числа? 15
5. Простые числа близнецы 16
6. Гипотеза Гольдбаха 18
7. Гипотеза Гильбрайта 21
8. Разложение натурального числа на простые сомножители . . 22
9. Какими цифрами могут начинаться и заканчиваться про-
простые числа? 27
10. Число простых чисел, не превосходящих данное число . . 28
П. Некоторые свойства л-го по порядку простого числа ... 30
12. Многочлены и простые числа 32
13. Арифметические прогрессии, образованные из простых чисел 34
14. Малая теорема Ферма 35
15. Доказательство теорем, согласно которым имеется беско-
иечио много простых чисел каждого из видов 46 + 1, 4ft -f- 3
и 6А + 5 40
16. Некоторые гипотезы относительно простых чисел 43
17. Теорема Лаграижа 45
18. Теорема Вильсона 47
19. Разложение простого числа на сумму двух квадратов ... 51
20. Разложение простого числа на разность двух квадратов
и другие разложения 57
21. Квадратичные вычеты 62
90

22. Числа Ферма 65
23. Простые числа видов пп-\-\, пп"-\-\ и иекоторых других
видов 72
24. Три ошибочных теоремы Ферма 76
25. Числа Мерсенна 77
26. Простые числа в различных бескоиечных последовательно-
последовательностях ■ 80
27. Решение уравнений в простых числах 81
28. Магические квадраты, составленные из простых чисел ... 83
29. Несколько нерешенных задач, касающихся простых чисел 84
30. Гипотеза А. Шинцеля 85
Именной указатель 88

Вацлав Серпинский
Что мы энаеи и чего ие эиаеи
о простых числах
Л., Фиэматгиз, 1963 г., 92 стр. с нлл.
Редактор Н. М. Розенгауз
Техн. редактор А. А. Лукьянов
Корректор Л. А. Любович
Сдано в набор 9/V 1963 г. Подписано к пе-
печати 3/IX 1963 г. Бумага 84x108'/,,. Физ. печ. л. 2,875.
Усл. печ. я. 4,72. Уч.-изд. я. 4,71. Тираж 100 000 экз.
Цена книги 14 коп. Заказ М 1390.
Государственное издательство
физико-математической литературы
Москва, В-71, Ленинский проспект, 15
Типография № 2 ни. Ввг. Соколовой
' УЦБ и ПП Леисомархоза.
Ленинград. Измайловский пр., 29.