Текст книги "Восемь этюдов о бесконечности. Математическое приключение"

Капрекар раскрывает тайны числа 6174

Индийский математик Даттарая Рамчандра Капрекар родился в 1905 г. Он закончил Мумбайский университет[14]14
  В то время Бомбейский.


[Закрыть] и посвятил себя преподавательской работе. Он проработал школьным учителем несколько десятилетий, но так никогда и не изучал высшую математику. Он внес вклад в развитие нескольких разных областей – в том числе магических квадратов, периодических десятичных дробей и целых чисел с особыми свойствами. Он открыл несколько замечательных свойств чисел, но при жизни так и не получил признания. Лишь совсем недавно его вклад в теорию чисел был оценен по достоинству: в знак запоздалого признания его именем была названа постоянная.

Постоянная Капрекара

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

Попробуем проделать это с номером года, в котором я начал писать эту книгу, – 2009. Наибольшее число, которое можно образовать из этих четырех цифр, – 9200, а наименьшее – 0029. Вычтем 29 из 9200 и получим 9171.

Повторим эту процедуру: 9711 – 1179 = 8532.

Продолжим: 8532 – 2358 = 6174. Наши поиски завершены: в конце пути нас с самого начала поджидало число 6174.

На математическом языке 6174 называется «неподвижной точкой», что означает следующее: если мы подставим в этот процесс само это число, мы снова вернемся к нему же. Проверим: 7641 – 1467 = 6174. Действительно, дальше дороги нет; путешествие подошло к концу.

А что, если немного схитрить? Получится ли этот же фокус с числом, в котором есть три одинаковые цифры? Скажем, с числом 1112? Давайте попробуем.

2111 – 1112 = 999

Поскольку мы работаем с четырехзначными числами, запишем результат в виде 0999.

9990 – 0999 = 8991

9981 – 1899 = 8082

8820 – 0288 = 8532

8532 – 2358 = 6174

Вот мы и на месте.

Если кому-нибудь из вас остро требуется трудотерапия, можете попробовать проделать это с какими-нибудь другими числами.

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

Попробуем, например, взять число 169.

961 – 169 = 792

Кстати, 169 = 13², а 961 = 31². Но не будем отвлекаться.

972 – 279 = 693

963 – 369 = 594

954 – 459 = 495

Мы пришли к неподвижной точке (проверьте, что это так!). Неужели мы открыли постоянную Капрекара для трехзначных чисел? Именно это мы и сделали! Если вы увлекаетесь алгеброй, вам не составит особого труда доказать это утверждение.

Перейдем к двухзначным числам. С ними-то все должно быть совсем легко, правда?

Начнем с одного из моих любимых чисел – 17.

71 – 17 = 54, 54 – 45 = 9, 90 – 9 = 81, 81 – 18 = 63, 63 – 36 = 27, 72 – 27 = 45, 54 – 45 = … Минуточку! Здесь мы уже были! Что происходит? На самом деле мы пришли к точке периодичности. Для двухзначных чисел неподвижной точки не существует.

Головоломка

А что получается с пятизначными числами? А с шестизначными?

Числа Капрекара

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

Числа 9, 45, 999, 818 181 – и многие другие – относятся к сообществу «чисел Капрекара». Вы можете запустить на своем компьютере простую программу, которая познакомит вас со многими другими представителями этого сообщества.

Головоломка

Докажите, что числа 9, 99, 999 и 9999 – это числа Капрекара.

Древняя индийская задача

Найдите следующее число в последовательности: 1, 2, 4, 8, 16, 23, 28, 38, 49…

Подумайте несколько минут. Если вы не сможете решить эту задачу, ответ можно найти в примечаниях в конце книги{13}13
  Ответ – 62. Каждое число последовательности равно сумме предыдущего числа и суммы цифр предыдущего числа. Например, после 16 идет 23, потому что 16 + (1 + 6) = 16 + 7 = 23. Следовательно, ответ задачи: 49 + 13 = 62.


[Закрыть].

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

Капрекар заметил, что некоторые числа можно получить сложением меньшего числа с суммой его цифр, а для других чисел это оказывается невозможным. Например, число 40 можно получить этим методом, взяв 29 (2 + 9 = 11, 29 + 11 = 40). Но число 20 таким образом получить невозможно, с какого бы числа мы ни начинали (проверьте, так ли это).

Капрекар сформулировал критерий, по которому можно определить, какие числа невозможно получить при помощи этого метода[15]15
  В русской терминологии такие числа (например, число 20) называются самопорожденными, в отличие от порожденных чисел (например, числа 40; число 29 называется его генератором).


[Закрыть]. Я не хочу лишать вас удовольствия самостоятельно воссоздать этот критерий. Дам лишь небольшой совет: найдите первое число, удовлетворяющее этому критерию, и попытайтесь вывести общее правило.

А теперь вернемся к нашему великому герою – Пифагору.

II. Пифагор на пляже

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

Посмотрим на некоторые примеры.

Сумма последовательных нечетных чисел

Каждый, кто помнит хоть что-то из школьного курса, вероятно, может вспомнить и следующий закон: сумма n первых последовательных нечетных чисел, начиная с 1, всегда равна квадрату n.

Проиллюстрируем это утверждение:

1 + 3 = 4 = 2²;

1 + 3 + 5 = 9 = 3²;

1 + 3 + 5 + 7 = 16 = 4²

и так далее.

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

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

1 + 3 + … + (2n – 3) + (2n – 1) = n².

Доказательство состоит из двух частей. В первой части мы доказываем справедливость так называемого индукционного перехода, то есть несколько странного утверждения, которое гласит: «Если это равенство истинно для n, то оно истинно и для n + 1».

Во второй части нужно доказать так называемую базу индукции, то есть убедиться, что это равенство истинно для n = 1.

Вот и всё! Этим мы доказываем справедливость этого утверждения для всех натуральных чисел.

Все это может показаться сомнительным, но позвольте мне объяснить. Представьте себе, что доказательство для n – это костяшка домино. Если вы когда-нибудь выстраивали ряд костяшек домино, вы знаете, что их ставят так, что, когда некая определенная костяшка падает, она толкает соседнюю, та толкает следующую и так далее – пока не упадут все костяшки. В доказательстве по индукции мы точно так же выстраиваем свои «утверждения» в ряд: если мы доказали утверждение для любого элемента n, это «толкает» утверждение для элемента n + 1. Но, как и в случае костяшек домино, чтобы запустить цепную реакцию падения, нужно подтолкнуть первую костяшку – или, если использовать терминологию математической индукции, доказать базу индукции. Итак, мы совершаем индукционный переход – то есть предполагаем, что истинно следующее равенство:

1 + 3 + … + (2n – 3) + (2n – 1) = n².

Теперь докажем, что оно справедливо и для n + 1, рассуждая следующим образом.

Левая часть равенства имеет вид:

1 + 3 + … + (2(n + 1) – 3) + (2(n + 1) – 1) = 1 + 3 + … + (2 n – 1) + (2n + 1).

В правой же части должно быть (n + 1)². Поскольку мы предполагаем, что наше равенство выполняется для n, мы можем утверждать, что:

1 + 3 + … + (2n – 1) + (2n + 1) = n² + (2n + 1) = (n + 1)².

Этим завершается доказательство гипотезы индукции. Осталось только толкнуть первую костяшку. Для базы индукции, то есть при n = 1, утверждение, несомненно, справедливо, так как 1 = 1².

Теперь костяшки доказательства начинают падать одна за другой: утверждение для n = 2 вытекает из утверждения для n = 1, утверждение для n = 3 – из утверждения для n = 2 и так далее.

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

Один шарик и три шарика легко расставить в форме квадрата размером 2 × 2 клетки:

Один шарик, три шарика и еще пять шариков дают правильный квадрат размером 3 × 3:

Если же добавить к ним следующее нечетное число, 7, точно так же получится квадрат размером 4 × 4 клетки:

Великий еврейский философ Барух Спиноза различал три вида знания:

1. Вера.

2. Исследование (экспериментирование).

3. Понимание.

Я объясню, о чем идет речь. Если вы сообщаете мне что-то – например что сумма последовательности нечетных чисел равна полному квадрату, – я могу поверить, что вы знаете, о чем говорите. Это первый уровень знания. Однако вполне может быть, что то, что вы мне рассказали, неверно.

Если я не поленюсь проверить эту информацию – то есть рассмотрю несколько примеров и смогу убедиться, что для них это правило выполняется, – я перейду на второй уровень знания. На нем утверждение несколько более достоверно, потому что я видел, что оно действительно справедливо в некоторых случаях, но считать его абсолютно истинным нельзя. Профессор Бено Арбель (1939–2013) показал мне однажды замечательный пример, в котором многократные проверки не позволяют убедиться в истинности утверждения, даже когда их число необычайно велико. Возьмем выражение 991n² + 1. Существует ли такое значение n, при котором это выражение дает полный квадрат? Можно подставить множество разных значений n, а потом перебрать кучу других значений n, и все время будет казаться, что это выражение никогда не дает полного квадрата. Но это не так, потому что при n = 12 055 735 790 331 359 447 442 238 767 получается именно полный квадрат! Даже если мы проживем миллиард лет и потратим все это время на подстановки и вычисления, вряд ли мы обнаружим это число.

А это подводит нас к третьему уровню: только если понять, почему нечто происходит, – например разложив камни квадратом, – можно исключить всякую возможность ошибки.

Скажи мне – и я забуду. Научи меня – и я запомню. Дай мне сделать – и я пойму.

Китайская мудрость

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

Однажды мне попалась в библиотеке книга русского математика Якова Успенского (1883–1947) под названием «Теория уравнений» (Theory of Equations, 1948). Он работал в Стэнфордском университете под именем Джеймс Успенский. Успенский доказал множество разнообразных формул тем же путем, каким доказывал Пифагор, – то есть при помощи иллюстраций.

Начну с весьма простого примера.

Если сложить все числа от 1 до n, результат будет равен

Следующий чертеж объясняет, почему эта формула действует для случая n = 4.

Сумма чисел от 1 до 4 равна половине площади прямоугольника; другими словами, ½ × 4 × 5 = 10.

Ну хорошо, для n = 4 все просто. А что происходит с более крупными числами?

Существует хитрый способ вычисления суммы последовательных чисел от 1 до, скажем, 100. Этот способ тесно связан с историей, главный герой которой – маленький мальчик. Разные страны и народы спорят о том, кто именно был этим мальчиком. Русские утверждают, что это был математик Николай Лобачевский, «Коперник геометрии», и было ему тогда семь лет. Евреи говорят, что это был Барух Спиноза, но возраст называют такой же. Немцы называют героем этого повествования выдающегося математика – на самом деле одного из величайших во всей истории математики – К. Ф. Гаусса (в честь которого, что неудивительно, названа колоколообразная кривая – гауссиана) в шестилетнем возрасте. Немало и таких родителей, которые утверждают, что это произошло с их собственным ребенком.

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

Так вот, однажды маленький Барух сидел на уроке и очень, очень скучал. Но беда была не только в том, что ему было скучно, а еще и в том, что из-за этого он шалил и мешал учителю вести урок. Учитель решил дать мальчику какую-нибудь задачу, которая займет его на долгое время, и велел Баруху сложить все числа от 1 до 100. «Этого ему хватит по меньшей мере до конца урока», – решил учитель.

Но его ожиданиям не суждено было сбыться. Не успел учитель повернуться к доске, как Барух сказал: «Учитель, ответ – 5050».

Мы можем предположить, что Барух еще не был знаком с приведенной выше формулой (он был слишком мал). Как же ему удалось так быстро сосчитать эту сумму?

1 + 2 + 3 + 4 + … + 98 + 99 + 100 =?

Ответ оказывается очень простым и к тому же очень изящным. Барух не стал складывать все числа по порядку: он заметил, что можно сложить первое число с последним (1 + 100 = 101), второе – с предпоследним (2 + 99 = 101), третье – с третьим с конца (3 + 98 = 101) и так далее, вплоть до 50 + 51 = 101, и получить пятьдесят пар, сумма членов каждой из которых равна 101. После этого ему оставалось только умножить 50 на 101, а это очень легко сделать: 50 × 100 = 5000 плюс еще один раз 50, итого 5050.

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

Привычка Пифагора преподавать с использованием камешков также объясняет, почему мы называем некоторые числа «квадратными», «треугольными», «кубическими» и так далее. Он просто давал этим числам названия, соответствующие их геометрическим представлениям.

Например, как можно видеть из иллюстрации, числа 1, 4, 9, 16, 25… – «квадратные»:

Числа 1, 3, 6, 10, 15… – «треугольные»:

А числа 1, 5, 12… – пятиугольные.

Вернемся к треугольным числам.

Теория: любое треугольное число от 3 и выше может быть выражено в виде суммы полного квадрата и двух треугольных чисел.

Доказательство: хватит и иллюстрации.

И действительно, 15 = 9 + 3 + 3 = 3² + 3 + 3.

Ч. т. д.

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

А как обстоит дело с суммой квадратов последовательных чисел?

1² + 2² + 3² + 4² + 5² + … =?

Те, кто по-настоящему любил в школе задачи на индукцию, возможно, даже помнят следующую формулу (символ · обозначает в ней операцию умножения):

Это равенство было известно уже китайскому математику Ян Хуэю, жившему в XIII в.

Какая логика лежит в его основе? Чтобы понять ее, нам придется обратиться за помощью к пифагорейцам. Я продемонстрирую концепцию для n = 4. Концепция для общего случая следует в точности тому же принципу.

Теперь осталось только собрать следующую фигуру:

и мы получим:

или

.

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

Без математики невозможно проникнуть вглубь философии. Без философии невозможно проникнуть вглубь математики. Без них обеих невозможно проникнуть вглубь чего бы то ни было.

Лейбниц

Теорема Пифагора

Можно ли говорить о Пифагоре и не упомянуть о прославленной теореме, носящей его имя? Разумеется, нельзя. Поэтому я закончу эту главу несколькими историями о теореме Пифагора.

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

Интересно отметить, что эту теорему знали еще древние египтяне, которые даже использовали пифагоровы треугольники со сторонами 3 – 4 – 5 для построения прямых углов.

Разумеется, всякий, кто учился в школе, способен дать формулировку этой знаменитой теоремы, но многие ли из вас действительно знают почему она справедлива и как ее доказать?

Рассказывают, что, когда философ Томас Гоббс (1588–1679) случайно увидел теорему Пифагора в книге «отца геометрии» Евклида, он был так поражен, что решительно отказался поверить, что это утверждение может быть истинным. В то время Гоббсу было около 40, и до этого момента он не особенно интересовался математикой. Гоббс прочитал доказательство (что совсем не мало для человека, не отличавшегося страстью к геометрическим фигурам) и влюбился в геометрию.

Что же – если Гоббс не желал поверить в истинность теоремы, мне не остается ничего другого, как доказать ее. Собственно говоря, ее доказательств существуют сотни, начиная с самого первого, так поразившего Гоббса в изложении Евклида, и до доказательств с использованием дифференциалов.

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

Доказательство № 1 – изящество простоты

Это доказательство я выбрал потому, что оно – одно из самых простых.

Возьмем квадрат со стороной a + b и построим в нем четыре одинаковых прямоугольных треугольника, как показано в левой части представленного ниже чертежа. Теперь расположим те же треугольники по-другому, как показано в правой части. Площадь заштрихованных участков на обоих чертежах должна быть одинаковой, так как она в обоих случаях равна суммарной площади квадрата за вычетом площади четырех треугольников.

Следовательно, a² + b² = c².

Доказательство № 2 – доказательство Гарфилда

Если вы думаете, что автором доказательства теоремы Пифагора был ленивый кот Гарфилд[16]16
  Герой одноименного комикса.


[Закрыть], вы ошибаетесь. Это доказательство принадлежит двадцатому президенту Соединенных Штатов Джеймсу А. Гарфилду. Однако, если вы думаете, что между котом Гарфилдом и президентом Гарфилдом нет никакой связи, вы опять ошибаетесь! Создатель кота Гарфилда художник Джим Дэвис назвал его в честь своего дедушки, а дедушку назвали в честь президента Гарфилда.

Вот это доказательство. Посмотрите на трапецию, изображенную на следующем чертеже:

Площадь трапеции равна произведению ее высоты (a + b) на среднее арифметическое длин ее оснований

Вместе с тем трапеция состоит из трех треугольников – I, II и III, – а площадь каждого из треугольников I и II равна

Исходя из того, что сумма углов треугольника равна 180°, легко доказать, что треугольник III прямоугольный. Отсюда вытекает, что площадь треугольника III равна

Следовательно,

Раскрыв скобки в левой части и упростив, получаем в результате a² + b² = c².

Ч. т. д.

Браво, двадцатый президент Соединенных Штатов!

Доказательство № 3 – Пифагор и Леонардо

На этот раз автором доказательства был не кто иной, как Леонардо да Винчи. Джорджо Вазари (1511–1574) пишет в «Жизнеописаниях наиболее знаменитых живописцев, ваятелей и зодчих» (1550), книге о великих художниках, что Леонардо изучал математику всего несколько месяцев, но и за такое короткое время сумел стать специалистом в этой области. Точно так же Леонардо не посвящал много времени изучению музыки, и тем не менее подобно Пифагору любил петь, аккомпанируя себе на лютне. Есть много других предметов, которыми Леонардо занимался лишь недолгое время и тем не менее освоил настолько, что научился применять их даже лучше, чем те, кто затратил на их изучение много времени и сил.

Уверен, что никто не удивится, если я скажу, что основную идею доказательства да Винчи легко можно понять из чертежа.

Как Леонардо да Винчи пришел к этому чертежу? Где именно таится в нем доказательство? Я дам вам время немного поупражнять мозг, размышляя над этой задачей.

3
Тайная жизнь простых чисел

«Эврика» Евклида

В предыдущей главе, в которой мы познакомились с Пифагором, нам встретились треугольные числа, квадратные числа и даже пятиугольные числа. Однако мы совсем не говорили о числах прямоугольных. Почему же?

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

Гораздо интереснее искать числа, которые нельзя представить в виде прямоугольника; точнее говоря, числа, которые делятся только на единицу и само на себя. Например, число 17.

Не существует никакого способа составить из клеток прямоугольник, отличающийся от показанного ниже.

Число называется простым, если у него есть ровно два разных делителя – единица и само это число. Числа, не являющиеся простыми, называют составными. Вот несколько первых простых чисел: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47… Их список продолжается и дальше. Если вы внимательно прочитаете определение простого числа, вы поймете, почему в этот список не входит число 1.

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

Например: 72 = 2 × 2 × 2 × 3 × 3 = 2³ × 3².

Тем, кто не считает себя членом сообщества математиков, тот факт, что любое число может быть представлено в виде одного, и только одного, произведения простых сомножителей, кажется совершенно очевидным. Однако для математиков этот факт не вполне ясен: им приходится его доказывать. Не следует, однако, обвинять математиков в излишней педантичности; в прошлом было такое множество положений, которые казались «совершенно очевидными», а потом оказались – и это было доказано – ложными, что математики категорически решили, что любое и каждое утверждение должно быть подтверждено доказательством. Можно предположить, что сложение множества нулей непременно дает нуль, но, как вы увидите далее в этой книге, сумма нулей не всегда бывает равна нулю, а если уж нельзя доверять нулям, то кому вообще можно доверять?

Но я отвлекся. Вернемся к теме простых чисел.

Первое, что мы можем спросить, завязывая с простыми числами отношения, которые мы собираемся заботливо развивать, это: «Сколько всего существует простых чисел?»

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

Евклидова геометрия оказала сильнейшее влияние на лучшие умы человеческой цивилизации, одним из которых был величайший из философов, Барух Спиноза. Евклидовы методы построения геометрии на основе аксиом и базовых концепций настолько впечатлили Спинозу, что он применил этот подход в главной своей работе, «Этике». Разумеется, Спиноза не говорит в своей книге о точках и прямых. Он рассуждает о концепции Бога и о месте человека в мироздании. Но для представления своих доводов он использует чисто евклидовские методы: Спиноза излагает основополагающие концепции, формулирует конкретные аксиомы, а затем использует их для доказательства теорем. Более того, главное произведение Спинозы называется в латинском оригинале Ethica ordine geometrico demonstrata (хотя эту книгу часто называют просто «Этикой»; точный перевод латинского названия – «Этика, доказанная в геометрическом порядке»).

Но вернемся к Евклиду. Прежде чем мы посмотрим его ответ на вопрос «сколько существует простых чисел?», давайте немного подумаем самостоятельно.

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

Если их количество конечно, то каково самое большое простое число?

Если же простых чисел бесконечно много, можно ли это доказать?

Можно ли представить себе, что некое действительно огромное, необычайно большое число не делится нацело ни на что, кроме единицы и самого себя, и, следовательно, считается простым числом?

Существует ли формула, которую можно использовать для получения всех простых чисел?

ТЕОРЕМА ЕВКЛИДА

Существует бесконечно много простых чисел.

Я приведу два доказательства этой теоремы. Одно из них кратко и подчеркивает красоту великой идеи Евклида. Второе доказательство, по сути, сводится к тому же, но оно длиннее и помогает подробно объяснить более краткое доказательство.

Короткое доказательство

Предположим, что ряд 2, 3, 5, 7, 11, …, P – это полный список простых чисел вплоть до некоторого простого числа P.

Образуем новое число S, такое, что S = (2 × 3 × 5 × 7 × 11 × … × P) + 1.

Число либо S является простым, либо делится на одно или несколько из простых чисел, больших, чем P. В любом из этих случаев число P не может быть самым большим простым числом. Следовательно, количество простых чисел должно быть бесконечным.

Ч. т. д.

Убедило ли вас это доказательство? Если да, вы можете пропустить следующее; если нет, – читайте дальше!

Длинное доказательство

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

Если количество простых чисел конечно, то должна существовать возможность найти самое большое простое число, которое мы обозначим P. Выпишем все простые числа: 2, 3, 5, 7, 11, 13, 17, …, P.

Теперь образуем еще одно число: S = (2 × 3 × 5 × × 7 × 11 × 13 × 17 ×… × P) + 1. Другими словами, число S равно произведению всех простых чисел из нашего списка плюс 1.

На что же делится число S?

Оно не может делиться на два, так как выражение в скобках равно четному числу (поскольку 2 – один из сомножителей этого выражения). Прибавление единицы делает S нечетным числом.

Кроме того, S не может делиться на 3. Это можно утверждать по такой же причине: число, стоящее в скобках, делится на 3 (потому что 3 – один из сомножителей этого выражения); следовательно, при прибавлении единицы получается число, не делящееся на 3 (собственно говоря, при делении S на любое простое число из списка получается остаток, равный 1).

Число S также не может делиться на 4, поскольку оно не делится на 2. Вообще, любое число, делящееся на некий делитель, также делится и на его простые сомножители. Например, любое число, делящееся на 6, делится также на 2 и на 3.

Продолжая в том же духе, мы поймем, немного поразмыслив, что число S не может делиться ни на 5, ни на 6, ни на 7, ни на какое бы то ни было другое число до числа P включительно, которое, как мы предполагаем, является самым большим простым числом. Это оставляет нам две возможности:

1. Либо S – простое число, большее P.

2. Либо S делится на некое простое число, не входящее в наш список, то есть на простое число, большее P (поскольку мы уже видели, что оно не делится ни на одно из простых чисел, меньших или равных P).

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

Ч. т. д.

Кстати, если вам интересно, используемое во многих языках вместо «ч. т. д.» сокращение QED происходит от латинских слов Quod Erat Demonstrandum, то есть «что и нужно было продемонстрировать»: каждый математик гордо выписывает это радостное обозначение в конце своего рассуждения, когда ему наконец удается довести до завершения какое-нибудь длинное и сложное доказательство.

Спиноза часто использовал это латинское сокращение. Интересно отметить, что сам Евклид применял греческое сокращение OEΔ, внешне похожее на латинское и означающее ὅπԑρ ἔδει δεῖξαι – «что и нужно было показать».

Важное примечание: доказательство Евклида не особенно конструктивно. Иначе говоря, оно не дает простого рецепта получения новых простых чисел. Число S, как мы уже указывали, вполне может не быть простым числом: оно также может быть числом составным, делящимся на простое число, большее P.

Вот иллюстрация этого утверждения.

Предположим, что число 3 – самое большое из существующих простых чисел (разумеется, это предположение абсолютно ложно). Образуем число S, равное (2 × 3) + 1 = 7, и 7 действительно оказывается простым числом. То же верно и для S = (2 × 3 × 5) + 1, для S = (2 × 3 × 5 × 7) + 1 и для S = (2 × 3 × 5 × 7 × 11) + 1.

Но после этого мы получаем пример осуществления второго варианта:

(2 × 3 × 5 × 7 × 11 × 13) + 1 = 30 031 = 59 × 509.

Другими словами, (2 × 3 × 5 × 7 × 11 × 13) + 1 есть составное число, делящееся на простые числа 59 и 509, которые оба больше числа 13, которое временно выступало в роли «самого большого простого числа». Видим, что никакого противоречия в доказательстве Евклида нет – оно безупречно.

Интересно отметить, что довольно многим впервые столкнувшимся с доказательством Евклида кажется, что, если бы им его не показали, они вполне смогли бы открыть его самостоятельно. «Подумаешь, перемножить простые числа и прибавить единицу. Что тут сложного? Я бы и сам до этого додумался за пару минут, не больше!» В большинстве случаев это иллюзия. Простота этого доказательства лишь подчеркивает его красоту и гениальность.