Infinitely many prime $p$ with $\text{ord}_p(a)$ is a power of a given prime? Let $a$ be an integer and $\ell$ a prime. I am interested in the following question: Are there infinitely many primes $p$ such that the multiplicative order of $a$ mod $p$ is a power of $\ell$? In order for the multiplicative order mod $p$ to be $\ell^n$, it is necessary that $\ell^n \mid p-1$ and there are infinitely many such $p$. But it is of course not a sufficient condition. Any ideas?
 A: For $a\ne -1,0,1$ and $\ell \ne a-1$.
If $\ell$ divides $a^{\ell^n}-1$ then it divides $a-1$.
So let $p$ be a prime necessarily  $\ne \ell$ dividing some $a^{\ell^n}-1$.
We have $order(a\bmod p) = \ell^m$ for some $m\le n$.
$\Bbb{Z}/p^j\Bbb{Z}^\times$ has $p^{j-1} (p-1)$ elements, so there will be some $f(p^j)$ such that $$order(a\bmod p^j) = p^{f(p^j)} \ell^m$$
This implies that for $j$ large enough, when $f(p^j)>0$, then $p^j$ won't divide any $a^{\ell^n}-1$.
And hence, for $n'$ large enough there is some prime dividing $a^{\ell^{n'}}-1$ but not dividing $a^{\ell^n}-1$.
Which gives the inifinitely many primes you are asking.
A: Here is a proof using elementary number theory.

Assume $a > 1$. Let $S$ denote the union of prime divisors of $a^{l^n} - 1$ for all $n \geq 0$. We prove that $S$ is an infinite set.
Suppose $S$ is finite. Since $a^{l^{n + 1}} - 1$ is a multiple of $a^{l^n} - 1$, there exists an $m$ such that all prime numbers in $S$ divide $a^{l^m} - 1$.
It follows that there exists a positive integer $d$ such that $a^{l^{m + 1}} - 1 \mid (a^{l^m} - 1)^d$.
This can be rewritten as $T \mid (a^{l^m} - 1)^{d - 1}$ where $T = a^{l^{m(l - 1)}} + \cdots + 1$.
But it is clear that $T \equiv l \pmod{a^{l^m} - 1}$ and hence $\gcd(T, a^{l^m} - 1) \mid l$.
This is only possible when $T$ is a power of $l$. Since $T > l$, we have $l^2 \mid T$. Moreover, we must have $l \mid a^{l^m} - 1$ which implies that $l \mid a - 1$.
Thus $a^l - 1 = (a - 1)(a^{l - 1} + \cdots + 1)$ is a multiple of $l^2$ and hence $l^2 \mid \gcd(T, a^{l^m} - 1)$, contradicting $\gcd(T, a^{l^m - 1}) \mid l$.

We have proved that there are infinitely many prime numbers $p$ such that there exists $n$ with $p \mid a^{l^n} - 1$. For each such $p$, the order of $a$ mod $p$ must be a divisor of $l^n$, hence a power of $l$.
