Несколько дней назад широко известный в узких кругах математиков видеоблогер Michael Penn опубликовал видео под заголовком "Моё новое любимое доказательство малой теоремы Ферма".
Я поглядел - и нахожусь в некоторой прострации. Точнее, в том её синониме, который из четырех букв, на а начинается на и краткий заканчивается
Потому что одно из трех - или заголовок видео врёт, или Майкл действительно раньше не знал этой техники доказательств, или смысл заголовка в том, что раньше он такие вещи не любил, а вот теперь она ему стала нравиться. В первое верить не хочется, в последнее тоже, - значит, второе?
Вдвойне стрёмно, что излагая комбинаторное (по сути) доказательство, он совершенно не говорит о его комбинаторной природе, а ограничивается только алгеброй.
Так можно было? А зачем?
https://www.youtube.com/watch?v=Ow_9II-DeTI&ab_channel=MichaelPennИзложение того же доказательства на более комбинаторном языке.
Рассмотрим множество вершин правильного p-угольника, и раскрасим каждую вершину в один из a цветов (получая a-цветное ожерелье). Тогда общее число рассматриваемых раскрасок равно a^p.
Среди этих ожерелий есть ровно два типа - те, в которых присутствует ровно один цвет, и те, в которых есть более одного цвета.
Первых - ровно a штук: по одному для каждого из цветов.
Количество ожерелий второго типа сосчитать не совсем просто, но нам этого и не нужно (Майклу Пенну тоже не нужно, но он делает вид, что нужно). Нам важно, что эти ожерелья легко группируются в кучки по p штук - в каждую кучку входят все ожерелья, которые получаются из данного такими поворотами вершин многоугольника, при которых все вершины переходят сами в себя. Таких поворотов ровно p, и все ожерелья в них различны именно потому, что p - простое, и p-периодические ожерелья не могут иметь периодов, меньших чем p.
Это означает, что количество ожерелий второго типа делится нацело на p, то есть (a^p - a) кратно p, - а это и есть малая теорема Ферма.
