Глава 1 На заре арифметики

Глава 1

На заре арифметики

Как и у всего остального, у простых чисел тоже есть происхождение: свое начало они берут в системах счета. Простые числа появились одновременно с натуральными, но очень быстро выделились в виде особого набора специальных чисел.

Нет ничего более натурального, чем натуральные числа.

«Бог создал первые десять чисел, остальное — дело рук человека». Эти слова сказаны немецким математиком Леопольдом Кронекером (1823–1891) про натуральные числа, которые мы используем при счете: 1, 2, 3, 4, 5 и т. д. Кронекер имел в виду, что могучее здание математики построено на самой простой, элементарной арифметике. Если не углубляться в религию, то утверждение о том, что Бог дал нам первые десять чисел, означает, что эти числа всегда были частью природы.

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

Это создало потребность в конкретных способах счета. Представим себе пастуха, который выгоняет стадо на пастбище. Он должен быть уверен, что в загон вернется то же количество животных, которое он выпускал. Без системы счета самым естественным решением будет взять горсть гальки и класть один камень в сумку каждый раз, как из загона выходит одна овца. Затем, по возвращении, он должен вынимать один камень для каждой входящей в загон овцы, чтобы таким образом убедиться в том, что все овцы целы. Это, конечно, примитивная система подсчета. Кстати, слово подсчет (calculation) происходит от латинского слова calculus, означающего «галька, камешки». Такая галечная система не требует понятия числа. В терминах современной математики мы бы сказали, что пастух устанавливает взаимно однозначное (один к одному) соответствие между стадом овец и множеством камней.

Заметим, однако, что математическое понятие взаимно однозначного соответствия между двумя множествами появилось лишь в XIX в., поэтому было бы странным называть такой процесс подсчета наиболее естественным. Так что, используя слова «естественный» или «натуральный», по крайней мере в этом контексте, мы должны сделать некоторые разъяснения.

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

* * *

ВОСПРИЯТИЕ ЧИСЕЛ

Когда китайцы говорят о десяти тысячах звезд на небе, это не значит, что они их все посчитали. Это просто способ выразить очень большое число. Можно подумать, что для выражения такого понятия лучше подходит число миллиард. Но мы должны с самого начала учитывать, что наше непосредственное восприятие чисел ограничено пятью единицами. Если кто-то показывает пять пальцев одной руки и три пальца другой, мы практически сразу определяем общее количество в восемь пальцев, но для нас это почти что шифр. Когда же восемь объектов разложены на столе, нам придется посчитать их или визуально разделить на маленькие группы, чтобы узнать их количество. Поэтому нам очень трудно представить миллион объектов, если у нас нет непосредственного соответствия. Мы знаем, что значит выиграть миллион фунтов в лотерею, потому что мы знаем цену деньгам, и мы быстро проделываем мысленные расчеты, что на них можно купить. Но существует большая разница между таким пониманием и четким представлением о том, как выглядит выложенный в ряд миллион монет в один фунт (они покроют расстояние в 22,5 км).

С одного взгляда наш мозг способен распознать до пяти объектов. При больших количествах для подсчета приходится использовать другие стратегии.

* * *

Системы счета возникли на основе такого мощного процесса абстракции, который, по мнению многих специалистов, наряду с изучением языка является одним из самых серьезных достижений человечества за всю историю. Когда мы говорим «три», мы можем иметь в виду три овцы, три камня, три дома, три дерева, три чего угодно. Если бы приходилось использовать разные слова для описания количества разных объектов, первобытное сельскохозяйственное общество с самого начала было бы погребено под лавиной словесной информации. «Три» является абстрактным понятием, чисто ментальным образом, для которого требуется только одно слово и один знак, чтобы служить средством коммуникации в социальной группе.

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

Многие не любят математику, объясняя это тем, что она слишком абстрактна, как будто процесс абстракции является чем-то искусственным и неестественным.

Но это не так. Если бы мы не обладали способностью к абстракции, мы не смогли бы даже выработать общий язык. Иногда абстрактное мышление называют также непрактичным, но и это не соответствует действительности. Лишь наиболее абстрактный метод является наиболее практичным. Хорошим примером этого служит позиционная система счисления, которую мы используем в повседневной жизни самым «естественным» образом. В непозиционной системе символ, представляющий число, имеет одно и то же значение независимо от позиции, которую он занимает.

Например, в римской системе счисления число пять обозначается буквой V и имеет одно и то же значение в выражениях XV, XVI и VII. Однако если бы римская система была позиционной системой счисления, то в первом выражении символ V означал бы пять единиц, во втором — 50, а в третьем — 500.

Открытие позиционной системы счисления оказалось не совсем простым делом.

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

Цивилизация майя — одна из немногих древних цивилизаций, применявших позиционную систему счисления. Майя использовали только три символа: раковина обозначала ноль, точка — каждую единицу, тире — пять единиц.

Что такое простое число?

Возьмем любое число, например, 12. Мы знаем, что мы можем выразить это число по-разному как произведение других чисел:

12 = 2 х 6;

12 = 3 х 4;

12 = 2 х 2 х 3.

Далее мы будем называть эти числа «делителями». Таким образом, мы будем говорить, что 3 является делителем числа 12. Делитель — это меньшее число, на которое делится большее, а именно, 12 делится на 3. Аналогично мы можем сказать, что 5 является делителем 20, потому что 20 делится на 5. В данном контексте под словом «делится» мы подразумеваем тот факт, что если разделить число 20 на 5, то получится натуральное число, в данном случае 4, а остаток от деления будет равен нулю.

Разложение числа на множители иногда называют факторизацией: от латинского слова facere — «делать» или «производить», потому что каждый множитель «производит» исходное число. В выражении 12 = 3 х 4 число 3 является одним из множителей, которые «производят» число 12.

Соответственно, на вопрос: «Какие числа являются делителями числа 12?» можно ответить, что числа 2, 3, 4 и 6 будут делителями числа 12, потому что при делении 12 на любое из них получается целое число. Делителем любого числа также является 1, так как каждое число делится на единицу и еще на само себя. Например, делителями числа 18 являются следующие числа: 1, 2, 3, 6, 9 и 18.

Теперь сделаем то же самое для числа 7, а именно найдем его делители. Мы увидим, что число 7 делится только на единицу и на само себя. То же самое верно и для чисел 2, 3, 5, 11 и 13. Эти числа и являются «простыми».

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

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

* * *

ЗНАКИ ДЬЯВОЛА

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

Гэрберт Орильякский, избранный папой римским под именем Сильвестра II, был папой-математиком.

* * *

Основная теорема арифметики

Простые числа называют «кирпичами» в здании математики, «атомами» математики и «генетическим кодом» чисел. Дома строятся из кирпичей, все в природе состоит из атомов, а живые организмы определяются генетическим кодом. Все эти аналогии основаны на общем понятии: первичных элементах, из которых строится вся система. Рассмотрим теперь роль простых чисел в математике.

Как мы увидели, число может быть разложено на делители, или на множители. Так, число 12 можно представить в виде 3 x 4. Напомним, что при разложении на множители имеется в виду, что число 12 производится числами 3 и 4. Но мы также знаем, что число 12 может быть получено и из других чисел, например:

12 = 2 x 6 = 3 x 4 = 2 x 2 x 3.

Итак, процесс разложения числа на множители называется факторизацией. Напомним, именно этот процесс привел нас к точному определению простого числа, при факторизации которого мы получаем только единицу и само число в качестве множителей. Например, число 13 будет разложено так:

13 = 1 х 13.

Когда один из множителей в произведении повторяется, мы используем надстрочный индекс, равный количеству повторений. Например:

2 х 2 х 2 х 2 х 2 = 2⁵;

З х З х З х З = 3⁴.

В математике это называют «степенью». Читается это как 2⁵ (два в пятой степени) и З⁴  (три в четвертой степени).

В предыдущем примере мы представили число 12 в виде трех произведений с различными множителями: 2 и 6; 3 и 4; 2, 2 и 3. Только последнее из этих произведений содержит лишь простые множители. Рассмотрим другой пример, число 20:

20 = 2 x 10 = 2 x 2 x 5 = 4 x 5.

Только произведение 20 = 2 x 2 x 5 = 2² х 5 содержит лишь простые множители.

Перед нами встает следующий вопрос: можно ли любое наугад взятое число всегда разложить на простые множители? Другими словами, может ли оно быть представлено в виде произведения только простых чисел? Ответ на этот вопрос положителен. Более того, любое число можно разложить на простые множители единственным образом. Когда мы записываем число 20 в виде произведения простых множителей, 20 = 2² х 5, мы делаем это единственно возможным образом, учитывая, что порядок множителей не имеет существенного значения, то есть разложения 2 х 5 х 2 и 5 х 2 х 2 считаются одинаковыми. Эта теорема была сформулирована Евклидом и известна как «основная теорема арифметики». Она утверждает, что «любое натуральное число может быть представлено единственным образом в виде произведения простых множителей».

* * *

КАК НАЙТИ ПРОСТЫЕ ЧИСЛА

Чтобы разложить число на простые множители, для начала нужно написать исходное число слева от вертикальной линии. Затем проверить, делится ли число на 2, 3, 5 и т. д., то есть на простые числа, начиная с самых маленьких. Если делится, то мы записываем результат деления слева от черты и проделываем с ним то же самое. Процесс продолжается до тех пор, пока слева не появится единица. Тогда правый столбик будет содержать простые числа, которые являются множителями в разложении исходного числа.

* * *

Так что когда мы пишем 24 = 2³  х 3, мы утверждаем, что это единственный способ разложить число 24 на простые множители. Таким образом, название «основная теорема» полностью оправдано, поскольку это одна из основ арифметики. Кроме того, в этом смысле простые числа также играют важнейшую роль. Возвращаясь к вышеупомянутым сравнениям, можно сказать, что разложение 2³ х 3 является формулой ДНК числа 24; это — последовательность, состоящая из генов 2³  и 3, или из атомов 2 и 3, образующих элемент 24.

Следовательно, простые числа являются первичными элементами, из которых построены все числа. Слово «простой» (prime) происходит от латинского слова primus, означающего «первый» и включающего в себя оригинальное значение «первичный», или «примитивный», так как все числа могут быть порождены простыми числами. Так же как атомы образуют молекулы, простые числа образуют составные числа. Все известные химические элементы состоят из атомов, которые сочетаются друг с другом определенным образом. Русский химик Дмитрий Иванович Менделеев (1834–1907) создал периодическую систему элементов, расположив все химические элементы по группам. Однако не существует аналогичной таблицы для простых чисел, в которой они были бы сгруппированы в соответствии с неким правилом, не существует закона, который генерирует все простые числа без исключений. Простые числа появляются хаотическим образом и распределяются в ряду натуральных чисел без всякой видимой закономерности.

Простые числа: изобретение или открытие?

С появлением систем счисления одной из первых естественных задач была проверка того, является ли число четным или нечетным. Следующим шагом было разложение чисел на множители, что определило признаки деления, которые изучаются в начальной школе. Таким образом, в любой системе счета есть наборы чисел, определяемые своими свойствами, которые легко проверить. Но это не относится к простым числам. Единственное, что точно о них известно, это то, что они не могут быть четными (за исключением самого первого простого числа — 2), иначе они бы делились на два. Но и нельзя их рассматривать как что-то редко встречающееся, так как еще Евклид доказал, что множество простых чисел бесконечно. Позже мы рассмотрим элегантный способ доказательства этой идеи. Также нельзя недооценивать важность простых чисел, поскольку основная теорема арифметики определила им в математике главную роль. Поэтому, как уже говорилось, простые числа по праву стали предметом пристального изучения.

Когда мы говорим о предмете научного исследования, логично предположить, что он существует. Мы его уже обнаружили или еще нет, впоследствии мы можем его изучать или проигнорировать, но в любом случае он существует независимо от того, что мы о нем думаем. Так в определенный исторический момент бактерии стали для биологов объектом изучения. Никто не сомневается в том, что бактерии уже присутствовали в природе в качестве живых организмов задолго до появления биологов, на самом деле даже до появления вида человека. Никто из ученых не сомневается в этом. Однако в математике вопрос приобретает иную окраску. Являются ли простые числа открытием или изобретением человеческого ума? Существовали бы простые числа, если бы не было человека? Этот вопрос вызывал и продолжает вызывать много споров, что очень интересно для одних и неважно для других. Скорее всего, это один из вопросов, не имеющих ответа, и мы можем лишь высказывать свои мнения.

Но в отношении математических исследований есть действительно интересный момент: математики ведут себя как первопроходцы, вступающие в странный незнакомый мир, как будто математика на самом деле отделена от нашего мира. Это чувство неизведанного является самой сутью математических исследований и придает им поэтическую привлекательность. Немецкий физик Генрих Рудольф Герц (1857–1894) говорил: «Разве можно не испытывать такого чувства, будто математические формулы живут собственной жизнью, обладают собственным разумом? Кажется, что эти формулы умнее нас, умнее даже самого автора, что они дают нам больше, чем мы в них изначально заложили».

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

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

Существуют ли простые числа сами по себе, вне человеческого разума? Этот вопрос занимал немецкого физика Генриха Рудольфа Герца.

* * *

КОСТЬ ИШАНГО

Кость Ишанго, возможно, берцовая кость бабуина, с первого взгляда выглядит как некий инструмент. Она имеет рукоятку, за которую ее удобно держать, и заостренный кристалл кварца на конце. Она была найдена у истоков Нила, на границе между Угандой и Демократической Республикой Конго, и принадлежала первобытному племени, погребенному извержением вулкана. Этому инструменту около 20000 лет.

Кость Ишанго выставлена в бельгийском музее естественных наук в Брюсселе.

* * *

На кости имеются насечки в виде коротких прямых линий. Их детальное изучение привело к гипотезе, что эта кость не инструмент, а численная система для помощи в счете. В таком случае вполне вероятно, что кварцевый наконечник использовался для написания неких цифр. Другими словами, эта кость являлась примитивным калькулятором. Расположение насечек по столбцам предполагает операции сложения и умножения в системе счисления с основанием 12. Все числа справа — нечетные, но самое удивительное, что все числа слева являются простыми из промежутка от 10 до 20. Маловероятно, что эти знаки нанесены случайно, скорее всего, они указывают на существование некоторого серьезного метода вычислений.

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

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

Вопрос о существовании математических истин независимо от человека имеет третий компромиссный ответ, который допускает возможность того, что действительно существуют математические идеи, которые могут быть открыты, но они являются «психическими понятиями», предопределенными нашим генетическим наследием. Если это так, некоторые примитивные формы этих понятий должны существовать в природе. Например, существует несколько видов животных, которые совершенно точно могут считать. Одиночные осы могут подсчитывать количество живых гусениц, которых они оставляют рядом со своими яйцами в качестве пищи для вылупившихся личинок: это всегда в точности 5, 12 или 24. У ос рода Eumenes мы встречаем еще более удивительные примеры. Оса знает, какая особь вылупится из отложенного яйца: мужская или женская. Неясно, как ей удается установить пол будущего потомства, так как норки, в которых она откладывает яйца, совершенно одинаковы. Но самое удивительное, что оса оставляет пять гусениц рядом с яйцом мужской особи и десять — рядом с яйцом женской особи. Причина такого различия в том, что женские особи вырастают до гораздо больших размеров, чем мужские.

Для иллюстрации существования в природе более сложных понятий, таких как простые числа, можно привести любопытный пример некоторых видов так называемых периодических цикад, а именно Magicicada septendecim и Magicicada tredecim.

Названия видов septendecim и tredecim означают соответственно 17- и 13-летний жизненные циклы насекомых. Оба числа являются простыми, и зоологи разработали различные теории для объяснения выбора простого числа для жизненного цикла этих насекомых.

Возьмем, к примеру, вид Magicicada septendecim. Личинка цикады живет под землей и питается соками корней деревьев. Она проводит 17 лет в таком состоянии, а затем выходит на поверхность, чтобы превратиться во взрослое насекомое. Эта стадия длится всего несколько дней, во время которых цикада размножается и после этого умирает. Теория, объясняющая такой жизненный цикл цикады, выглядит следующим образом: взрослое насекомое защищается от паразита с жизненным циклом два года.

Если бы жизненный цикл цикады был кратен 2, оба вида встречались бы каждые 2, 4, 8 лет и так далее. Однако если жизненный цикл цикады является достаточно большим простым числом, например, 17, паразит и цикада могут встретиться раз в 34 года, так как 34 — первое число, кратное 17 и 2. Если бы, к примеру, жизненный цикл паразита составлял 16 лет, они бы могли встретиться раз в 16 х 17 = 272 года.

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

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

Решето Эратосфена

Поиск простых чисел всегда был сложной задачей. Один из первых известных методов приписывают Эратосфену из Кирены (273–194 до н. э.), древнегреческому математику, астроному и географу, который также заведовал Александрийской библиотекой. Метод получил название решета Эратосфена. Давайте посмотрим, как с помощью этого метода можно найти простые числа в первой сотне натуральных чисел.

Во-первых, составим таблицу со всеми натуральными числами от 1 до 100. Затем вычеркнем все числа, кратные двум: 4, 6, 8, 10 потом вычеркнем все числа, кратные трем: 6 (уже вычеркнули), 9, 12, 15. Затем проделаем то же самое для чисел, кратных пяти и семи.

Остались только простые числа.

Обратите внимание, что «просеивание» закончилось на числе 10, квадратном корне из 100. В общем случае, чтобы найти все простые числа, меньшие, чем заданное число N, нужно «просеять» все числа, которые меньше или равны квадратному корню из N. Это и дает метод нахождения простых чисел, который используется и сегодня, спустя более чем 2000 лет после изобретения, для поиска «малых простых чисел»: так называются простые числа, которые меньше 10 млрд.

* * *

РАЗМЕРЫ ЗЕМЛИ

Имя Эратосфена связано с методом нахождения простых чисел. Однако этот метод вовсе не является его самым важным достижением. На самом деле Эратосфен вошел в историю науки как первый человек, вычисливший размер Земли. Используя методы, доступные в III в. до н. э., он смог посчитать длину полярной окружности с погрешностью менее одного процента.

Карта мира, каким он был известен Эратосфену. Греческий ученый был первым, кто разделил изображение мира на равные части, проведя параллели, хотя его меридианы были расположены неравномерно.

* * *

Сколько существует простых чисел?

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

С первого взгляда видно, что простые числа совершенно непредсказуемы. Например, между 1 и 100 простых чисел больше, чем между 101 и 200. Всего в первой тысяче 168 простых чисел. Можно предположить, что если продолжить нашу таблицу, то с каждой тысячей количество простых чисел будет увеличиваться. Но это не так. Уже известно, что, например, среди тысячи чисел между 10¹⁰⁰ и 10¹⁰⁰ + 1000 находится лишь два простых числа. И эти числа состоят более чем из ста цифр!

Казалось бы, чтобы найти закономерность, надо составить таблицу, которая содержит все простые числа. Все? А что, если их очень много? Хотя, имея в распоряжении современные методы, можно проделать с числами всевозможные тесты, позволяющие найти закономерности. Ведь понятно, что в случае конечных множеств, даже очень больших, закономерность может быть найдена или, по крайней мере, можно придумать правило, которое для данного множества будет работать. Однако ситуация радикально меняется, если мы имеем дело с бесконечными множествами, поэтому мы должны сначала выяснить, является ли множество простых чисел бесконечным. Эта задача также была решена Евклидом. Его метод так остроумен, элегантен и прост, что стоит рассмотреть его подробнее.

Возьмем ряд последовательных простых чисел, например: 2, 3, 5.

Затем перемножим их:

2 х 3 х 5 = 30.

Теперь добавим к результату единицу:

2 х 3 х 5 + 1 = 30 + 1 = 31.

Ясно, что если разделить 31 на любое простое число из этого ряда — 2, 3, 5, — то в остатке получится 1:

31/2 = 15 + 1

31/3 = 10 + 1

31/5 = 6 + 1.

Это означает, что число 31 не делится на наши числа. Это справедливо и в общем случае: если взять ряд последовательных простых чисел, перемножить их и добавить единицу, то полученное число не будет делиться ни на одно из исходных простых чисел. Этот простой факт и лежит в основе доказательства Евклида.

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

{2, 3, 5, 7, 11, 13}.

Перемножим их и добавим единицу:

2 х 3 х 5 х 7 х 11 х 13 + 1 = 30 030 + 1 = 30 031.

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

30 031 = 59 х 509.

Евклид уже доказал, что любое натуральное число может быть единственным образом разложено в произведение простых множителей. В случае с числом 30 031, которое является составным числом, ясно, что для его разложения в произведение простых множителей чисел в списке {2, 3, 5, 7, 11, 13} будет недостаточно, то есть этот список неполон.

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

1) простое число, которого нет в списке;

2) составное число, при разложении которого на простые множители получаются простые числа, не входящие в список.

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

К сожалению, этот метод не позволяет найти все простые числа, хотя он является важной отправной точкой, так как указывает на масштаб проблемы и позволяет разрабатывать различные стратегии для ее решения. Можно было бы подумать, что не так уж важно доказывать, что множество простых чисел бесконечно, ибо это подсказывает нам интуиция. Однако с простыми числами нужно быть очень осторожными, ведь они настолько «редко» встречаются, как будто могут закончиться в любой момент. Тем не менее, теорема Евклида убедительно доказывает, что этого не произойдет.