Обратные остатки

Нам будет удобнее думать, что — перестановка не чисел, а вычетов по модулю Запишем каждую перестановку в виде двух строк, в каждой из которых расставлены все вычеты. При этом — это вычет во второй строке, над которым в первой строке стоит По условию мы рассматриваем только такие перестановки, в которых ни под одним вычетом не стоит он сам (для краткости назовём их хорошими). В каждой хорошей перестановке умножим все вычеты в обеих строках на При этом снова получится хорошая перестановка (так как при умножении на всех вычетов снова получаются все вычеты по этому модулю, и если то а выражение умножится на Таким образом, мы установили соответствие между хорошими перестановками, у которых вычет этого выражения равен и теми, у которых он равен Поскольку для каждого вычета существует вычет для которого наша операция обратима, а соответствие взаимно-однозначно, откуда и следует, что перестановок двух требуемых видов поровну.