Най-голямото известно просто число към октомври 2023 г.
Простите числа на Мерсен —
търсенето на най-голямото просто число
Числата от вида \(2^p - 1\) крият тайна от хиляди години. Хиляди доброволци по целия свят дарят изчислителната мощ на компютрите си, за да намерят следващото рекордно просто число. Защо? И какво прави тези числа толкова специални?
Какво е просто число на Мерсен?
Нека започнем с основите. Просто число е естествено число, по-голямо от 1, което се дели само на 1 и на самото себе си: 2, 3, 5, 7, 11, 13, 17, … Простите числа са строителните блокове на цялата аритметика — всяко естествено число може да бъде разложено на прости множители по единствен начин (основна теорема на аритметиката).
Просто число на Мерсен е просто число от специалния вид \(M_p = 2^p - 1\), където показателят \(p\) също е просто число. Необходимо условие \(p\) да е просто — ако \(p\) е съставно, то \(2^p - 1\) задължително е съставно. Обратното обаче не е вярно: не всяко \(2^p - 1\) при просто \(p\) е просто.
\(M_3 = 2^3-1 = 7\) ✓ просто
\(M_5 = 2^5-1 = 31\) ✓ просто
\(M_7 = 2^7-1 = 127\) ✓ просто
\(M_{11} = 2^{11}-1 = 2047 = 23\times89\) ✗ не е просто — показва, че простотата на \(p\) не гарантира простотата на \(2^p-1\).
Числата носят името на Марин Мерсен (1588–1648), френски монах, теолог и математик, живял по времето на Декарт и Паскал. Мерсен изследва числата от вида \(2^p - 1\) и публикува списък с тези, за които смята, че са прости. Макар списъкът му да съдържа грешки, именно той поставя началото на систематичното изучаване на тези числа.
Историческият рекорд от 2018 г.
Дълги години най-голямото известно просто число беше \(2^{82\,589\,933}-1\), открито от компютърния доброволец Патрик Лароше в рамките на проекта GIMPS през декември 2018 г. Когато е записано в десетична система, това число има 24 862 048 цифри. Само за сравнение — ако го отпечатате с нормален шрифт, ще са необходими около 9000 страници книга. За да го прочетете на глас, ще са ви нужни повече от девет часа непрекъснато четене.
Първите 120 цифри на това число изглеждат така:
1289425213239361064475310309971132180337174752834401423587560…
То беше с почти един милион цифри по-голямо от предишния рекорд — \(2^{77\,232\,917}-1\), открит от GIMPS само две години по-рано, през януари 2016 г.
Новият световен рекорд от 2024 г.
Красивата връзка с идеалните числа
Простите числа на Мерсен крият и неочаквана математическа красота. Идеално число е естествено число, равно на сумата от всичките си правилни делители. Например \(6 = 1+2+3\) и \(28 = 1+2+4+7+14\) са идеални числа.
Ойлер доказва, че всяко четно идеално число е от вида \(2^{p-1}(2^p-1)\), където \(2^p-1\) е просто число на Мерсен. Тоест намирането на ново просто число на Мерсен е равносилно на намирането на ново четно идеално число! Дали съществуват нечетни идеални числа — остава открит въпрос в математиката от над две хиляди години.
За \(M_3=7\): \(2^{3-1}(2^3-1)=4\cdot7=28\) — идеално число ✓
За \(M_5=31\): \(2^{5-1}(2^5-1)=16\cdot31=496\) — идеално число ✓
Тази закономерност е открита от Евклид, а пълното доказателство е дадено от Ойлер.
Тестът на Лукас-Лемер
Как се проверява дали \(2^p-1\) е просто, когато числото има десетки милиони цифри? Не чрез деление на всички възможни делители — това би отнело повече от живота на вселената дори за съвременни суперкомпютри. Вместо това се използва елегантен специализиран алгоритъм — тестът на Лукас-Лемер.
Той работи по следния начин: дефинираме редицата \(s_0 = 4\) и \(s_{k+1} = s_k^2 - 2\). Тогава \(2^p-1\) е просто тогава и само тогава, когато \(s_{p-2} \equiv 0 \pmod{2^p-1}\). Само \(p-2\) итерации са нужни — ефективността му е несравнима с обикновеното пробно деление.
Проектът GIMPS
Великото интернет търсене на просто число на Мерсен — GIMPS (Great Internet Mersenne Prime Search) — е разпределена изчислителна система, стартирала от 1996 г. от Джордж Уолтман. Хиляди доброволци по целия свят инсталират безплатна програма (Prime95/MPrime), която работи на заден план и проверява потенциални прости числа на Мерсен.
Моделът е изключително ефективен: всеки участник получава за проверка различен кандидат за просто число, резултатите се събират централно и при намиране на ново просто число — откривателят получава признание и награда. От основаването си досега GIMPS е открил 18 прости числа на Мерсен, включително всички намерени след 1996 г.
Защо са важни тези числа?
Криптография: Простите числа са в сърцето на съвременната криптография. Алгоритъмът RSA — използван при всяка защитена интернет връзка — разчита на трудността на разлагането на произведение от две огромни прости числа. Колкото по-добре разбираме разпределението на простите числа, толкова по-сигурни можем да правим криптографските системи.
Хипотезата на Риман: Разпределението на простите числа е тясно свързано с нулите на дзета функцията на Риман. Хипотезата на Риман — един от т.нар. „Проблеми на хилядолетието" с награда от един милион долара — засяга именно закономерностите в разпределението на простите числа. Търсенето на огромни прости числа помага на математиците да тестват хипотези в тази посока.
Проверка на изчислителни системи: Намирането на огромни прости числа е един от най-надеждните начини за проверка на стабилността и коректността на компютърен хардуер. Суперкомпютрите в NASA и Intel използват тестове с прости числа, за да верифицират новите процесори.
Хронология на рекордите
Запишете урок
Индивидуални и групови онлайн уроци по математика за цялата страна
- ›НВО по математика след 7 клас
- ›НВО по математика след 10 клас
- ›Кандидатстудентски изпити по математика
- ›Прием в университети в чужбина (ISEE, SAT, A-Level)
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти: Мат. анализ, Линейна алгебра, Аналитична геометрия, Диф. уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.
Коментари
Публикуване на коментар