Карта → событие
Люка: рекордное простое — вручную
Числа Мерсенна
Числа вида
$$M_p=2^{p}-1$$
носят имя французского монаха Марена Мерсенна, опубликовавшего в 1644 году список показателей $p\leqslant257$, при которых, по его мнению, $M_p$ просто:
$$p=2,\,3,\,5,\,7,\,13,\,17,\,19,\,31,\,67,\,127,\,257 .$$
Список содержит пять ошибок: 67 и 257 в него попали напрасно, а 61, 89 и 107 пропущены. Проверить его целиком удалось лишь к 1947 году — то есть на проверку одной страницы ушло три века. Имя тем не менее закрепилось, и это ещё один пример закона Стиглера.
Первое, что стоит заметить: показатель обязан быть простым. Если $p=ab$, то
$$2^{ab}-1=(2^{a}-1)\left(2^{a(b-1)}+\cdots+2^{a}+1\right),$$
то есть $M_p$ делится на $2^{a}-1$. Обратное неверно: $2^{11}-1=2047=23\cdot89$.
Числа Мерсенна связаны с совершенными числами Евклида: каждому простому $M_p$ отвечает чётное совершенное число $2^{p-1}M_p$. Известно 52 простых Мерсенна — и, следовательно, ровно столько же чётных совершенных чисел.
Тест
Эдуард Люка (1842–1891) занимался последовательностями, обобщающими числа Фибоначчи:
$$U_{n+1}=P\,U_n-Q\,U_{n-1},$$
и обнаружил, что их свойства делимости дают критерий простоты, а не только необходимое условие, как у теста Ферма.
В окончательном виде (доработанном Дерриком Лемером в 1930 году) тест выглядит так:
Тест Люка — Лемера. Положим $s_0=4$ и $s_{k+1}=s_k^{2}-2$. Тогда при простом $p>2$ число $M_p=2^{p}-1$ просто тогда и только тогда, когда $s_{p-2}\equiv 0 \pmod{M_p}$.
Проверим для $p=5$, $M_5=31$: $s_0=4$, $s_1=14$, $s_2=194\equiv 194-6\cdot31=8$, $s_3=64-2=62\equiv0\pmod{31}$. Так как $p-2=3$, тест пройден: 31 просто. $\checkmark$
Для $p=11$, $M_{11}=2047$: $s_0=4$, $s_1=14$, $s_2=194$, $s_3=37634\equiv 1481$, …, $s_9\ne0$ — и действительно $2047=23\cdot89$.
Замечательное свойство теста: он даёт достоверный ответ, а не вероятностный, и требует всего $p-2$ возведений в квадрат по модулю $M_p$. Именно поэтому все рекорды по величине известного простого числа с 1876 года и до сегодняшнего дня, за единственным исключением, принадлежат числам Мерсенна.
Что сделал Люка
В 1876 году он доказал вручную, что
$$2^{127}-1=170\,141\,183\,460\,469\,231\,731\,687\,303\,715\,884\,105\,727$$
просто. Тридцать девять десятичных знаков. Никаких машин; работа заняла, по его свидетельству, девятнадцать лет с перерывами, причём он придумал для вычислений специальную схему с шахматной доской и фишками.
Число оставалось крупнейшим известным простым до 1951 года — то есть до появления электронных вычислителей. Рекорд, поставленный человеком с пером и бумагой, продержался три четверти века.
Тогда же Люка показал, что $2^{67}-1$ составное, — не найдя ни одного делителя, а только по невыполнению критерия. Разложение нашлось лишь в 1903 году, и найдено оно было при обстоятельствах, вошедших в фольклор: на заседании Американского математического общества Фрэнк Нельсон Коул молча вышел к доске, возвёл 2 в 67-ю степень, вычел единицу, затем в столбик перемножил $193\,707\,721\times 761\,838\,257\,287$, получил то же число и сел на место, не сказав ни слова. Зал аплодировал стоя. На вопрос, сколько это заняло, он ответил: «три года воскресений».
Люка помимо простых чисел
Он вообще был человеком редкого склада — серьёзный математик и одновременно изобретатель головоломок.
Ханойская башня (1883) — его изобретение, выпущенное под псевдонимом «профессор Н. Клаус из Сиама» (анаграмма от «Люка д'Аман»). Задача о переносе $n$ дисков требует $2^{n}-1$ ходов — снова число Мерсенна, и легенда о 64 золотых дисках в храме Брахмы даёт $2^{64}-1\approx1{,}8\cdot10^{19}$ ходов.
Числа Люка $2,1,3,4,7,11,18,\dots$ — та же рекуррента, что у ФибоначчиЛеонардо ПизанскийПривёз в Европу индийские цифры, нуль и счёт пером вместо жетонов на доске; кролики из двенадцатой главы — побочная задача, прославившая его через шестьсот пятьдесят лет., с другим началом; они связаны соотношением $L_n=F_{n-1}+F_{n+1}$ и постоянно всплывают в теории чисел.
Задача о пушечных ядрах (1875). Можно ли сложить квадратную пирамиду из ядер так, чтобы из них же выкладывался квадрат? То есть при каких $n$
$$1^{2}+2^{2}+\cdots+n^{2}=m^{2}?$$
Люка предположил, что единственное нетривиальное решение — $n=24$, $m=70$; строго доказал это Уотсон в 1918 году. Число 24 здесь не случайно: оно же отвечает за исключительность решётки Лича в 24 измерениях и за критическую размерность 26 в бозонной теории струн.
Смерть его была нелепой: на банкете официант уронил посуду, осколок рассёк математику щёку, началось рожистое воспаление, и через несколько дней он умер, сорока девяти лет от роду.
Сегодня
Проект GIMPS (Great Internet Mersenne Prime Search) с 1996 года ищет простые Мерсенна распределённо: тест Люка — Лемера гоняется на десятках тысяч добровольческих компьютеров. Все рекорды последних тридцати лет принадлежат ему. Найденные числа имеют десятки миллионов знаков — распечатать такое число обычным шрифтом заняло бы несколько тысяч страниц.
Бесконечно ли много простых Мерсенна, неизвестно. Эвристика Ленстры — Померанса — Вагстаффа предсказывает, что показателей $p\leqslant x$ должно быть примерно $e^{\gamma}\log_2 x$ — то есть их бесконечно много, но растут они крайне медленно. Доказательства нет.
Задача. Докажите, что если $2^{n}-1$ просто, то $n$ просто, и проверьте, что обратное неверно на примере $n=11$ и $n=23$.
(Ответ: разложение из текста; $2^{11}-1=2047=23\cdot89$, $2^{23}-1=8388607=47\cdot178481$.)
Следующая точка: Бордо и Лувен — где одновременно и независимо докажут то, что ГауссКарл Фридрих Гаусс«Король математиков», у которого напечатанное было заметно меньше сделанного: половина результатов пролежала в дневнике до самой смерти — включая неевклидову геометрию. угадал по таблицам в пятнадцать лет.