Малая теорема Ферма

Подсказка 1

Покажем, что таких перестановок не существует (иначе их количество считать сложно, потому что мы не понимаем как устроены остатки произвольных чисел, по произвольному модулю). Остается надеяться, что мы сможем найти какое-либо противоречие, смотря на те степени, с которыми мы умеем работать.

Подсказка 2

Одним из таких является модуль p-1. Ясно, что существует число r такое, что a_r=p-1. Чему равно r^{a_r}?

Подсказка 3

По малой теореме Ферма r^{a_r}=r^{p-1} дает остаток 1 по модулю p. Чему может быть равно r?

Подсказка 4

Назовем S множество остатков чисел i^{a_i} для всех i от 1 до n-1. Предположим, что r не равно 1, но тогда 1^{a_1} сравнимо 1 и тогда в S нашлось сразу 2 единички. Теперь давайте посмотрим на то, чему может быть равен остаток числа (p-1)^{p-1}.

Подсказка 5

(p-1)^{a_{p-1}} сравнимо с (-1)^{a_{p-1}}, следовательно остаток равен числу 1 или -1. Первое из них уже занято, следовательно, остаток равен -1. Что это говорит о числе a_{p-1}?

Подсказка 6

Оно нечетное. Теперь мы поняли, что остатки 1 и -1 соответствуют числам 1 и p-1 в S. Если бы нам удалось найти четную степень, по которому все числа давали остатки равные 1 или -1, то мы бы нашли противоречие. Что это за остаток?

Подсказка 7

Это (p-1)/2. Докажите, что для любого a, не кратного p, число a^{(p-1)/2} сравнимо с 1 или -1.