How to show that that $q \mid p-1$?

Question

Let $p, q$ be prime numbers and $n ∈ \mathbb{N}$ such that $p \not\mid n- 1$. If $p \mid n^q -1$ then show that $q \mid p-1$.

My ideas: I was thinking about the formula $$n^q -1 = (n-1)(n^{q-1} + n^{q-2} +\cdots+1),$$ but now here I do not know how to show that $q \mid p-1$.

Any hints or solution can be appreciated.

Answer 1

Since $p \mid n^q - 1$, then $(p, n) = 1$. By Fermat's little theorem, $p \mid n^{p - 1} - 1$, thus$$ (n^q - 1, n^{p - 1} - 1) = n^{(q, p - 1)} - 1 \Longrightarrow p \mid n^{(q, p - 1)} - 1. $$

Suppose $q \not\mid p - 1$, then $(q, p - 1) = 1$, which implies $n^{(q, p - 1)} - 1 = n - 1$, contradictory to $p \not\mid n - 1$. Therefore, $q \mid p - 1$.

Answer 2

$\bmod p\!:\ n^{\large q}\equiv 1\,\Rightarrow\, k:= {\rm ord}(n)\mid q\,\Rightarrow\,k = 1\,$ or $\,q,\,$ But $\,k=\color{#c00}1\,\Rightarrow\ n^{\large \color{#c00}1}\equiv 1\,$ contra hypothesis.

Therefore $\,{\rm ord}(n) = k = q\ $ so $\ a^{p-1}\equiv 1\,\Rightarrow\, q\mid p-1$