Attempted Proof:

Let $S = \{k: n^k-1 \equiv 0 \pmod{p}, k\in \mathbb{N}\}$. Minimal element $r$ exists by Well-Ordering. we show $r=q$. We note, $\gcd(p,n)=1$, otherwise $p \mid n^q-1 \implies p \mid 1$.

We have:

$n \not\equiv 1 \pmod{p}\implies n^2 \not\equiv n \pmod{p}$ ; [since $p , n$ are coprime and $p$ prime ]. Now, for any $0<j< i < r,$ $n^i \equiv n^j \pmod{p} \implies n^j(n^{i-j}-1) \equiv 0 \pmod{p} \implies (n^{i-j}-1) \equiv 0 \pmod{p} $, contradicting the minimality of $r$.

Now, we proceed to show that, all elements of $S$ are integral multiples of $r$. (Claim 1)

We have, $n^{tr} \equiv 1 \pmod{p} \implies n^{tr+l} \equiv n^l \pmod{p} $, for $0\leq l <r$. Now, for any two such $l$, say $c$ and $d$, with $d<c$ , $n^{tr+c} \equiv n^{tr+d} \pmod{p} \implies n^{tr+d}(n^{c-d}-1) \equiv 0 \pmod{p}$, which again contradicts our assumption that $r$ is the least element of $S$. Hence, Claim 1 is established. But, it implies that $q$ is composite (an impossibility); hence $r$ must be equal to $q$ .

Finally, by Fermat's Little Theorem, we have $n^{p-1} \equiv 1 \pmod{p}$ [ it holds, since $\gcd (p, n) =1$].

Therefore, $p-1$ must be an integral multiple of $q$, i.e. $q \mid p-1$.

PS: I am aware of the duplicates, but I want my solution checked. Thank you.


You appear to be reinventing the wheel (here $\rm ord$ = order of an element). Using this it's a one-liner

$\!\bmod p\!:\ n^{\large q}\equiv 1\,\Rightarrow\, {\rm ord}\, n\mid q\,$ prime, so $\, {\rm ord}\,n = q\,$ by $\,n\not\equiv 1$, so $\ n^{\large p-1}\equiv 1\,$ implies $\, q\mid p\!-\!1$

Said more structurally your set $S$ is a nontrivial set of integers closed under subtraction, so a one-line Euclidean descent proof shows the its least positive element $\,r := {\rm ord}\, n\,$ divides every element of $S$.

  • $\begingroup$ Order of the element in which Group? $U_n$? $\endgroup$ – Subhasis Biswas Feb 9 at 19:22
  • $\begingroup$ @Subhasis In the cyclic group generated by $n$ (note $\,n^{p-1}\equiv 1\,$ by Fermat). But you don't need to know any group theory to understand these fundamental properties of $\,\rm ord$ $\endgroup$ – Bill Dubuque Feb 9 at 19:28
  • $\begingroup$ @Subhasis I added a link to full proofs of these basic properties of $\rm ord.\ \ $ $\endgroup$ – Bill Dubuque Feb 9 at 19:33
  • $\begingroup$ @BillDubuque: I'd be interested in your thoughts on this question $\endgroup$ – J. W. Tanner Jul 1 at 20:23
  • $\begingroup$ @J.W.Tanner I added some links there. If you chase them you should fine much of interest (including Moonshine!). $\endgroup$ – Bill Dubuque Jul 1 at 20:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.