Для эрудитов. Газета Информатика № 10 2012 г.

Самое большое простое число

Как известно,  простыми называют числа, неимеющие других делителей, кроме самого себя и
единицы. Поиском таких чисел издавна занимаются многие исследователи (хотя, казалось бы, какаяот них польза!). Один из рекордов поставил в свое время Леонард Эйлер, найдя простое число 2³¹ – 1 ==  2 147 483 647.

Строго говоря, название данной заметки является неправильным, так как речь идет о самом большом из  известных простых чисел, и, возможно, пока вы читаете эти строки, найдено еще большее простое число. Максимального же простого числа не существует вообще! Первое доказательство это го принадлежит древнегреческому математику Евклиду, жившему около 300 г. до н.э. Суть его в следующем. Предположим, что мы нашли самое большое простое число. Перемножим все известные простые числа и прибавим к произведению 1. Полученное число (большее “нашего”) будет простым,так как при делении на любое число результат не
будет целым, в остатке всегда будет 1. Если то же самое сделать применительно к новому “наибольшему” простому числу, то также получим еще большеепростое число и т.д. Не правда ли — изящно?
Наибольшим известным простым числом по состоянию на февраль 2012 года является 2^43112609– 1.Оно содержит 12 978 189 десятичных цифр. Его нашли в США 23 августа 2008 года на математическом факультете университета UCLA в рамках проекта по распределенному поиску простых чисел Мерсенна3  — GIMPS (Great  Internet Mersenne PrimeSearch).

Кстати, Фонд электронного фронтира (ElectronicFrontier  Foundation, EFF) выплачивал денежные призы за нахождение простых чисел из 1 000 000 и 10 000 000 десятичных цифр. А за открытие простого числа, состоящего из 100 миллионов цифр, объявлена награда в 150 тысяч долларов…