Таблицы Брадиса

Значит, общее число способов раскрасить

Значит, общее число способов раскрасить

Элементы математики в задачах - Г. А. Мерзон

Итак, все способы, кроме одноцветных, подсчитаны p раз, а все одноцветные способы подсчитаны один раз. Значит, общее число способов раскрасить колесо обозрения, состоящее из p одинаковых кабинок, в не более чем a различных цветов равно числу неодноцвет­ных раскрасок, деленному на p, плюс число одноцветных раскрасок,

ap — a . „                       p

то есть —---- 1- а. В частности, ар — а делится на р.

Решение 3. Еще одно решение. Случай a = 0 (mod p) очевиден, по­этому будем решать для ненулевых остатков a. Рассмотрим ори­ентированный граф, вершины которого соответствуют ненулевым остаткам по модулю p, и из вершины x выходит ребро в верши­ну ax. Поскольку умножение обратимо, в каждую вершину входит ровно одно ребро. Таким образом, все остатки разбиваются на цик­лы. Заметим, что длины всех циклов равны, и равны наименьшему натуральному k, для которого ak = 1 (mod p). Следовательно, общее число ненулевых остатков (а именно, p — 1) делится на это число k, откуда ap_1 = (afc)£‘_ = 1 (mod р) и ар — a = a(ap_1 — 1) = 0 (mod р).

Задача 16* (теорема Вильсона). Пусть p — простое число, тогда (p — 1)! = —1 (mod p).

Указание. Докажите, что по модулю p все остатки, кроме ±1, разби­ваются на пары с произведением 1.

Решение. По задаче 12 для любого ненулевого остатка a по модулю p можно найти «обратный» остаток a—1, такой что aa—1 = 1 (mod p),

причем (а—х)—1 = а. Таким образом, все остатки, для которых а—1 = а, разбиваются на пары остатков, дающих в произведении единицу, и не влияют на значение (p — 1)! mod p. Найдем теперь все остат­ки, для которых а—1 = а, то есть а2 = 1 (mod p), что равносильно (а — 1)(а +1) = 0 (mod p), откуда а є {—1,1}.

Итак, произведение всех остатков, кроме 1 и —1, равно 1, а 1 ■ (—1) = —1, откуда (p — 1)! = — 1 (mod p).