Рис. 1.17
В Древнем Китае даже было понятие отрицательного числа, оно представлялось счетными палочками другого цвета. Полагают, что использование черных и красных чернил в европейском бухгалтерском учете восходит к китайской практике использования черных и красных палочек. Любопытно, впрочем, что китайцы пользовались черными палочками для обозначения отрицательных чисел.
По-видимому, впервые простые числа получили свою важную роль именно в китайской культуре. В ней полагалось, что у каждого числа был свой род – у четных чисел женский, а у нечетных мужской. У некоторых нечетных чисел были замечены особенности. Например, если у вас 15 камней, то их можно выложить в аккуратный прямоугольник 3 на 5. Но 17 камней нельзя представить прямоугольником, а лишь выложить в прямую линию. Поэтому для китайцев простые числа были настоящими мачо. А у нечетных чисел, которые не были простыми, был ощутимый налет женственности.
Точка зрения древних китайцев была обусловлена тем важным свойством простых чисел, что кучку из простого числа камней нельзя разложить в аккуратный прямоугольник.
Ранее мы видели, что египтяне рисовали жаб для представления чисел, майя использовали точки и черточки, вавилоняне занимались клинописью, китайцы располагали палочки, а в еврейской культуре числа находились в соответствии с буквами алфавита. Хотя особую роль простых чисел поняли китайцы, первые шаги по раскрытию тайн этих загадочных чисел были сделаны в другой культуре – в древнегреческой.
Как древние греки использовали решето для приготовления простых чисел?
Древние греки открыли следующую систематическую процедуру, весьма эффективную для нахождения небольших простых чисел. Задача состоит в том, чтобы найти действенный метод по отбрасыванию всех чисел, не являющихся простыми. Запишем числа от 1 до 100. Начнем с вычеркивания числа 1. (Как я упоминал, хотя греки считали 1 простым числом, современная математика так не поступает.) Перейдем к следующему числу, к 2. Это первое простое число. Затем зачеркнем каждое второе число после 2. Это, по существу, устраняет все числа, кратные 2, то есть все четные числа за исключением 2. Математики любят шутить, что 2 – странное простое число, потому что лишь оно четное… Но, возможно, юмор – не самая сильная сторона математиков.
Рис. 1.18. Зачеркните каждое второе число после 2
Теперь перейдем к минимальному незачеркнутому числу, в нашем случае к 3, и систематически отбросим все остальные числа, кратные 3:
Рис. 1.19. Теперь зачеркните каждое третье число после 3
Поскольку 4 уже было отброшено, далее мы переходим к 5 и зачеркиваем каждое пятое число после 5. Мы повторяем далее эту процедуру и переходим к минимальному числу n, которое еще не было устранено, и вычеркиваем все числа, расположенные через n после него:
Рис. 1.20. Наконец у вас останутся все простые числа из интервала от 1 до 100
Эта процедура прекрасна тем, что она совершенно механическая и не требует размышлений. К примеру, простое ли число 91? Если вы используете данный метод, то не нужно думать. 91 будет зачеркнуто, когда вы отбрасываете числа, кратные 7, ведь 91 = 7 × 13. На числе 91 зачастую происходит ошибка, потому что мы не стремимся учить таблицу умножения 7 до 13.
Эта систематическая процедура служит хорошим примером алгоритма, метода решения задачи путем выполнения заданного набора инструкций – так, по существу, устроена компьютерная программа. Именно этот алгоритм был открыт две тысячи лет назад в одном из центров математической мысли своего времени – в Александрии, которая располагается на территории современного Египта. Тогда Александрия была форпостом великой Греческой империи и славилась одной из лучших библиотек мира. В III в. до н. э. библиотекарь Эратосфен и придумал эту раннюю компьютерную программу для нахождения простых чисел.
Она называется решетом Эратосфена, потому что всякий раз, когда вы просеиваете группу составных чисел, вы как бы используете решето, у которого расстояние между прутьями равно достигнутому вами простому числу. Сначала расстояние между прутьями равно 2, затем 3, потом 5 и т. д. Единственный недостаток этого метода: он быстро становится неэффективным, если вы ищете все бо́льшие и бо́льшие простые числа.
Эратосфен не только отсеивал простые числа и приглядывал за сотнями тысяч папирусных и пергаментных свитков в библиотеке, но и вычислил радиус Земли, а также расстояние от Земли до Солнца и Луны. По его расчету, Солнце находилось в 804 000 000 стадиев от Земли – хотя непонятно, каким именно стадием он пользовался, что делает трудной оценку точности его вычислений. Какой стадион подразумевали бы мы: «Уэмбли» или что-то поменьше, вроде «Лофтус Роуд»?
Кроме расчетов Солнечной системы, Эратосфен нанес Нил на карту и дал первое правильное объяснение его разливов: они были обусловлены сильными дождями в его удаленных верховьях в Эфиопии. Он даже создавал поэтические произведения. Но, несмотря на всю его активность, друзья дали ему прозвище Бета, потому что он ни в чем не преуспел по-настоящему. Говорили, что он уморил себя голодом после того, как ослеп в старческом возрасте.
Вы можете использовать какую-либо настольную игру с числовыми полями для приведения решета Эратосфена в действие. Возьмите спагетти и кладите их кусочки на исключаемые поля. Оставшиеся числа и будут простыми.
Много ли понадобится времени, чтобы написать список всех простых чисел?
Любому, кто захочет написать список всех простых чисел, придется писать его вечно, потому что их количество бесконечно. Почему же мы уверены, что никогда не дойдем до последнего простого числа, что за ним в списке будет следующее? Одно из величайших достижений человеческого разума состоит как раз в том, что с помощью небольшой последовательности логических шагов мы можем осознать бесконечность.
Первым, кто доказал нескончаемость простых чисел, был греческий математик Евклид, живший в Александрии. Он был учеником Платона, и время его деятельности также пришлось на III в. до н. э., хотя, по-видимому, он был на 50 лет старше библиотекаря Эратосфена.
Для того чтобы доказать бесконечность количества простых чисел, Евклид задался вопросом: может ли, напротив, множество простых чисел быть конечным? Конечный список простых чисел означал бы, что любое другое число может быть получено перемножением элементов этого конечного списка. Предположим, к примеру, что список простых чисел включает лишь три числа: 2, 3 и 5. Может ли любое число быть получено путем перемножения различных комбинаций 2, 3 и 5? Евклид придумал способ построения числа, которое не может быть получено таким путем. Он начал с перемножения списка простых чисел, что приводит к 30. Затем – и в этом была гениальная догадка – он добавил 1 к этому числу и получил 31. Ни одно из списка простых чисел, ни 2, ни 3, ни 5, не является его делителем. Всегда получается остаток 1.
