Let $p,q\in \mathbb{P}$ and $r\in\mathbb{Z}$ with $r\equiv 1 \mod p$ and $r^q\equiv 1 \mod p$. Then $p\equiv 1 \mod q$. Why? 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.
 A: $r^{p-1} \equiv 1 \pmod p \quad \quad \text{Fermat's Theorem}$
and $r^q \equiv 1 \pmod p$
$\implies q|p-1$
A: Let $d=\gcd(p-1,q)$. Then there exist integers $x$ and $y$ such that $(p-1)x+qy=d$. 
From $r^{p-1}\equiv 1\pmod p$ (Fermat) and $r^p\equiv 1\pmod{p}$ we conclude that $r^d\equiv 1 \pmod{p}$.
We know $r\not\equiv 1\pmod{p}$, so $d \ne 1$. The only other divisor of $q$ is $q$.
A: Let $f$ be the least positive integer such that $r^f \equiv 1$ (mod $p$).
Let $q = fk + l$, where $0 \leq l < f$.
Since $r^l \equiv 1$ (mod $p$), $l = 0$.
Hence $f|q$.
Since $q$ is prime, $q = f$.
Since $r^{p-1} \equiv 1$ (mod $p$) by Fermat, the similar argument as above shows $f|p - 1$, hence $q|p - 1$ and we are done.
A: Hint $\ $ The set $\,\cal O\,$ of integers $\rm\:n >0\:$ such that $\rm\:r^n \equiv 1\:$ is closed under positive subtraction, i.e.
$$\rm \color{#C00}n>\color{#0A0}m\,\in\,{\cal O}\ \Rightarrow\ 1\equiv \color{#C00}{r^n} \equiv r^{n-m}\, \color{#0A0}{r^m} \equiv r^{n-m}\, \Rightarrow\ n\!-\!m\,\in\,{\cal O}$$
So, by the Theorem below, every element of $\rm\,\cal O\,$ is divisible by its least element $\rm\:\ell\ \! $ := order of $\rm\,r.$ Therefore $\,\ell\,$ divides the prime $\rm\,q\in\cal O,\:$ thus $\,\ell = 1\,$ or $\rm\,\ell = q.\:$ But if $\ \ell = 1\,$ then $\rm\,r^1\equiv 1\,$ contra hypothesis. Thus $\rm\ \ell = q.\:$ By little Fermat  $\rm\,p\!-\!1\in \cal O,\:$ hence $\rm\,q\,$ divides $\rm\,p\!-\!1\,$ by the Theorem. 
Theorem $\ \ $ If a nonempty set of positive integers $\rm\,\cal O\,$ satisfies $\rm\ n > m\, \in\, {\cal O} \ \Rightarrow\  n\!-\!m\, \in\, \cal O$
then every element of $\rm\,\cal O\,$ is a multiple of the least element $\rm\:\ell \in\cal O.$
Proof $\  $ If not there's a least nonmultiple $\rm\:n\in \cal O,\:$ contra  $\rm\:n\!-\!\ell \in \cal O\:$ is a nonmultiple of $\rm\:\ell. \ $ QED
For more on the key innate structure  see this post on order ideals and denominator ideals.
