When is $2^{2n}-2^n+1$ prime? Is it known when
$2^{2n}-2^n+1$
is prime?
It seems to be only when n is 1,2,4 or 32.
 A: Based on standard heuristics, one should expect there to be infinitely many such $n$ (Edit: Actually see below). By the prime number theorem, the "chance" that $2^{2n}-2^n+1$ should be prime should be about $$\frac{1}{\log (2^{2n}-2^n+1) } \sim \frac{1}{n \log 2}.$$
Since $$\sum_{i=1}^\infty \frac{1}{n \log 2} $$ diverges we should expect infinitely many such primes, barring some congruence issue or factorization trick, which do not seem to show up.
We can however rule out some specific cases. For instance one can never have $5|n$ since $x^{10}-x^5 +1$ has  $(x^2-x+1)$ as a factor. This also rules out 7, 11, 13, 17, 19,23  as prime factors, but not 3. It is possible that $x^{2p} - x^p +1$ must always have a $x^2-x+1$ for any prime $p \geq 5$. Edit to note: This is true by Will Savin's remark below. And this means that one only can have n be a power of 2 times a power of 3, and if we redo the heuristic with that restriction we then expect only finitely many values.
A: Expanding on the remarks by Pace Nielsen (with an additional result that we need only consider $n>2$ a multiple of $4.$):
$x^n-1=\prod_{d \mid n}\phi_d(x)$. The factors are irreducible over the rationals.
In particular $$x^6-1=\phi_1(x)\phi_2(x)\phi_3(x)\phi_6(x)=(x-1)(x+1)(x^2+x+1)(x^2-x+1)$$
And $$\phi_6(x^n)=x^{2n}-x^n+1$$ is a factor of $x^{6n}-1.$ It is an irreducible rational polynomial exactly if  $n$ is of the form $n=2^i3^j,$ then $$\phi_6(x^n)=\phi_{6n}(x)$$ .
But if $p$ is prime to $6$ then $$\phi_6(u^p)=\phi_p(u)\phi_{6p}(u)$$ so for $n=pm$ $$\phi_{6}(x^n)=\phi_p(x^m)\phi_{6p}(x^m).$$
Accordingly, a necessary condition for  $b^{2n}-b^n+1$ to be prime is that $n$ is of the form $2^i3^j.$
In the event that $b \bmod 3=-1$ we also need $n$ even lest $b^{2n}-b^n+1 \bmod 3=0.$
Finally, in the given case that $b=2,$ we have that for $n=4k-2>2$ the integer $2^{2n}-2^n+1$ has two factors of roughly equal size.
For example $2^{36}-2^{18}+1=68719214593=246241\cdot 279073.$
This is due to the following interesting Aurifeuillean factorization
$$\left(x^{4 k -2}+x^{2 k -1}+1+(x^{3 k -1}+x^{k})\right) \left(x^{4 k -2}+x^{2 k -1}+1-(x^{3 k -1}+x^{k})\right)\\ =x^{8 k -4}+(2 x^{6 k -3}-x^{6 k -2})-(x^{2 k}- 2 x^{2 k -1})+(3 x^{4 k -2}-2 x^{4 k -1})+1$$
Putting $x=2,$ the first two pairs become $0$ and the third $2^{4k-2}.$
So the question might be phrased "when does the Mersenne number $2^n-1$ have factors other than those suggested by algebra?" Here restricted to $n=6m.$ That is the subject of the Cunningham Project where much information (in very condensed form) can  be found.
