Multiplicative order and primitive roots

Let $p$ be an odd prime and r an integer coprime to $p$. I am trying to show that if $r^{p-1}/q$ is not equal to $1$ for all primes $q$ dividing $p$, then $r$ is a primitive root modulo $p$. The hard part is that we only need consider the primes $q$ dividing $p$ for some reason. Thanks for any help you can give.

If $r$ is not a primitive root, then $r$ has order $m$ where $m$ is a proper divisor of $p-1$. But then $m$ divides $\frac{p-1}{q}$ for some prime divisor of $q-1$.
If this does not seem obvious, note that $\frac{p-1}{m}$ is divisible by some prime $q$. Thus $\frac{p-1}{m}=kq$ for some $k$. But then $km=\frac{p-1}{q}$, so $m$ divides $\frac{m-1}{q}$.
It follows that $r^{(p-1)/q}\equiv 1\pmod{p}$. But the problem specified that $r^{(p-1)/q}\not \equiv 1\pmod{p}$.
• Not really. Want (the smallest) prime dividing $\frac{p-1}{m}$ where $m$ is the order of $r$. – André Nicolas Jul 30 '13 at 19:03
Lagrange's theorem tells us, that the smallest $k$ satisfying $r^k=1$ in $\mathbb Z_p^*$ divides $|\mathbb Z_p^*|=p-1$. So there is some $a$, such that $ka=p-1$ for this $k$.
Assume, $r$ is not primitive, then $a>1$, so you can write $a=qb$, where $q$ is a prime. Now $kqb=p-1$. Then $r^k=1$ implies $r^{kb}=1$ and $$1=r^{kb}=r^{\frac{p-1}{q}}$$ is a contradiciton to your precondition.