The converse of Fermat's theorem on sums of two squares (if an odd prime $p$ can be expressed as $p=a^2+b^2$, then $p \equiv 1~(\text{mod}~4)$ can be proved as follows:
Let $p$ be an odd prime such that $p=a^2+b^2$. Then $a^2+b^2 \equiv 0~(\text{mod}~p)$. Since $\gcd(b,p)=0$, we have $({a \over b})^2 \equiv -1~(\text{mod}~p)$, implying $({a \over b})^4 \equiv 1~(\text{mod}~p)$. This means that the order $d$ of ${a \over b}~\text{mod}~p$ divides $4$. But $({a \over b})^2 \not\equiv 1~(\text{mod}~p)$, meaning $d \not\mid 2$, so $d=4$. By Fermat's little theorem, we have $4 \mid p – 1$ or $p \equiv 1~(\text{mod}~4)$.
This proof can easily be generalized to prove that any odd prime $p=a^{2^k}+b^{2^k}$ satisfies $p \equiv 1~(\text{mod}~2^{k+1})$. So my question is, if its converse can be generalized, is it possible to generalize Fermat's theorem too? That is, given an odd prime $p \equiv 1~(\text{mod}~2^{k+1})$, can it always be expressed as $p=a^{2^k}+b^{2^k}$?
I did some quick checking myself and saw it doesn't work even for small $k$ (e.g. if $k=2$, $41=5 \cdot 2^{k+1}+1$ fails). But is there any $k>1$ that does work?
Best Answer
The answer is no. Let $k \ge 2$ be given. Then by the prime number theorem in arithmetic progressions there is a constant $c > 0$ such that (for large enough $n$) there are at least $\frac{cn}{\log(n)}$ primes $p$ below $n$ for which $p \equiv 1 \pmod{2^{k+1}}$. However, the total number of integers below $n$ that can be written as $a^4 + b^4$ is at most about $\sqrt{n}$, which is less than $\frac{cn}{\log(n)}$ for large enough $n$. Therefore, most primes will not be of the form $a^4 + b^4$, let alone $a^{2^k} + b^{2^k}$.