[Перевод] 5 самых старых нерешенных задач Математики о простых числах13.06.2021 08:31

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

Наши размышления о закономерностях в простых числах привели к некоторым сложнейшим проблемам, нерешенным даже величайшими математическими гениями. Сегодня мы рассмотрим 5 старейших математических задач о простых числах, которые интуитивно понятны старшекласснику, но все еще не доказаны даже после упорных попыток в течение 500–2000 лет.

1. Совершенные числа: существуют ли нечетные совершенные числа? Бесконечны ли четные совершенные числа?

Рассмотрим числа 6, 28, 496, 8128…

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

Двигаемся дальше…

Если посмотреть на собственные делители этих чисел, то нетрудно заметить то самое «красивое» свойство:

496 = 1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248

8128 = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 127 + 254 + 508 + 1016 + 2032 + 4064

Числа, для которых сумма собственных делителей равна самому числу, называются совершенными числами. Самое раннее исследование совершенных чисел затеряно в истории. Однако, мы знаем, что пифагорейцы (525 год до н. э.) изучали идеальные числа.

Что мы знаем о таких числах?

Евклид доказал, что для данного n, если — простое число, то $x = 2^{n - 1} (2^n - 1)$ — совершенное число. В качестве упражнения попробуйте доказать это самостоятельно.

Окей, краткий экскурс.

Простые числа Мерсенна: простые числа вида x = 2^n - 1 для некоторого n. Мерсенн предположил, что все числа вида 2^n - 1 простые, когда n простое. (Мы знаем, что это неправда. Например, $2^{11} - 1 = 2047 = 23 * 89$ ).

Открытый вопрос: существует ли бесконечно много простых чисел Мерсенна? На данный момент нам известно 47 простых чисел Мерсенна.

В 18 веке Эйлер показал обратное: любое четное совершенное число имеет вид $2^{n-1} (2^n - 1).$ Другими словами, существует взаимно однозначное соответствие между четными совершенными числами и простыми числами Мерсенна.

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

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

Евклид (ок. 300 г. до. н. э.) первым доказал то, что простых чисел бесконечно много.

2. Гипотеза о близнецах: простых чисел-близнецов бесконечно много

Простые числа-близнецы — это пара вида (p, p + 2), где p и p + 2 являются простыми числами.

Точное происхождение гипотезы о простых числах-близнецах не установлено. Первая формулировка гипотезы о простых числах-близнецах была дана в 1846 году французским математиком Альфонсом де Полиньяком. Однако греческий математик Евклид дал старейшее из известных доказательств существования бесконечного числа простых чисел. Но он не предполагал, что существует бесконечное число простых чисел-близнецов.

На протяжении 2000 лет в доказательстве этого утверждения практически не было прогресса.

Что мы знаем!

Существует бесконечно много простых пар вида (p, p + k), где k <= 246.
Если допустить истинность гипотезы Эллиота — Халберстама (которая, по нашему мнению, верна), то существует бесконечно много простых пар вида (p, p + k), где k <= 6. Это означает, что множество пар простых чисел, отличающихся на 2 (twin-primes), на 4 (cousin-primes) и на 6 (sexy-primes) бесконечно.

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

3. Какие правильные n-угольники построимы?

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

Древние греки знали, как построить правильный многоугольник с 3,4 и 5 сторонами. Также они умели строить правильные многоугольники с удвоенным числом сторон для данного правильного многоугольника.

Таким образом, они могли построить правильный n-угольник для n = {3, 6, 12, 24… 4, 8, 16… 5, 10, 20…} и так далее.

Естественно задать вопрос, для каких значений n можно построить правильный многоугольник. Первый реальный результат в решении этой проблемы был получен спустя 2000 лет после того, как древние греки впервые начали её изучать. В 1796 году 19-летний подросток построил правильный 17-угольник. Этим ребенком был не кто иной, как Карл Фридрих Гаусс. Несколько лет спустя Гаусс дал ответ на общую проблему.

Что мы знаем!

Гаусс показал, что правильный n-угольник может быть построен с помощью циркуля и линейки тогда и только тогда, когда n является произведением степени двойки и любого количества различных простых чисел Ферма (включая ни одного).

Простое число Ферма — это простое число вида:

$2^{2^n} + 1$

Таким образом, проблема поиска всех построимых многоугольников сводится к нахождению всех простых чисел Ферма. Это отдельная нерешенная проблема. Несколько первых чисел Ферма: 3, 5, 17, 257, 65537, 4294967297…

По состоянию на 2021 год единственными известными простыми числами Ферма являются F0=3, F1=5, F2=17, F3=257, F4=65537.

Ферма предположил, что все числа Ферма являются простыми. В 1732 году Эйлер открыл, что F5 делится на 641. С тех пор мы выяснили, что для n = 5, 6…31 числа Ферма составные. Простое число Ферма после F4 неизвестно.

Мы найдем ответ на вопрос о построимых правильных n-угольниках в тот же момент, как только найдем ответ на вопрос о существовании простых чисел Ферма.

4. Гипотеза Гольдбаха (1742)

Сильная гипотеза Гольдбаха:

Каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел.

Слабая гипотеза Гольдбаха:

Каждое нечётное число, большее 5, можно представить в виде суммы трёх простых чисел.

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

(Примечание — В 2013 году Харальд Хельфготт опубликовал доказательство слабой гипотезы Гольдбаха. По состоянию на 2018 год доказательство широко принято в математическом сообществе, однако оно еще не было опубликовано в рецензируемом журнале).

В любом случае, все ждут доказательства сильной гипотезы.

Что мы знаем!

В 1930 году было доказано, что любое натуральное число больше 1 может быть записано в виде суммы не более чем C простых чисел, где C < 800 000 [Примечание — мы хотим, чтобы C = 2].
В последнее десятилетие было показано, что каждое четное число n >= 4 на самом деле является суммой не более чем 6 простых чисел (т.е. С <= 6). Позже результат был улучшен до C <= 4.

Забавный факт — гипотеза Гольдбаха является частью сюжета испанского фильма 2007 года »Западня Ферма».

Отказ от ответственности: название статьи вводит в заблуждение. После рассказа о 4 нерешенных задачах я хотел бы показать одну математическую проблему (пятая проблема), которая была недавно решена (в 2004 году).

5. Тест простоты числа принадлежит классу P (2004)

Допустим, вам дано число n = 10089886811898868001. Вас спрашивают, простое ли это число. Первое, что вам приходит на ум, так это,

Алгоритм A — проверить для каждого числа 1 < k < n делится ли n на k. Вы можете оптимизировать этот алгоритм, понимая, что если n не является простым, то n будет иметь такой множитель k, что $k \leq \sqrt{n}$

Алгоритм B — итак, вы проверяется только $1 < k \leq \sqrt{n}$

Хорошо, но погодите, что такое »P»?

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

Итак, что такое быстрый алгоритм?

Для любой заданной проблемы у нас имеется размер ввода (назовем его x). Для нашей задачи размер ввода — это количество цифр в числе n. Итак, x = 20 для указанного выше n. В общем случаем, при заданном n, $x = \log{n}$

Алгоритм называется быстрым (алгоритм с полиномиальным временем), если он решает задачу за f (x) шагов, где f — полиномиальная функция.

Если взглянуть на вышеупомянутые алгоритмы, то получим, что мы имеем n шагов в алгоритме А и $\sqrt{n}$ шагов в алгоритме B.

Итак, размер ввода в нашем случае — $\log{n}$

Обозначим $\gamma(x)$ — количество шагов в алгоритме для данного размера ввода x.

Для алгоритма А, $\gamma (x) = n \; шагов = e ^ {\log{n}} = e ^ x \; шагов$

Для алгоритма B, $\gamma (x) = \sqrt {n} \; шагов = \sqrt {e^x} \; шагов = e^{0.5x} \; шагов$

В обоих случаях алгоритмы имеют экспоненциальное время. В течение 400 лет математики пытались выяснить, можно ли решить задачу определения простоты числа за полиномиальное время. Оказывается, что да. Новость об этом распространилась в математическом сообщество (особенно среди теоретиков чисел) в 2004 году, когда об этом объявили профессор и двое его студентов из IITK.

Алгоритм (известный как тест простоты AKS) был опубликован в статье под названием »Primes Is In P», где показывается, что задача (независимо от того, является ли n простым или нет), может быть решена за ~ $\log ^{12}n$ шагов. Позже были внесены некоторые улучшения, сократившие время до ~ $\log^6 n$ шагов, также выдвигались предположения, что время можно уменьшить и вовсе до ~ $\log^3 n$ шагов (прим. переводчика — предположение оказалось ложным).

Дата-центр ITSOFT — размещение и аренда серверов и стоек в двух дата-центрах в Москве. За последние годы UPTIME 100%. Размещение GPU-ферм и ASIC-майнеров, аренда GPU-серверов, лицензии связи, SSL-сертификаты, администрирование серверов и поддержка сайтов.