# Problem on divisibility (Fermat's Theorem?) [duplicate]

This question already has an answer here:

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.

## marked as duplicate by Saad, José Carlos Santos, Davide Giraudo, Xam, Robert SoupeMar 22 '18 at 18:22

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• I bet this is a question from homework. – Saad Mar 22 '18 at 7:29

## 1 Answer

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.