Путеводитель для влюбленных в математику Шейнерман Эдвард
Переводчик Алексей Огнёв
Научный редактор Михаил Гельфанд
Редактор Александр Петров
Руководитель проекта А. Тарасова
Корректоры Е. Сметанникова, М. Ведюшкина
Компьютерная верстка М. Поташкин
© Edward Scheinerman, 2017
Originally published by Yale University Press
© Издание на русском языке, перевод, оформление. ООО «Альпина нон-фикшн», 2018
Все права защищены. Данная электронная книга предназначена исключительно для частного использования в личных (некоммерческих) целях. Электронная книга, ее части, фрагменты и элементы, включая текст, изображения и иное, не подлежат копированию и любому другому использованию без разрешения правообладателя. В частности, запрещено такое использование, в результате которого электронная книга, ее часть, фрагмент или элемент станут доступными ограниченному или неопределенному кругу лиц, в том числе посредством сети интернет, независимо от того, будет предоставляться доступ за плату или безвозмездно.
Копирование, воспроизведение и иное использование электронной книги, ее частей, фрагментов и элементов, выходящее за пределы частного использования в личных (некоммерческих) целях, без согласия правообладателя является незаконным и влечет уголовную, административную и гражданскую ответственность.
Рейчел и Мордехаю
Просветительский фонд «Эволюция»
основан в 2015 году сообществом российских просветителей.
Цель фонда – популяризация научного мировоззрения, продвижение здравомыслия и гуманистических ценностей, развитие науки и образования. Одно из направлений работы фонда – поддержка издания научно-популярных книг.
Каждая книга, выпущенная при содействии фонда «Эволюция», тщательно отбирается серьезными учеными. Критерии отбора – научность содержания, увлекательность формы и значимость для общества.
Фонд сопровождает весь процесс создания книги – от выбора до выхода из печати. Поэтому каждое издание библиотеки фонда – праздник для любителей научно-популярной литературы.
Больше о работе просветительского фонда «Эволюция» можно узнать по адресу
Предисловие
Математика прекрасна и приносит радость[1]. Нам знакомы шедевры в разнообразных областях деятельности человека. В изобразительном искусстве – «Мона Лиза», в театре – «Гамлет», в биологии – открытие роли ДНК в наследственности, в археологии – расшифровка иероглифов с помощью Розеттского камня, в физике – уравнение E = mc. Понять шедевры математики сложнее, поэтому я просто хочу поделиться с вами собственными предпочтениями.
Музеи изобразительных искусств хранят огромные коллекции, но выставляют на всеобщее обозрение лишь некоторые предметы. Так же и я отобрал некоторые шедевры и хочу представить их вашему вниманию.
Эта книга не настолько мала, чтобы я ограничился одной-единственной математической драгоценностью, но если бы мне предложили выбрать таковую, я бы остановился на доказательстве того факта, что простых чисел бесконечно много[2]. Этот пример демонстрирует, чем я руководствовался, выбирая темы для своего «Путеводителя»:
• Они неизвестны людям, не имеющим отношения к математике. Читатели могут знать, что такое простое число, но вряд ли они задумывались над вопросом, сколько всего существует простых чисел.
• Они высвечивают идею доказательства, и в особенности технику доказательства от противного.
• Для их понимания не требуется вузовская подготовка – хватит знаний, полученных в средней школе.
• Они полны сюрпризов. Ответы неочевидны. Легко понять, что существует бесконечно много нечетных чисел или идеальных квадратов, но нет четкого закона, по которому простые числа следуют друг за другом. Поразительно, что короткая цепочка рассуждений приводит нас к неоспоримому выводу о том, что простые числа никогда не иссякнут.
• Они имеют практическое применение, например в случае простых чисел это криптография.
Хотя некоторые темы, затронутые в нашем «Путеводителе», не обладают всеми перечисленными свойствами, каждая глава книги рассказывает о математическом чуде, которое удивит и заинтригует читателя.
В 1940 году британский математик Годфри Харди[3] опубликовал «Апологию математика» – личное оправдание того обстоятельства, что он потратил жизнь на изучение абстракций. В книге Харди рассказывал, сколько радости и блаженства он испытал. Но говорить о радости занятия математикой – все равно что говорить о радости плавания. Пока вы лично не поплещетесь в прохладной воде, вы не поймете, насколько это здорово.
Боюсь, для многих получение математических знаний было безрадостным процессом. Представьте, что занятия словесностью свелись к изучению орфографии и пунктуации, а чтение «Гарри Поттера» и сочинение своих собственных историй оказались под запретом. Случись такое, школьники вряд ли бы стали любить литературу.
Вот несколько утрированная иллюстрация того, как некоторые воспринимают изучение математики:
• В начальной школе мне рассказали, что у меня было десять апельсинов, а потом три апельсина кто-то отнял. Зачем? Я бы и так с ним поделился.
• В средней школе я нашел общий знаменатель и подсчитал какие-то проценты.
• В старших классах меня заставили запомнить формулу корней квадратного уравнения[4], я до сих пор могу написать ее, но так и не понял, зачем она мне нужна.
Разумеется, в математике есть много прикладных задач, но среди прочего она обладает великой красотой. Моя цель – поделиться хотя бы частью этой красоты.
Математика изучает числа и геометрические фигуры, и я выбрал эти темы для первых двух частей «Путеводителя».
В части под названием «Число» мы исследуем некоторые необычные числа (например, 2 и e) и последовательности чисел (например, простые числа и числа Фибоначчи). Кроме того, читателя ждет множество неожиданных вещей: он узнает, как одна бесконечность может быть бесконечнее другой и почему в нашем мире на цифру 1 начинается большее количество чисел, чем на цифру 9.
В части под названием «Геометрические фигуры» мы вспомним хороших двумерных знакомых (например, круги и окружности), а также познакомимся с трехмерными фигурами (например, платоновыми телами) и с фигурами, чья размерность больше одного, но меньше двух (с фракталами). Нас ждет немало сюрпризов. Так, все знают, как застелить пол плитками в форме квадратов или равносторонних шестиугольников, но такое возможно и в случае с равносторонними пятиугольниками. Ну что, я вас удивил? Заинтриговал? Этого-то я и добивался.
Завершается книга частью под названием «Неопределенность», там мы рассмотрим идеи случайности, непредсказуемости и интуитивных вычислений. Вы узнаете о том, как чрезвычайно надежный медицинский тест может давать неточные результаты, есть ли смысл в рейтингах и как правильно выбрать кандидата, когда их число больше двух. Как и прежде, вас ждут сюрпризы.
Последовательность глав произвольна, и вы можете читать их в любом удобном вам порядке[5]. Сложность материала разнится от главы к главе, так что вы ничего не потеряете, если пропустите самые заковыристые главы, чтобы вернуться к ним впоследствии.
Не торопитесь. Все главы короткие, но чтобы уловить их основные идеи, нужно время. Я часто прибегаю к вычислениям или алгебраическим выкладкам, чтобы подвести базу под те или иные тверждения. Вы лучше поймете, о чем идет речь, если вооружитесь карандашом и бумагой. Иногда вам нужно будет перечитывать какие-то абзацы, чтобы разобраться во всем досконально.
Можно читать не в одиночку. Предложите приятелю обсудить идеи из книги. Вам придется объяснять их таким образом, чтобы он уловил, о чем вы говорите. Это поможет вам лучше овладеть концепциями, о которых вы прочитали.
Главы устроены так, что самые замысловатые идеи расположены в конце. Лучше всего читать каждую главу последовательно с начала. Возможно, в какой-то момент вы решите остановиться и перейти к следующей главе.
На обложке изображено множество решений уравнения:
(x + y – 1) = xy. (*)
Какая пара чисел (x, y) удовлетворяет этому уравнению? Например, x = 1 и y = 0 при подстановке в левую и правую часть дадут одно и то же число, а именно 0. Если мы подставим x = –1 и y = 1, обе части (*) будут равны 1. Другими словами, пары (1, 0) и (–1, 1) являются решениями уравнения. Обратите внимание, что пара (0, 0) не является решением.
Существует бесконечно много решений уравнения, например x = 0,70711… и y = –0,41401… Если мы подставим эти числа в формулу, обе части будут равны –0,03548…
Бесконечное множество решений этого уравнения можно изобразить с помощью графика, если нанести на плоскость точки с координатами (x, y), где оба числа удовлетворяют уравнению (*). В этом случае мы получим изображение кривой в виде сердца, нарисованной на обложке.
Вы еще не полюбили математику? Когда дочитаете книгу, непременно полюбите.
Я хочу поблагодарить тех, кто давал плодотворные отзывы и полезные комментарии во время работы над книгой: Мордехая Леви-Эйчел, Джошуа Минкина, Йони Надив, Эми Шейнерман, Дэниела Шейнермана, Иону Шейнермана, Леонору Шейнерман, Наоми Шейнерман и Рейчел Шейнерман. Они читали черновик книги и давали полезные советы[6].
При подготовке книги к печати я получил замечательные отзывы рецензентов. О многих из этих людей я не знаю ничего, но имена некоторых, к счастью, мне известны. Спасибо за комментарии и энтузиазм Кристофу Бёрджерсу, Анне Лачовски и Джаядеву Атрейя.
Также я хочу поблагодарить Арта Беньямина за информацию о техасском холдеме в главе 19. Этот пример можно найти в задаче из книги Стюарта Айзера «Доктрина шансов: вероятностные аспекты азартных игр» (The Doctrine of Chances: Probabilistic Aspects Of Gambling).
Наконец, огромное спасибо за помощь издательству Йельского университета. Прежде всего – Джо Каламиа за его энтузиазм, множество полезных рекомендаций и ответы на мои непрерывные вопросы. Также я благодарю Энн-Мэри Имборнони за помощь при подготовке финальной версии, Лиз Кейси за дотошную редактуру, Соню Шэннон за дизайн, а Томаса Старра за великолепную обложку.
Прелюдия: теорема и доказательство
Джон Китс. Ода к греческой вазе
- «Краса есть правда, правда – красота»,
- Земным одно лишь это надо знать[7].
Красота – это первый критерий: в мире не найдется места для уродливой математики.
Г. Х. Харди. Апология математика
Что мы имеем в виду, когда говорим о чем-либо, что это правда? В науке истина открывается через наблюдения, часто во время эксперимента. Мы знаем, что планеты вращаются вокруг Солнца по эллиптическим орбитам – к такому выводу пришел Иоганн Кеплер[8], дотошно изучив данные, полученные Тихо Браге[9]. Мы знаем, что скорость света в вакууме – это постоянная величина, – знаем опять-таки на основе повторяющихся непосредственных наблюдений.
На самом деле орбиты планет не совсем эллиптические, потому что притяжение Солнца в данном случае не единственный воздействующий фактор, гравитационные поля планет тоже влияют друг на друга. И мы не знаем наверняка, что скорость света в нашей галактике совпадает со скоростью света, скажем, в галактике Андромеды, потому что мы еще не добрались туда и не поставили необходимые эксперименты.
В науке истина не абсолютна – это цепочка приблизительных суждений, становящихся все более точными. Нам кажется, что Земля плоская, и для большинства повседневных дел это на редкость верное приближение. Однако если мы намерены предпринять путешествие на значительное расстояние от дома, такое приближение становится ошибочным. Гораздо лучше будет считать Землю шарообразной. Эта модель работает прекрасно, пока мы не начинаем путешествовать на куда большие дистанции, и тогда гораздо лучше считать Землю сфероидом, сплющенным на полюсах: длина экватора немного больше, чем длина линии сечения Земли плоскостью, проходящей через полюса[10]. Эта геометрическая форма была предсказана теорией и затем подтверждена экспериментальными данными.
В отличие от остальных наук, в математике истина абсолютна. Когда мы утверждаем, что сумма двух нечетных чисел – четное число, мы подразумеваем, что это всегда так, со стопроцентной гарантией. Откуда мы знаем? Дело в том, что мы можем доказать это.
Математическое доказательство приводит к полной уверенности. В других сферах человеческой деятельности тоже используется слово «доказательство». Например, экспертиза ДНК способна доказать вину или невиновность подозреваемого. Точность этой экспертизы высока, но не идеальна. ДНК-следы, найденные на месте преступления, могут быть испорчены. Или вдруг у преступника обнаружится брат-близнец. ДНК-следы ничего не говорят о том, что совершил обвиняемый, даже если он действительно побывал на месте преступления.
В математике критерии истины и проверки на истинность абсолютны. Верные математические утверждения называют теоремами. Вот простой пример: Сумма двух нечетных целых чисел – четное целое число. Например, 3 и 11 – нечетные числа, а их сумма 3 + 11 = 14 – четное число. Утверждение о том, что сумма двух нечетных чисел – четное число, имеет абсолютную силу и не допускает исключений.
Откуда мы это знаем? Мы можем снова и снова придумывать пары нечетных чисел и всякий раз убеждаться в том, что их сумма – четное число. Так работают естественные науки, но не математика. Мы абсолютно уверены, что теорема верна, потому что можем привести доказательство.
Чтобы не быть голословным, приведу это доказательство здесь. Вначале нам нужно точно договориться, что значит «четное» и «нечетное». Вот определения:
• Целое число X называется нечетным, если мы можем найти такое целое число a, что X = 2a + 1. Например, 13 – нечетное число, потому что его можно выразить как 2 6 + 1.
• Целое число X называется четным, если мы можем найти такое целое число a, что X = 2a. Элегантная формулировка: четное целое число – результат удвоения другого целого числа. Например, 20 четное, потому что 20 = 2 10.
После этих определений мы можем перейти к доказательству теоремы о том, что сумма двух нечетных целых чисел – четное число[11].
Доказательство. Пусть X и Y – нечетные целые числа. Это означает, что X = 2a + 1 и Y = 2b + 1, где a и b – целые числа. Сумма X и Y может быть представлена следующим образом:
X + Y = (2a + 1) + (2b + 1) = 2a + 2b + 2 = 2 (a + b + 1).
Итак, X + Y представляет собой удвоенное цлое число. Таким образом, X + Y – четное число.
Доказывать теоремы непросто, но это гораздо увлекательнее, чем читать чужие доказательства, потому попробуйте доказать следующее: результат перемножения двух нечетных целых чисел – тоже нечетное число. Попытайтесь справиться с задачей самостоятельно, а потом сверьтесь с доказательством в конце раздела[12].
Другие математические теоремы гораздо интереснее, а их доказательства гораздо сложнее, но цель у них все та же: обосновать математический факт со стопроцентной уверенностью.
Итак:
Теорема – это математическое утверждение, требующее доказательства своей неопровержимой истинности.
Интересные теоремы красивы. Надеюсь, этот «Путеводитель» поможет вам видеть математическую красоту и наслаждаться ею.
Какие три слова жаждут услышать математики?
Конечно, нам греет душу фраза: «Я люблю тебя», но в данном случае речь идет о других заветных словах: «Quod erat demonstrandum». В переводе с латинского они означают: «Что и требовалось доказать» – и обычно завершают математическое доказательство. Впрочем, немногие пишут эту фразу целиком, большинство ученых ограничиваются аббревиатурой QED. К сожалению, и она уже вышла из моды, и сейчас в конце доказательства принято использовать символ, например небольшой квадрат: .
Часть I
Число
Глава 1
Простые числа
Физик Ричард Фейнман[13] верил: если человечество столкнется с опасностью потери всего научного знания, но у него будет возможность передать потомкам всего одну фразу о науке, эта фраза должна описывать, как атомы образуют материю[14]. Продолжим фантазировать в том же духе. Если бы мы могли передать следующему поколению всего одну математическую идею, это, как мне кажется, должен быть ответ на вопрос: как много существует простых чисел?
Математическая мысль начинается со счета. Мы используем для счета натуральные числа: 1, 2, 3 и т. д. Отсутствие объектов для счета – и необходимость подобрать число для этого отсутствия – приводит нас к понятию нуля. Когда мы складываем или умножаем натуральные числа, результат всегда представляет собой другое натуральное число. Но вычитание внушает беспокойство. Все хорошо, когда мы вычитаем три из пяти: 5 – 3, но если мы поступим наоборот, то получится 3 – 5, и результат не будет натуральным числом. Мы восполняем этот недостаток, вводя отрицательные числа: –1, –2, –3 и т. д.
Множество всех натуральных и полученных при их вычитании отрицательных чисел вместе с нулем называют целыми числами. Математики используют стилизованную букву Z, чтобы обозначить все целые числа:
= {…, –4, –3, –2, –1, 0, 1, 2, 3, 4, …}.
Когда мы делим целые числа друг на друга, возникает загвоздка. В то время как мы можем складывать, перемножать целые числа и вычитать их друг из друга в полной уверенности, что получим целое число, результат деления одного целого числа на другое иногда оказывается целым числом, а иногда и нет.
Возьмем два положительных целых числа а и b. Мы говорим, что а делится на b, если частное a / b – тоже целое число. Мы называем a – делимым, b – делителем.
Например, 24 делится на 6 (потому что частное от деления – целое число), но не на 7 (потому что частное не является целым числом). Всякое положительное целое число делится само на себя: если а – положительное целое число, то частное от а / а равно 1, и это, разумеется, целое число. Также всякое положительное целое число делится на 1, потому что, если а – положительное целое число, результат деления а / 1 равен а.
Положительное целое число называется простым, если у него есть ровно два делителя: 1 и оно само.
Например, 17 – простое число, потому что 1 и 17 – его единственные делители. По той же причине 2 – простое число.
С другой стороны, 18 не является простым числом, потому что помимо 1 и самого себя оно делится на 2, 3, 6 и 9. Такие числа, как 18, называют составными. Если говорить математическим языком, то положительное целое число называют составным, если у него есть другие делители помимо 1 и самого себя.
Размежевание чисел на простые и составные касается всех натуральных чисел, кроме 1. Мы выделяем 1 в отдельную категорию и называем единичным элементом, или единицей[15]. Кого-то расстраивает тот факт, что Плутон больше не причисляют к планетам, другие раздражены тем, что 1 не считается простым числом.
Если подытожить, у нас есть три категории положительных целых чисел:
• единица с одним положительным делителем;
• простое число с двумя положительными делителями;
• составное число с тремя и более положительными делителями.
Отмечу, что 1 – единственное в своем роде число, а вот составных чисел бесконечно много: 4, 6, 8, 10, 12 и т. д. – составные числа (и таких еще много).
Но сколько же простых чисел существует?
Разложить число на множители означает представить его в виде произведения. Рассмотрим число 84. Мы можем разложить его на множители несколькими способами, например:
2 42; 3 28; 12 7; 2 6 7; 21 4.
В пределе разложить на множители означает найти произведение простых чисел, например: 84 = 2 2 3 7. Нельзя разбить эти множители на части, потому что каждый из них представляет собой простое число. Разумеется, мы можем добавить какое-то количество единиц, например:
84 = 1 1 2 2 3 7,
но дополнительные множители усложняют, а не упрощают выражение, другие множители от этого не становятся меньше[16].
Возьмем другой пример: 120. Мы можем представить 120 как 12 10 и затем 12 как 2 2 3, а 10 – как 2 5. Это дает:
120 = (2 2 3) (2 5). (A)
С другой стороны, мы можем начать так: 120 = 4 30 и далее заметить, что 4 = 2 2, а 30 = 2 3 5. Вместе это дает:
120 = (2 2) (2 3 5). (B)
Важно отметить, что простые числа в выражениях (A) и (B) одинаковые, различается лишь порядок, в котором они перемножаются. Это показано на рисунке.
Любой способ представления числа 120 в качестве произведения простых чисел дает один и тот же результат.
Эта единственность разложения на множители зафиксирована в следующей теореме[17].
Теорема (основная теорема арифметики). Любое положительное целое (натуральное) число может быть разложено на простые множители единственным образом (если пренебречь порядком множителей)[18].
(Здесь необходимо небольшое пояснение. В случае, скажем, числа 30 это утверждение достаточно ясно. Мы можем представить 30 как 2 3 5 или как 5 3 2 – разницы нет, отличается лишь порядок множителей. Простое число имеет всего один простой множитель – само себя. Например, множитель 13 – это 13. Но как быть с 1? Принято говорить, что пустое произведение[19] равно единичному элементу; таким образом, произведение отсутствующих элементов равно 1.)
Сочетая простые числа, мы выстраиваем все положительные целые числа. Простые числа – это атомы умножения.
Вернемся к вопросу: сколько всего простых чисел существует? Ответ – на следующей строчке.
Теорема. Простых чисел бесконечно много.
Утверждение приписывают Евклиду[20]. Доказательство этой теоремы – математическая жемчужина. Мы не можем доказать ее методом перебора. Очевидно, что время от времени в числовом ряде попадаются простые числа. Вот несколько первых простых чисел:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 и 67.
Но чем дальше мы идем по последовательности простых чисел, тем обширнее становятся промежутки между ними. Если посмотреть на перечень выше, можно увидеть, что два числа отстоят друг от друга максимум на 6 единиц (например, 53 и 59). Но простые числа 89 и 97 отстоят друг от друга на 8 единиц, все целые числа между ними составные. Или вот другой пример: 139 и 149 – их отделяет 10 единиц. Чем дальше мы двигаемся, тем быстрее увеличиваются промежутки между соседними простыми числами. Можно предположить, что в конечном итоге простые числа должны совсем исчезнуть. На самом деле, хотя они и встречаются все реже, их список в числовом ряду не имеет конца. Впрочем, прежде чем говорить об этом уверенно, мы должны привести доказательство.
Ключевая идея – задаться вопросом: а что, если?..
А что, если количество простых чисел конечно? Если мы продемонстрируем, что предположение: «Количество простых чисел конечно» – приводит к абсурдному выводу, то будем считать его ложным[21]. Вслед за Шерлоком Холмсом мы найдем истину, отбросив невозможные варианты, и у нас получится, что простых чисел бесконечно много.
Вот что нам надо будет сделать:
1. Предположить, что количество простых чисел конечно;
2. Показать, что это предположение ведет к невозможному выводу;
3. Сделать умозаключение, что, раз предположение ведет к логическому противоречию, оно ложно;
4. Вывести из этого, что простых чисел бесконечно много.
А теперь перейдем к делу. Предположим, что простые числа можно пересчитать, и посмотрим, к чему это приведет.
Если количество простых чисел конечно, должно существовать наибольшее простое число P – крайнее в ряду простых чисел. В таком случае полный перечень простых чисел будет выглядеть так:
2, 3, 5, 7, 11, 13, …, P.
Перемножим все эти числа и приплюсуем единицу. Назовем получившееся гигантское число N:
N = (2 3 5 7 11 13 … P) + 1.
Число N – простое[22]? Наше предположение заставляет нас ответить: нет, потому что N больше P, последнего простого числа. Значит, N – составное число, и его можно разложить на множители. Здесь мы попадаем в западню.
Мы знаем, что у N есть простые делители. Может ли таким делителем быть 2? Мы утверждаем: нет. Посмотрите на формулу для вычисления N и обратите внимание, что число в скобках четное, потому что среди множителей присутствует 2:
N = ( 3 5 7 11 13 … P) + 1.
Таким образом, N на единицу больше некоторого гигантского четного числа. Другими словами, N – нечетное, следовательно, оно не делится на 2.
Ну и ладно. Мы же знаем, что у N есть простой делитель, так что нет ничего страшного в том, что 2 не подходит. Как насчет 3? Посмотрим снова на число в скобках и обнаружим, что среди множителей есть 3:
N = (2 5 7 11 13 … P) + 1.
Таким образом, N на единицу больше некоторого гигантского числа, делящегося на 3. Это означает, что при вычислении частного N / 3 мы получим остаток 1. Следовательно, N не делится на 3.
Видите, куда мы движемся? Возьмем очередное простое число, 5. Мы утверждаем, что N не делится на 5, потому что оно на единицу больше числа, без остатка делящегося на 5:
N = (2 3 7 11 13 … P) + 1.
Точно так же мы доказываем, что N не делится ни на 7, ни на 11, ни на 13 и ни на какое угодно другое простое число!
К чему мы пришли? Наше предположение о том, что количество простых чисел конечно, привело нас к двум выводам:
– N делится на некое простое число;
– N не делится ни на какое простое число.
Но это же абсурдно! Из ловушки можно выбраться, только если признать, что предположение о конечном количестве простых чисел было ложным. Таким образом, получается, что простых чисел бесконечно много.
Представленное нами доказательство относится к разряду доказательств от противного. Мы предположили, что утверждение, обратное тому, которое мы хотим доказать, верно, затем продемонстрировали, что это приводит к безвыходной ситуации, после чего сделали умозаключение, что наше предположение ложно, а утверждение, требующее доказательства, истинно. Путеводная путаница, софистика-эквилибристика!
Есть и другой способ доказательства: создать некий механизм по производству простых чисел. Мы засыпаем в него пригоршню простых чисел и – вуаля! – оттуда высыпаются новые простые числа. Вот как работает эта машина.
Зачерпнем полдюжины простых чисел: 2, 3, 5, 7, 11 и 13. Перемножим их и приплюсуем единицу:
(2 3 5 7 11 13) + 1 = 30 031.
Ясно, что 30 031 не делится на 2, – это легко заметить, потому что последняя цифра нечетная. На 3 оно тоже не делится (потому что на единицу больше, чем 2 3 5 7 11 13, которое делится на 3). Точно так же оно не делится на 5, 7, 11 и 13. Стало быть, или это число само простое, или его можно разложить на простые множители, не входящие в наш перечень. Кости выпали так, что число 30 031 – составное. Оно раскладывается на простые множители следующим образом: 59 509. Этих чисел не было в нашем перечне.
Возьмем их и предыдущие полудюжины чисел и построим новое число:
(2 3 5 7 11 13 59 509) + 1,
что равно 901 830 931. Кости выпали так, что число оказалось простым[23].
Мы можем добавить его в наш перечень и наштамповать так еще много чисел – либо простых, либо разложимых на простые множители. Эта операция позволяет бесконечно получать все новые и новые простые числа.
Это не единственное доказательства того, что простых чисел бесконечно много. Вот вам еще одно.
Как и в первом доказательстве, предположим, что количество простых чисел конечно, и покажем, что это предположение ведет к противоречию. Представим, что самое большое простое число равно P, и составим перечень простых чисел:
2, 3, 5, 7, 11, 13, …, P.
Пусть N – результат перемножения всех этих чисел:
N = 2 3 5 7 11 13 … P.
Теперь давайте подумаем обо всех числах от 1 до N включительно. Каждое из них (за исключением 1) делится на одно или несколько простых чисел; иными словами, любое число (кроме 1) делится на какое-то простое число.
Сколько чисел от 1 до N делится на 2? Очевидно, что половина (четные числа). Вычеркнем их и оставим лишь нечетные:
1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, …
Количество целых чисел между 1 и N, которые мы вычеркнули, равно N / 2.
Вычеркнем из оставшихся чисел те, которые делятся на 3. Вот что получится:
1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, …
Мы удалили треть оставшихся чисел[24]. Осталось две трети, а от изначального количества –
Продолжим в том же духе и вычеркнем числа, делящиеся на 5, удалив таким образом пятую часть оставшихся чисел. Получится чисел. Вот что останется:
1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 77, 79, …
Дальше мы вычеркиваем числа, делящиеся на 7, оставив шесть седьмых от нашего перечня, и будем двигаться по этому пути, пока не дойдем до числа P.
В конце концов количество тех чисел, которые мы не вычеркнули, станет равно
Так как все числа от 1 до N, кроме 1, делятся на какое-то простое число, выражение (C) должно быть равно 1. Верно? Вспомним, что N = 2 3 5 7 11 13 … P, подставим это произведение в выражение (C) и перегруппируем множители:
Это дает 1 2 4 6 … (P – 1), что существенно больше 1! Выражение (C) должно быть равно 1, но очевидным образом не равно 1. Ошибка заключалась в изначальном предположении о том, что количество простых чисел конечно. Следовательно, их бесконечно много.
Есть много захватывающих вопросов о простых числах. Здесь я расскажу про две самые печально известные проблемы.
Хотя простых чисел бесконечно много, они встречаются все реже и реже, когда мы последовательно двигаемся от единицы к бесконечности. Позже (в главе 7) мы проанализируем среднюю разность между двумя соседними большими простыми числами. Однако простые числа все равно часто встречаются рядом, отличаясь на две и более единицы (единственная пара с отличием на один – 2 и 3). Если простые числа отличаются на две единицы, их называют простыми числами-близнецами, или парными простыми числами. Наименьшая пара близнецов – числа 3 и 5. Между 1 и 10 000 есть 205 пар близнецов, последние – числа 9929 и 9931.
Вопрос: простых чисел-близнецов бесконечно много?
Надо признать, что это неизвестно до сих пор.
Вот другой вопрос. Принято считать, что впервые его поставил немецкий математик Кристиан Гольдбах (1690–1764). Ему стало любопытно: какие четные числа (кроме 2) можно представить в качестве суммы двух простых? Вот пример:
Вопрос: можем ли мы продолжать этот ряд бесконечно? Гольдбах предположил, что любое четное число (за исключением 2) представляет собой сумму двух простых.
Но на самом деле мы до сих пор не знаем этого наверняка.
Изучение простых чисел относится к области математики под названием теория чисел. Британский математик Годфри Харди говорил: «До сих пор никто не обнаружил, как применить теорию чисел в военных целях».
Харди не мог предвидеть появления глобальной компьютерной сети и того факта, что безопасность в сети будет зависеть от простых чисел. Каким образом?
Пусть P и Q – два больших простых числа, скажем стозначных. Перемножить их – титанический труд для человека, но компьютер может посчитать произведение N = P Q мгновенно. В то же время мы угодим в тупик, если попытаемся выяснить, какие два простых множителя дают N при умножении. Никто не знает эффективного алгоритма разложения таких огромных чисел на простые множители[25].
(Как это ни странно, определить, простое число или составное, можно достаточно быстро; однако найти простые множители больших чисел совсем не просто.)
Удивительно, однако эта диспропорция – легко перемножить, сложно разложить на множители – легла в основу создания шифров. Криптографическая система с открытым ключом[26] устроена так, что можно раскрыть метод шифровки сообщений, но это не облегчит расшифровку засекреченных текстов. Мы не станем сейчас погружаться в детали метода, но основная идея состоит в том, что в процессе шифрования используется составное число N, представляющее собой произведение двух огромных простых чисел: N = P Q. Расшифровка требует знания конкретных простых чисел P и Q. Если мы знаем N, этого достаточно для шифровки, но не для декодирования, а найти его простые множители все еще чрезвычайно сложно.
Мы используем криптографическую систему с открытым ключом всякий раз, когда совершаем покупки в интернете. Прежде чем браузер вышлет продавцу номер нашей кредитной карты, он получает от продавца открытый ключ шифрования. Браузер шифрует номер карты с помощью метода, о котором мы рассказывали. Если перехватить ключ, это ничего не даст, потому что метод шифровки не говорит о методе расшифровки (а его знает только продавец). Когда зашифрованное сообщение приходит на компьютер продавца, индивидуальный метод расшифровки раскрывает номер карты лишь законному получателю информации.
Криптографическая система с открытым ключом имеет и военные применения, вплоть до системы приведения в боевую готовность ядерного оружия[27].
211 591 = 457 463.
Глава 2
Двоичная система счисления[28]
Древних римлян часто поминают дурным словом за их громоздкую систему записи чисел. Люди не любят римские числа, так как они обременяют вычисления. Никто не обрадуется перспективе перемножать XLVII и DCDXXIV. А вот задача умножить 47 на 924 не выглядит настолько угрожающей (хотя большинство из нас все равно побежит за калькулятором).
Впрочем, прежде чем сбрасывать римские числа со счетов как причудливый анахронизм, нам необходимо признать, что их основополагающий принцип – буквы вместо цифр – используется до сих пор. Этот ключевой аспект римских чисел обрел новое воплощение. Что легче прочесть?
• Реновация школ в нашем округе обойдется в 23000000 долларов.
• Реновация школ в нашем округе обойдется в 23 млн долларов.
Разумеется, я не стал разделять разряды в первом случае, чтобы число было сложнее прочесть (и я попал в точку, не правда ли?). Но, даже если проставить пробелы, фраза «Пентагон требует дополнительные 19 000 000 000 долларов» сложнее для восприятия, чем «Пентагон требует дополнительные 19 млрд долларов». Иногда удобнее использовать слова вместо чисел.
Мнимое преимущество позиционной системы счисления[29] – это то, что в ней проще производить вычисления. Но давайте задумаемся о том, сколько сил уходит на перемножение двух чисел. Во-первых, нам необходимо запоминать дополнительные математические данные. К тому же мы обязаны помнить таблицу умножения. Во-вторых, мы проделываем многоуровневую процедуру: сортируем числа по разрядам, умножаем по соответствующему правилу, получаем промежуточные данные, складываем.
Да, десятичные числа легче перемножать, чем их римские аналоги, однако это по-прежнему утомительно. Возникает вопрос, есть ли способ записывать числа, который бы облегчал вычисления. Мы выяснили, что да, есть, но для этого придется пожертвовать наглядностью.
Простейший способ записи чисел – единичная система счисления: мы просто записываем столько же символов (будем использовать цифру 1), сколько единиц в интересующем нас числе. Например, число 3 окажется трехзначным: 111. Сложение и умножение становятся исключительно простыми. Чтобы сложить 3 и 5, мы просто запишем два числа, 111 и 11111, друг за другом (без пробела) – и вот он, ответ: 11111111. Умножать тоже просто. Мы запишем одно число вертикально, а другое горизонтально и получим следующую таблицу:
Затем мы заполним таблицу, поставив единичку в каждом столбце и в каждой колонке:
Наконец, мы выпишем все единички в ряд и получим ответ: 111111111111111. Складывать и перемножать числа в единичной системе счисления существенно проще, чем десятичные или римские числа[30].
Разумеется, такая простота вычислений дается ценой титанических затрат внимания и времени. Никому не захочется прибегать к этому методу, чтобы перемножить 47 и 924.
Числа, записанные в двоичной системе счисления[31], не так привычны нам, как десятичные или римские, но с ними проще делать вычисления. Вот почему в компьютерах используется именно двоичная система. Чтобы разобраться, как она устроена, нам нужно припомнить особенности десятичной системы.
Читать бесплатно другие книги:
