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 ) ?
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.