Prove that if $p$ is an odd prime that divides a number of the form $n^4 + 1$ then $p \equiv 1 \pmod{8}$

Solution 1:

As you have noticed, $p \equiv 1 \bmod 4$. Then $1 \equiv n^{p-1} = (n^4)^{(p-1)/4} \equiv (-1)^{(p-1)/4} \bmod p$. This means that $(p-1)/4$ is even, i.e., $p\equiv 1 \bmod 8$.

By induction, this argument generalizes to: if an odd prime $p$ divides a number of the form $n^k+1$, where $k$ is a power of $2$, then $p \equiv 1 \bmod {2k}$.

Solution 2:

The purpose of this answer is to give another proof of the generalization suggested in lhf's answer:

Let $p$ be an odd prime, and let $k$ be a positive integer. Suppose there is $x \in \mathbb{Z}$ such that $x^{2^k} \equiv -1 \pmod p$. Then $p \equiv 1 \pmod{2^{k+1}}$.

Proof: We work in the unit group $U(p) = (\mathbb{Z}/p\mathbb{Z})^{\times}$. Since $x^{2^k} \equiv -1$, $x^{2^{k+1}} \equiv (x^{2^k})^2 \equiv (-1)^2 \equiv 1 \pmod p$. Thus the order of $x$ in $U(p)$ divides $2^{k+1}$. To show that it is not smaller, we recall the following

Fact: Let $G$ be a group, $x$ an element of $G$ of finite order $n$, and $a \in \mathbb{Z}^+$. Then the order of $x^a$ is $\frac{n}{\operatorname{gcd}(n,a)}$.

Proof of the Fact: It is no loss of generality to assume that $x$ generates $G$ and thus that $G \cong (\mathbb{Z}/n\mathbb{Z},+)$. For the (easy) proof in this special case, see e.g. Proposition 7 of these notes.

Returning to the main proof, we know that the order of $x$ in $U(p)$ is of the form $n = 2^l$ for some $l \leq k+1$. Since $x^{2^k} = -1$, $x^{2^k}$ has order $2$. Applying the fact with $G = U(p)$, $a = 2^k$ gives

$2 = \frac{2^l}{\operatorname{gcd}(2^l,2^k)} = 2^{l - \operatorname{min}(k,l)}$,

so

$l - \operatorname{min}(k,l) = 1$

and thus $l = k+1$.