Задача 60743

Темы:    [ Малая теорема Ферма ] [ Комбинаторика орбит ] [ Правило произведения ]

Сложность: 3 Классы: 9,10,11

Условие

p – простое число. Сколько существует способов раскрасить вершины правильного p-угольника в a цветов? (Раскраски, которые можно совместить поворотом, считаются одинаковыми.)

Решение

Забудем временно про совмещение раскрасок поворотами. Тогда p вершин можно раскрасить a^p способами (см. задачу 60348). Среди этих раскрасок есть a одноцветных. Каждая из оставшихся совмещается с p раскрасками (считая исходную). Поэтому различных неодноцветных раскрасок в p раз меньше:    .

Ответ

  способов.

Замечания

1. Из этого результата немедленно следует малая теорема Ферма (см. задачу 60736).

2. Подумайте, почему важна простота числа p.

Источники и прецеденты использования

книга
Автор	Алфутова Н.Б., Устинов А.В.
Год издания	2002
Название	Алгебра и теория чисел
Издательство	МЦНМО
Издание	1
глава
Номер	4
Название	Арифметика остатков
Тема	Деление с остатком. Арифметика остатков
параграф
Номер	4
Название	Теоремы Ферма и Эйлера
Тема	Малая теорема Ферма
задача
Номер	04.117