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] – это то, что в ней проще производить вычисления. Но давайте задумаемся о том, сколько сил уходит на перемножение двух чисел. Во-первых, нам необходимо запоминать дополнительные математические данные. К тому же мы обязаны помнить таблицу умножения. Во-вторых, мы проделываем многоуровневую процедуру: сортируем числа по разрядам, умножаем по соответствующему правилу, получаем промежуточные данные, складываем.

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

Единичная