Республиканская олимпиада по математике 2010 года за 11 класс | Казахстанские олимпиады

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