Республиканская олимпиада по математике, 2010 год, 11 класс

Известно, что для натурального числа $n$ существует натуральное число $a$ такое, что $a^{n-1}\equiv 1 \pmod n$, а для любого простого делителя $p$ числа $n-1$ верно, что $a^{(n-1)/p}\equiv 1 \pmod n$. Докажите, что $n$ — простое.

Комментарий/решение

Мне кажется или здесь есть опечатка.

Да, здесь опечатка. В этой задаче на русском и на казахском разные условии(в казахском правильный).

Из условия следует, что $n-1$ показатель числа $a$ по модулю $n.$ Тогда

$$\{a^1,\ldots,a^{n-1}\}=\{1,\ldots,n-1\},$$

но с другой стороны $(a,n)=1,$ то есть числа $1,\ldots,n-1$ взаимно просты с $n,$ тогда $n-$простое.

Малая теорема Ферма и все