While studying primitive roots, I came across the following lemma:
Lemma: Let $p$ and $q$ be primes and suppose that $q^\alpha\mid p-1$, where $\alpha\geq 1$. Then there are precisely $q^\alpha - q^{\alpha -1}$ residue classes $a\pmod p$ of order $q^\alpha$.
However, I also know that given a $d\mid p-1$, $x^d\equiv 1\pmod p$ has $d$ solutions ($p$ is a prime). So, is the lemma in agreement with the previous statement? Because according to the statement shouldn't it be $q^\alpha$ residue classes instead of $q^\alpha - q^{\alpha -1}$ residue classes?
Am I missing something? Where am I going wrong?
There are $q^\alpha$ residue classes of order less than or equal to $q^\alpha$. There are $q^{\alpha-1}$ of order strictly less than $q^{\alpha}$. So there are $q^\alpha-q^{\alpha-1}$ of order exactly $q^\alpha$.
Added There are indeed $q^\alpha$ solutions of the congruence $x^{q^\alpha}\equiv 1\pmod{p}$. They all have order that divides $q^\alpha$. But they do not all have order $q^{\alpha}$. For concreteness, suppose from now on that $\alpha=4$.
Note that $x=1$ is a solution of the congruence $x^{q^4}\equiv 1\pmod{p}$, and $1$ has order $1$. And among the solutions of $x^{q^4}\equiv 1\pmod{p}$, there are the $q$ solutions of $x^q\equiv 1\pmod{p}$. Of these, one has order $1$, and the rest have order $p$. So being a solution of $x^{q^4}\equiv 1\pmod{p}$ does not make $x$ have order $4$.
Among the $q^4$ solutions of $x^{q^4}\equiv 1\pmod{p}$ there are the $q^3$ solutions of $x^{q^3}\equiv 1\pmod{p}$. There all have order a divisor of $q^3$. The rest of the solutions have order $q^4$, giving $q^4-q^3$ elements of order exactly $q^4$.