Primes $p$ such that $ord_p(3)$ is a power of $2$ I'm trying to solve this problem, and i need to find all primes $p$ for which $ord_p(3)$ is a power of $2$.
If such primes exist then they are of the form $p=2^km+1$ with $k\geq1$ and $m$ an odd integer, because $ord_p(3)$ is a power of $2$ we can assert that $p+1\leq 3^{2^k}$ which affirms that there is no such primes if $3^{2^k}\leq p$, numerically I find only fermat primes.

Question Can we find all odd primes $p$ such that $ard_p(3)$ is a power of $2$

 A: Primes $p$ with the property that $\operatorname{ord}_p(3)=2^k$ are surely factors of the number
$$
N_k:=3^{2^k}-1.
$$
Furthermore, if an odd prime $p\mid N_k$, then the order of $3$ modulo $p$ is always a power of two (as the order must be a factor of $2^k$).
On the other hand
$$
N_{k+1}=3^{2^{k+1}}-1=(3^{2^k}-1)(3^{2^k}+1)=N_k(N_k+2).
$$
Clearly $\gcd(N_k,N_k+2)=2$, so if $p$ is an odd prime factor of $N_k+2$ we can be certain that the order of $3$ modulo $p$ is exactly $2^{k+1}$. Because $N_k$ is not a power of two for any $k>1$ (Catalan's conjecture, now a theorem, implies this immediately, but is probably overkill), we see that for any $k>1$ there exists at least one prime $p$ such that
$\operatorname{ord}_p(3)=2^k$. This immediately implies that there are infinitely many primes with this property.
Here's the beginning of the list
$$
\begin{array}{c|l}
k&\text{primes with $\operatorname{ord}_p(3)=2^k$}\\
\hline
2&5\\
3&41\\
4&17,193\\
5&21523361\\
6&926510094425921\\
7&1716841910146256242328924544641\\
8&257,275201,138424618868737, 926510094425921, 3913786281514524929,153849834853910661121
\end{array}
$$
At which point my patience to wait for another factorization runs out. Surprisingly few primes actually. Probably somebody else knows more about this.
