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

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 $$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 . Now, for any two such $$l$$, say $$c$$ and $$d$$, with $$d , $$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$$.
• Order of the element in which Group? $U_n$? – Subhasis Biswas Feb 9 at 19:22
• @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$ – Bill Dubuque Feb 9 at 19:28
• @Subhasis I added a link to full proofs of these basic properties of $\rm ord.\ \$ – Bill Dubuque Feb 9 at 19:33