Better Explained: непростой взгляд на простые числа

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

Вот два неоспоримых доказательства крутости простых чисел:

• Простые числа — это строительный материал для всех остальных чисел. В химии знание химического состава вещества помогает спрогнозировать его свойства. С числами всё происходит точно так же!
• У простых чисел есть особые свойства, например, трудность их определения. Да, порой такая черта может быть оказаться весьма положительной — в таких сферах, как криптография.

Так что такое простые числа?

Основная теорема арифметики гласит, что любое число можно записать в виде произведения простых чисел. Например:

Простые числа — это неделимые далее числа. Например, 3, 5, 7 или 23. И число 2 — тоже простое число.

А что насчёт единицы?

1 — особенное число, которое не принято считать простым, хотя бы чтобы избежать шизофрении вида 1 = 1 * 1 * 1 * 1 и так далее..

Джексон Поллок «Номер 1», 1950 г., образец абстрактного импрессионизма

Источник: flickr

Представление натурального числа в виде произведения простых называется факторизацией, или разложением на простые. Разложение на простые кажется простым. На самом деле не всё здесь так уж просто. Оказывается, что:

• Ряд простых чисел бесконечен;
• Не существует алгоритма составления ряда простых чисел;
• Простые числа играют решающую роль в самых неожиданных матчах, например, в квантовой механике;
• Разложение на простые — это сложно. Пока что метод перебора является лучшим способом факторизации. А это очень медленно.

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

Аналогия: простые числа и химические формулы

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

H₂O = два атома водорода и один атом кислорода

Так и в математике мы записываем число с помощью простых чисел:

12 = 2 * 2 * 3 = 2² * 3 = две двойки и одна тройка

Разница только в том, что в химической формуле «степень» пишется снизу, а не сверху. Я писал Американской ассоциации химиков, чтобы они внесли необходимые изменения в свою систему обозначений, но они мне до сих пор не ответил.

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

Периодическая система элементов Д. И. Менделеева 1871 г.

Источник: science-techno.ru

Давайте посмотрим, как там было дело с периодической таблицей у химиков:

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

Вот бы нам такую таблицу для простых чисел!

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

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

Органическая химия и функциональные группы

Да, мы сейчас будем искать сходства между химическими формулами и простыми числами.

Источник: flickr

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

Некоторые свойства химических элементов зависят от их положения в периодической таблице химических элементов:

• Атомы в группе VIIIA — благородные газы. Они обладают очень низкой химической реактивностью и вряд ли когда-нибудь взорвутся перед вашим лицом.
• Атомы в группе IVA (подгруппа углерода) отличаются хорошим уровнем химической активности. Они — прекрасный строительный материал для других элементов.
• Атомы в группе I (подгруппа щелочных металлов) исключительно реактивны. Хотите взрыв? Опустите их в воду.

В органической химии есть понятие функциональной группы — когда несколько атомов определяют класс целой молекулы. К примеру:

• Спирты — это углеродно-водородная цепочка с группой OH в конце.
• Метанол, этанол и другие спирты обладают сходными свойствами как раз по причине наличия функциональной группы OH.

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

Пример первый: угадываем чётность

Органическое вещество, как правило, содержит углерод (это не всегда так, но нужно же с чего-то начать). Какие бы элементы вы ни смешивали, без углерода органическое вещество вы не получите.

Чётность работает примерно так же. Число является чётным, если при его разложении на простые мы имеем хотя бы одну двойку. Есть двойка в качестве множителя — число чётное; нет — нечётное.

А теперь давайте вспомним несколько математических задачек о произведении чётных и нечётных чисел.

• Что будет, если нечётное число умножить на чётное? (чётное или нечётное?)
• Что будет, если чётное число умножить на чётное? (чётное или нечётное?)
• Что будет, если нечётное умножить на нечётное? (чётное или нечётное?)

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

• Произведение нечётного и чётного чисел даёт чётное число.
• Произведение чётного и чётного чисел даёт чётное число.
• Произведение нечётного и нечётного чисел даёт нечётное число.

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

Ещё пример: заканчиваем нулём

Конечно, пора привести пример с функциональной группой.

Предположим, что у нас есть функциональная группа 2 * 5 — то есть в нашей «формуле числа» будет как минимум одна двойка и как минимум одна пятёрка:

Заметили модель поведения? Если у числа есть функциональная группа 2 * 5, число кратно десяти.

Почему? Ну что ж:

Нам достаточно взглянуть на формулу и предсказать свойство числа.

И ещё один пример: сумма цифр

По заявкам радиослушателей ещё одна иллюстрация функциональных групп в числах.

Представим функциональную группу 3 * 3. Если у числа есть эта функциональная группа, оно обладает следующими свойствами:

• Оно делится на 9
• Сумма его цифр делится на 9 (просто поверьте мне на слово)

Привожу пример:

• 18 = 2 * 3 * 3. Функциональная группа есть. Сумма его цифр 1 + 8 = 9, что делится на 9 без остатка.
• 279 = 31 * 3 * 3. Сумма его цифр 2 + 7 + 9 = 18, что делится на 9 без остатка.

Простые числа в реальном мире

У простых чисел есть поистине полезные свойства.

1. Большие числа сложно разложить на простые. Выше я уже говорили, что мы до сих пор действуем методом перебора, когда совершаем факторизацию числа. Этот факт применяется в криптографии.
2. Простые числа не пересекаются с обычными. Что я имею в виду? Например, 4 и 6 в итоге пересекутся уже на 12, а не на 24. 5 и 7 пересекутся только на 35. Для природы такая особенность может стать значительным преимуществом. Есть такие удивительные насекомые — семнадцатилетние цикады. Они находятся в коконе 17 лет, и только потом вылупляется. Это позволяет им значительно вырастить популяцию, поскольку их жизненный цикл не пересекается с жизненным циклом хищников, который обычно составляет 2-4 года.
3. Простые числа и в Африке простые. Последовательность простых чисел сложно сгенерировать случайным образом. Последовательность 1, 0, 1, 0 может быть произведена маятником. Ряд 2, 3, 5, 7, 11, 13 выстроится случайно с очень малой вероятностью. Более того, простые числа являются простыми в любой системе счисления. Везде найдутся числа, которые невозможно разделить на другие числа. В единичной системе счисления:

II
III
IIIII
IIIIIII

В заключение

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