Let $p, q$ be prime numbers and $n \in \mathbb{N}$ such that $p \nmid (n-1)$. If $p \mid (n^q - 1)$ then show that $q \mid (p-1)$.
Using Fermat's Theorem I got $n^{p-1} \equiv n^q \, (\text{mod}\, p)$. How do I get to $p \equiv 1 \, (\text{mod} \, q)$? Have I used Fermat's Theorem correctly or did I overlook some hypothesis?
A detailed proof would be much appreciated.
Observe that $n^q\equiv1\pmod p$ but $n\not\equiv1\pmod p$. As $q$ is prime, then $n$ has order $q$ in the multiplicative group $(\Bbb Z/p\Bbb Z)^*$ which has order $p-1$. By Lagrange's theorem $q\mid (p-1)$, since the order of an element in a finite group divides the order of the group.