Решение. Будем решать чуть обобщённую задачу, а именно: зафиксируем натуральное m и будем искать все n, для которых в любом из m множеств все остатки различны. Индекс j пробегает значения
Для начала докажем, что все n, не делящиеся на простые числа меньшие либо равные m + 1, подходят. Рассмотрим перестановку τ: i → (m + 1)i mod n (здесь мы позволим себе вольность считать, что остатки идут от 1 до n, а не от 0 до n – 1 как обычно). Поскольку n взаимно просто с m + 1, остатки не повторяются. Значит, по принципу Дирихле, каждый остаток встречается ровно один раз. Аналогично, каждый остаток встречается ровно один раз и в каждом из множеств
Докажем, что перестановки с требуемыми свойствами не существует если и Предположим обратное, зафиксируем наименьшее такое p и обозначим через k максимальную степень p, на которую делится n.
Сперва рассмотрим случай p = 2. Заметим что
формула легко доказывается по индукции. Тогда сумма n чисел, дающих остатки 1, 2, ..., n, сравнима с по модулю n. Посчитаем двумя способами остаток суммы по модулю n. С одной стороны, все слагаемые дают разные остатки, значит, сумма С другой стороны, по тем же соображениям у суммы отдельно такой остаток, и у суммы такой же, значит, их разность имеет остаток 0. Заметим, что
поскольку n + 1 нечетное а не делится на 2k. Предположение приведено к противоречию.
Попробуем получить решение в том же духе для произвольного p. Небольшой догадкой, которую нужно сделать на этом этапе решения, будет то, что считать надо сумму p — 1-х степеней. Слабой подсказкой в эту сторону является то, что p – 1 = 1 для двойки p = 2, и в этом же случае сработал подсчет суммы первых степеней. Гораздо более сильной — то что p — 1-е степени по модулю p ведут себя просто — это 1 если число не равно нулю, 0, если равно.
Итак, далее считаем что обозначим
Лемма 1. Заметим, что и Достаточно доказать этот факт для поскольку
Для S(pk) проведем индукцию по k. При k = 1 утверждение следует из Малой теоремы Ферма: среди слагаемых p – 1 единица и один ноль. Пусть доказано для k, докажем для k + 1. Тогда
Все сравнения по модулю pk+1.
Теперь для каждого j: рассмотрим сумму
Раскроем все степени по биному Ньютона, получим слагаемые вида
С другой стороны, все члены в Sj(n) — это переставленные в каком-то порядке остатки по модулю n членов суммы S(n), то есть Итак, мы хотим найти такой набор αj, чтобы домножив на него сравнимости и сложив мы смогли бы прийти к противоречию. Сделать это поможет вторая лемма.
Лемма 2. Существуют такие целые числа α1, ..., αp – 1, что
Сначала покажем, как из этой леммы вывести оставшуюся часть утверждения задачи. Рассмотрим сравнимость
С одной стороны, если раскрыть все Sj по биному Ньютона, и собрать вместе члены вида то по Лемме 2 перед каждым членом коэффициент, равный нулю по модулю pk. Тогда:
Вспомнив, что видим, что все члены вида сократились с правой частью, итак
Но первая скобка не делится на p по Лемме 2, а S(n) не делится на pk по Лемме 1. Осталось доказать лемму 2. Сперва отметим, что если вместо набора целых чисел αj удалось подобрать набор рациональных чисел βj, таких что их знаменатели не делятся на p, все сравнимости из условия леммы заменились на равенства, а последнее выражение равно целому числу, не делящемуся на p — то лемма доказана, достаточно все βj заменить на сравнимые с ними по модулю pk целые числа. Сравнимость определена корректно поскольку знаменатели не делятся на p.
Теперь осталось взять
Читателю остается упражнение доказать (например, по индукции, поскольку простота p здесь уже не важна), что во всех условиях Леммы 2, кроме последнего, получается 0, а в последнем
Ответ: все n, не делящиеся ни на 2, ни на 3, ни на 5.