Будем ре­шать чуть обобщённую за­да­чу, а имен­но: за­фик­си­ру­ем на­ту­раль­ное 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 не­чет­ное а не де­лит­ся на 2^k. Пред­по­ло­же­ние при­ве­де­но к про­ти­во­ре­чию.

По­про­бу­ем по­лу­чить ре­ше­ние в том же духе для про­из­воль­но­го p. Не­боль­шой до­гад­кой, ко­то­рую нужно сде­лать на этом этапе ре­ше­ния, будет то, что счи­тать надо сумму p  — 1-х сте­пе­ней. Сла­бой под­сказ­кой в эту сто­ро­ну яв­ля­ет­ся то, что p – 1  =  1 для двой­ки p  =  2, и в этом же слу­чае сра­бо­тал под­счет суммы пер­вых сте­пе­ней. Го­раз­до более силь­ной  — то что p  — 1-е сте­пе­ни по мо­ду­лю p ведут себя про­сто  — это 1 если число не равно нулю, 0, если равно.

Итак, далее счи­та­ем что обо­зна­чим

Лемма 1. За­ме­тим, что и До­ста­точ­но до­ка­зать этот факт для по­сколь­ку

Для S(p^k) про­ве­дем ин­дук­цию по k. При k  =  1 утвер­жде­ние сле­ду­ет из Малой тео­ре­мы Ферма: среди сла­га­е­мых p – 1 еди­ни­ца и один ноль. Пусть до­ка­за­но для k, до­ка­жем для k + 1. Тогда

Все срав­не­ния по мо­ду­лю p^k+1.

Те­перь для каж­до­го j: рас­смот­рим сумму

Рас­кро­ем все сте­пе­ни по би­но­му Нью­то­на, по­лу­чим сла­га­е­мые вида

С дру­гой сто­ро­ны, все члены в S_j(n)  — это пе­ре­став­лен­ные в каком-то по­ряд­ке остат­ки по мо­ду­лю n чле­нов суммы S(n), то есть Итак, мы хотим найти такой набор α_j, чтобы до­мно­жив на него срав­ни­мо­сти и сло­жив мы смог­ли бы прий­ти к про­ти­во­ре­чию. Сде­лать это по­мо­жет вто­рая лемма.

Лемма 2. Су­ще­ству­ют такие целые числа α₁, ..., α_p – 1, что

Сна­ча­ла по­ка­жем, как из этой леммы вы­ве­сти остав­шу­ю­ся часть утвер­жде­ния за­да­чи. Рас­смот­рим срав­ни­мость

С одной сто­ро­ны, если рас­крыть все S_j по би­но­му Нью­то­на, и со­брать вме­сте члены вида то по Лемме 2 перед каж­дым чле­ном ко­эф­фи­ци­ент, рав­ный нулю по мо­ду­лю p^k. Тогда:

Вспом­нив, что видим, что все члены вида со­кра­ти­лись с пра­вой ча­стью, итак

Но пер­вая скоб­ка не де­лит­ся на p по Лемме 2, а S(n) не де­лит­ся на p^k по Лемме 1. Оста­лось до­ка­зать лемму 2. Спер­ва от­ме­тим, что если вме­сто на­бо­ра целых чисел α_j уда­лось по­до­брать набор ра­ци­о­наль­ных чисел β_j, таких что их зна­ме­на­те­ли не де­лят­ся на p, все срав­ни­мо­сти из усло­вия леммы за­ме­ни­лись на ра­вен­ства, а по­след­нее вы­ра­же­ние равно це­ло­му числу, не де­ля­ще­му­ся на p  — то лемма до­ка­за­на, до­ста­точ­но все β_j за­ме­нить на срав­ни­мые с ними по мо­ду­лю p^k целые числа. Срав­ни­мость опре­де­ле­на кор­рект­но по­сколь­ку зна­ме­на­те­ли не де­лят­ся на p.

Те­перь оста­лось взять

Чи­та­те­лю оста­ет­ся упраж­не­ние до­ка­зать (на­при­мер, по ин­дук­ции, по­сколь­ку про­сто­та p здесь уже не важна), что во всех усло­ви­ях Леммы 2, кроме по­след­не­го, по­лу­ча­ет­ся 0, а в по­след­нем

Ответ: все n, не де­ля­щи­е­ся ни на 2, ни на 3, ни на 5.