Най-голямото известно просто число към октомври 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 само година по-рано, през декември 2017 г.
Новият световен рекорд от 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\). Тогава за нечетно просто \(p\) числото \(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)
- ›Усвояване на текущия учебен материал (всички класове)
- ›Студенти: Мат. анализ, Линейна алгебра, Аналитична геометрия, Диф. уравнения, Теория на вероятностите, Статистика и др.
Харесва ли ви съдържанието?
Ако тази статия ви е харесала, можете да подкрепите създаването на нови безплатни материали.
Коментари
Публикуване на коментар