Infinitely many prime $p$ with $\text{ord}_p(a)$ is a power of a given prime?

Solution 1:

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.

Solution 2:

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$.