How to count the number of solutions for this expression modulo a prime number $p$? I am trying to prove the following theorem

Let $p$ be a prime number and let $r$ be a divisor of $p-1$. Then the number of distinct values of $x \pmod{p}$ such that, $\;x^r \equiv 1 \pmod{p}\;$ and $x^i \not \equiv 1 \pmod{p}$ for any $i < r$, is $\phi(r)\;$ ( $\phi$ being totient function ).

I tried to prove the above using induction. But now to prove the above I have to prove the theorem below which I am unable to prove.

Let $p$ be a prime number and let $r$ be a divisor of $p-1$. Then the number of distinct values of $x \pmod{p}$ such that, $\;x^r \equiv 1 \pmod{p}\;$ is $r$.

How do I go about proving the second theorem independent of the first theorem ( ie. without using the first theorem ) ?
 A: Are you familiar with the following result? Assuming this result (which can be obtained by using Lagrange's Theorem).
Theorem:
Let $f(x)=x^n+\sum_{k=0}^{n-1}a_kx^k$ be a polynomial of degree $n$. Then $f(x) \equiv 0 \pmod{p}$ has exactly $n$ distinct solutions if and only if $f(x)$ divides $x^p-x$ modulo $p$.
Proof of the result you are looking for:
Let $p-1=rt$ for some $t \in \mathbb{Z}$. Then consider
$$x^{p-1}-1=x^{rt}-1=(x^r-1)(x^{(t-1)r}+ \dotsb + 1).$$
This shows that 
\begin{align*}
x^r-1 &| x^{p-1}-1\\
x^r-1 &| x(x^{p-1}-1)\\
x^r-1 &| x^{p}-x.
\end{align*}
Now use the theorem with $f(x)=x^r-1$ to prove the claim.
(Sketch) Proof of Theorem:
Suppose $f$ has $n$ solutions in $\mathbb{Z}_p$, then for sure $n \leq p$. Using the division algorithm we get
$$x^p-x =f(x)q(x)+r(x), \qquad 0 \leq \text{deg }r(x) < n.$$
If $a \in \mathbb{Z}_p$ is a root of $f$, then using Fermat's little theorem we get
$$a^p-a =0=r(a).$$
Thus every root of $f$ is a root of $r$, but $r $ has degree less than $n$ so it should be identically $0$ (here I'm using Lagrange's theorem).
Thus $f(x)$ divides $x^p-x$. 
Now for the converse. Suppose we have
$$x^p-x=f(x)q(x).$$
Then degree of $q$ has to be $p-n$, thus it can have at most $p-n$ distinct roots (again Lagrange). But $x^p-x$ has exactly $p$ distinct roots. Thus $f$ should have $n$ distinct roots.
I hope this helps a bit.
