Does every prime of the form $4k+1$ divide a number of the form $4^n+1$?

Question

While playing around with Fermat's little theorem I was asking myself the question in the title and I can't answer it...

Answer 1

No. Take $p = 73$ as a counterexample. $4$ has order $9 \pmod{73}$ and we get that $4^n + 1$ is periodic $\bmod 73$ with cycle $$5, 17, 65, 38, 3, 9, 33, 56, 2.$$

In general, your claim fails if $\textrm{ord}_p(4)$ is odd.

Answer 2

Taking lulu's answer note that counterexamples here require $p|2^{2n}+1$ and we need $4$ to have odd multiplicative order modulo $p=4k+1$. The multiplicative group $\bmod p$ has order divisible by $4$ so that $4$ must be a fourth power in this multiplicative group.

That means $2$ must be a square $(2^2=4)$, and that means $p\equiv 1 \bmod 8$, which means that $2$ must now be a fourth power for the order of $4$ to be odd. In particular, as lulu has observed, $2$ cannot be a primitive root.

The condition here is related to biquadratic reciprocity and requires there to be integers with $x^2+64 y^2=p$. The condition is not yet sufficient, because if $p=2^{r+1}q+1$ where $q$ is odd, $2$ must be an $2^{r^{th}}$ power modulo $p$. This requires further checking if $x\equiv \pm 1 \bmod 8$.

This accounts for the sparsity of counterexamples, the first few of which which come out as $$73=9+64\cdot 1$$$$89=25+64\cdot 1$$$$223=1693+64\cdot 1$$$$281=25+64\cdot 4$$$$337=81+64\cdot 4$$