Малая теорема Ферма
Малая теорема Ферма. Если p — простое число и a — целое число, не делящееся на p, то аᵖ⁻¹– 1 делится на p.
Доказательство. Рассмотрим такую задачу. На карусели p одинаковых сидений. У маляра есть a красок. Сколькими способами он может раскрасить сидения карусели, если раскраски, переходящие друг в друга при повороте, считаются одинаковыми?
Разберём сначала на примере.
На рисунке изображены все способы раскраски в 2 цвета круга, который разделён на 5 равных секторов. Среди них выделяются два способа — когда весь круг синий и когда он весь красный. А остальные разбиты на 6 групп по 5 раскрасок, получающихся одна из другой поворотом.
Теперь в общем виде. Сначала закрепим карусель на месте. Имеется аᵖ способов покрасить её сидения (по а вариантов для каждого их р сидений). Теперь пусть карусель вращается. Большую часть раскрасок мы посчитали по р раз (так, в приведённом примере раскраски ССККК, КССКК, ККССК, КККСС, СКККС считаются одинаковыми). Действительно, все аᵖ – а несплошные раскраски учтены ровно р раз, так как р — простое, и каждый из р поворотов такой раскраски при наложении не совпадает с другим поворотом, поскольку для простого р отсутствуют центральносимметричные варианты раскраски. (В случае же, если бы р было составным, некоторые раскраски обладали бы центральной симметрией и некоторые повороты совпадали бы при наложении, а значит, такие раскраски были бы учтены меньше, чем р раз).
Исключения составляют одноцветные раскраски (по а штук), которые мы посчитали по одному разу. Вычтем их, поделим на р и добавим обратно. Получится (аᵖ – а )/р + а способов.
Поскольку количество способов не бывает дробным, число аᵖ –а обязано нацело делиться на p. Теорема доказана.