Рафаель Роузен - Математика для гиков

8 = 2 × 2 × 2

9 = 3 × 3

10 = 2 × 5

11 – простое число.

12 = 2 × 2 × 3

13 – простое число.

И так далее.

Сколько простых чисел существует? Евклид доказал, что на самом деле их бесконечное количество. Неважно, как далеко мы находимся на числовой прямой, мы никогда не доберемся до последнего простого числа. Их всегда будет больше.

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

1. Во-первых, помните, что каждое число – это простое число или же получено путем перемножения ряда простых чисел.

2. Во-вторых, мы будем использовать особый вид способа доказательств под названием reduction ad absurdum (доведение до абсурда): мы попробуем доказать противоположное тому, что мы пытаемся доказать. Если мы докажем, что это противоположное не может быть правдой, тогда мы будем знать, что противоположное ему утверждение – то, что мы изначально хотели доказать, – будет истиной.

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

Шаг первый: давайте изобретем число и назовем его «Джордж». Скажем, что мы можем получить Джорджа, если перемножим все простые числа, от первого до последнего, а потом прибавим к результату 1. (Не забывайте, что мы предполагаем, что существует ограниченное количество простых чисел.) Мы знаем, что Джордж должен быть простым числом или должен быть получен в результате умножения простых чисел. Мы сразу же можем увидеть, что если Джордж является простым числом, то мы доказали, что есть простое число – Джордж! – которое не входило в наш изначальный список. Теперь мы можем остановиться и похлопать себя по спине, так как наш результат будет актуален для любого количества простых чисел.

Но давайте представим другой вариант: скажем, что Джордж не является простым числом. Это значит, что его можно получить путем умножения двух или более простых чисел. Но ни одно простое число из нашего списка не подойдет, так как если мы будем использовать их в наших вычислениях, у нас всегда будет оставаться остаток 1. Следовательно, должны существовать другие простые числа, не из нашего списка, которые путем перемножения дадут нам Джорджа. Опять же мы доказали, что для любого ряда простых чисел всегда будут существовать простые числа, не входящие в него.

Это один из примеров силы и красоты математического умозаключения.

Некоторые простые числа экзотичнее других. Числа Ферма, например, имеют вид 2 2n+ 1 и являются простыми. Однако единственными известными числами Ферма являются те, где n = 0, 1, 2, 3 и 4 и равны 3, 5, 17, 257 и 65537 соответственно.

Забудьте об электронной почте и социальных сетях. Тогда наиболее глубокое влияние Интернета на мир могут оказывать интернет-магазины. Но онлайн-коммерция таит в себе опасности. Когда вы вбиваете номер своей кредитной карты на такие сайты, как Amazon, и кликаете «Купить», что останавливает киберворов от перехвата этой информации и кражи номера?

Обратимся к математике. Безопасность работы в Интернете и криптография с открытым ключом в целом основаны на простых числах, особом виде чисел, которые делятся только на себя и на 1. (Для сравнения: число 10 делится на себя, 1, 2 и 5 и простым не является.) Примерами простых чисел являются 1, 3, 5, 7 и 11, но их существует бесконечное множество и соответственно могут расти на огромные расстояния. Существует математическое доказательство того, почему простых чисел бесконечное множество, но это уже другая история (см. главу 4.2).

Когда вы вбиваете номер своей кредитной карты онлайн, вы пользуетесь так называемым алгоритмом RSA. Он был назван в честь создателей – Рональда Ривеста (Rivest), Ади Шамира (Shamir) и Леонарда Адлемана (Adleman). Алгоритм был создан в 1977 году и является системой шифрования, которая основывается на огромных простых числах. В сущности, система обеспечивает безопасность ваших личных данных путем преобразования номера вашей кредитки в другой, чрезвычайно длинный номер, который получен в результате умножения двух длинных случайных простых чисел. Вы могли бы превратить этот новый номер обратно в номер своей карточки, если бы знали два простых числа, но безопасность ваших данных обеспечивается еще одним математическим фактом: крайне тяжело разложить большое число на простые числа. На самом деле, для очень длинного числа могут понадобиться сотни и тысячи лет для того, чтобы сеть суперкомпьютеров смогла найти два правильных простых числа.