Let $p,q$ be primes and $n \in \Bbb N,$ such that $p \nmid\ n-1.$ If $p\ |\ n^q-1$ then which one of the following option/s is/are correct?

$(1)$ $p\ |\ q-1.$

$(2)$ $q\ |\ p-1.$

$(3)$ $p\ |\ (p-1)(q-1).$

$(4)$ $q\ |\ (q-1)(p-1).$

My attempt $:$ If I take $p=3, q=2$ and $n=2$ then I find that the given condition holds but option $(1)$ and hence option $(3)$ fails to hold. What about options $(2)$ and $(4)$? It is quite clear that either both the options $(2)$ and $(4)$ are correct or both the options are false. How to prove or disprove $(2)$? Any help in this regard will be highly appreciated.

Thank you very much for your valuable time.

  • $\begingroup$ What have you edited @janmarqz? $\endgroup$ – math maniac. Mar 30 at 15:42
  • 2
    $\begingroup$ Changed the | to \mid in the first line. It makes the slash look nicer $\endgroup$ – Ross Millikan Mar 30 at 15:44
  • $\begingroup$ better latex for $p$ divides not $n-1$ $\endgroup$ – janmarqz Mar 30 at 15:44
  • $\begingroup$ Dub Dub dubuque @Bill Dubuque. $\endgroup$ – math maniac. Mar 30 at 17:36

If $p$ divides $n^{q} - 1$ then $n^{q}\equiv 1$ ($\mathrm{mod}$ $p$). So the order of $n$ modulo $p$ divides $q$. Hence the order is $1$ or $q$, and yet $p$ does not divide $n -1$ so the order is $q$.

Now apply Euler's theorem and once more use the fact that if $n^{k} \equiv 1$ ($\mathrm{mod}$ $p$) then the order of $n$ modulo $p$ divides $k$.

| cite | improve this answer | |

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