4
$\begingroup$

My Question is the above question:

Let $p,q\in \mathbb{P}$ and $r\in\mathbb{Z}$ with $r\not\equiv 1 \mod p$ and $r^q\equiv 1 \mod p$. Then $p\equiv 1 \mod q$. Hence $q|p-1$.

I was calculating to get a proof, but i didn't get it. So maybe someone knows the solution. Thanks.

  • 0
    The linear-algebra and numerical-linear-algebra tags seem to be a little out of place...2012-08-10
  • 1
    From $r^q\equiv 1\pmod{p}$, we conclude that the *order* of $r$ modulo $p$ divides $q$. But since $q$ is prime and the order is not $1$, the order must be $q$. Thus $q$ divides $p-1$.2012-08-10

4 Answers 4