Ибн аль-Хайсам: теорема Вильсона до Вильсона

Человек

Абу Али аль-Хасан ибн аль-Хайсам (ок. 965–1040), в латинской традиции Альхазен, — один из крупнейших естествоиспытателей Средневековья, известный прежде всего «Книгой оптики»: там впервые правильно объяснено зрение (свет идёт от предмета в глаз, а не наоборот), описана камера-обскура и проведены настоящие эксперименты с контролем условий.

Биографический сюжет, который обычно рассказывают: приглашённый халифом аль-Хакимом в Каир для устройства плотины на Ниле, он, оценив задачу на месте, понял, что при тогдашней технике она нерешаема, и, опасаясь казни, симулировал сумасшествие; под домашним арестом он провёл около десяти лет — самых плодотворных в его жизни — и вернулся к нормальной жизни лишь после смерти халифа в 1021 году. Историчность деталей оспаривается, но каирский период и его продуктивность сомнений не вызывают.

Критерий простоты

В сочинении «Opuscula» Ибн аль-Хайсам разбирает задачу такого типа:

Найти число, которое при делении на 2, 3, 4, 5, 6 даёт в остатке 1, а на 7 делится нацело.

Первый способ решения — китайская теорема об остатках (о ней ниже); ответ $301=7\cdot43$, и вообще все числа вида $301+420k$.

Второй способ и содержит интересующее нас утверждение. Ибн аль-Хайсам замечает: если $p$ — простое, то $(p-1)!+1$ делится на $p$. Тогда для $p=7$ число $6!+1=721=7\cdot103$ подходит под условие сразу: $6!=720$ делится на 2, 3, 4, 5, 6, значит $721$ даёт остаток 1 при делении на каждое из них.

Честная оговорка об авторстве. Ибн аль-Хайсам утверждение сформулировал; сохранившиеся тексты не позволяют сказать, умел ли он его доказывать, и историки на этот счёт осторожны. Обратную часть («и только тогда») он, по-видимому, не рассматривал вовсе. Так что корректная формулировка такая: критерий известен в Каире около 1000 года, а доказан в Берлине в 1771-м.

Европейская история. В 1770 году Эдвард Уоринг публикует утверждение, сообщая, что его высказал его ученик Джон Уилсон, и честно добавляя, что доказательства ни у кого из них нет. ГауссКарл Фридрих Гаусснемецкий математик и астроном · 1777–1855«Король математиков», у которого напечатанное было заметно меньше сделанного: половина результатов пролежала в дневнике до самой смерти — включая неевклидову геометрию., прочитав это, по легенде заметил, что здесь нужны не обозначения, а понятия. Первым доказал ЛагранжЖозеф Луи Лагранжфранцузский математик и механик итальянского происхождения · 1736–1813Написал механику без единого чертежа, довёл до конца всё, что начали Эйлер и Ферма, и первым понял, что решаемость уравнения зависит от перестановок его корней. (Берлин, 1771), он же первым доказал и обратное утверждение.

Доказательство

Пусть $p$ — простое. Рассмотрим $1,2,\dots,p-1$ — все ненулевые вычеты по модулю $p$. Каждый из них обратим, и обратный единствен. Разобьём их на пары $\{a,a^{-1}\}$; произведение в каждой паре равно 1.

Кто останется без пары? Те $a$, для которых $a=a^{-1}$, то есть $a^{2}\equiv1$, то есть $p\mid(a-1)(a+1)$. Так как $p$ простое, это значит $a\equiv1$ или $a\equiv-1$. Ровно два элемента.

Значит,

$$(p-1)!\equiv 1\cdot(p-1)\cdot\underbrace{1\cdot1\cdots1}_{\text{пары}}\equiv -1 \pmod p . \qquad\blacksquare$$

Проверка: $p=7$: $6!=720=7\cdot103-1$. $\checkmark$ $p=11$: $10!=3628800=11\cdot329891-1$. $\checkmark$

Обратное. Пусть $n$ составное, $n=ab$ с $1<a<n$. Тогда $a$ входит сомножителем в $(n-1)!$, значит $a\mid (n-1)!$; если бы $n\mid (n-1)!+1$, то и $a\mid (n-1)!+1$, откуда $a\mid1$ — противоречие. (Случай $n=4$ разбирается отдельно: $3!+1=7$ на 4 не делится.) $\blacksquare$

Итак, критерий точен: $n>1$ просто тогда и только тогда, когда $n\mid (n-1)!+1$. Заманчиво использовать его для проверки простоты — и совершенно бесполезно: вычисление $(n-1)!$ по модулю $n$ требует $n-2$ умножений, то есть экспоненциально много относительно длины записи $n$. Это хороший пример того, что критерий и алгоритм — разные вещи; практический тест даст только малая теорема Ферма.

Китайская теорема об остатках

Первый метод, которым Ибн аль-Хайсам решает свою задачу, заслуживает отдельного абзаца — и отдельного упоминания Китая, который на этой карте недобран.

Теорема. Если $m_1,\dots,m_k$ попарно взаимно просты, то система $x\equiv a_i \pmod{m_i}$ имеет решение, единственное по модулю $m_1\cdots m_k$.

Впервые задача такого рода появляется у Сунь Цзы (III–V вв.) в «Суань цзин»: найти число, дающее остатки 2, 3, 2 при делении на 3, 5, 7. Ответ 23. Общий метод — «да янь шу», «правило великого обобщения» — дал Цинь Цзюшао (1247) в «Девяти книгах о математике»; он же умел работать с не взаимно простыми модулями.

Сегодня эта теорема — рабочий инструмент вычислений: она позволяет считать по частям, отдельно по каждому простому модулю, а потом собирать ответ. На ней держатся быстрые алгоритмы умножения больших чисел и вся арифметика в криптографии.

Задача. Проверьте критерий для $n=9$ и $n=11$: вычислите $(n-1)!\bmod n$ и убедитесь, что для составного 9 получается 0, а не $-1$. Объясните, почему для составных $n>4$ всегда выходит именно 0.
(Указание: при $n=ab$, $a\ne b$, оба множителя входят в $(n-1)!$; при $n=p^{2}$, $p>2$, туда входят $p$ и $2p$.)

Следующая точка: Пиза — где на придворном состязании решат задачу о квадратах и попутно докажут частный случай теоремы, которой ещё нет.