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

Problem

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

My attempt was,
Since $p$ divides $n^4 + 1 \implies n^4 + 1 \equiv 0 \pmod{p} \Leftrightarrow n^4 \equiv -1 \pmod{p}$. It follows that $(n^2)^2 \equiv -1 \pmod{p}$, which implies $-1$ is quadratic residue modulo p. Hence $p \equiv 1 \pmod{4} \Leftrightarrow p \equiv 1 \pmod{8}$.

Am I in the right track?

Thanks,

-
What happens with your last statement if $p=5$? Does $p\equiv 1 \pmod{4}$ imply $p\equiv 1 \pmod{8}$? –  M.B. Apr 17 '11 at 1:16
@M.B: Thank you. I got it. –  Chan Apr 17 '11 at 1:26
+1 for showing some thought –  Ross Millikan Apr 18 '11 at 3:04
This is a really interesting question, hence may I ask where you got this question? Also, it reminds me of the three propositions by Fermat, upon which he told Mersenne about June 1640 some statement, which, in the modern terminology, only amount to the so-called Fermat little theorem. Is this related? Indeed, Fermat has investigated the prime divisors of the numbers of the form $a^m+1$, but, unfortunately enough, guessed wrongly, and therefore missed the chance to discover the law of reciprocity. –  awllower Aug 5 '11 at 10:10

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}$.

-
Thanks a lot. I was so close to the answer. –  Chan Apr 17 '11 at 3:54
@lhf could you please explain how we arrive at: p≡1mod4 –  confused Aug 18 '12 at 9:17
@confused, the OP did that. –  lhf Aug 18 '12 at 11:02
@lhf I guess I wasn't able to follow it.. or, maybe there's something I don't understand. Could you elaborate on how we get from (n^2)^2 ≡ -1 (mod p), to p ≡ 1 (mod 4). Please? –  confused Aug 18 '12 at 11:38
@confused, it depends on what you want to assume. One way is that $n^4 \equiv (n^2)^2 \equiv -1 \bmod p$ implies $4\mid\phi(p)=p-1$ because $n^2$ will have order 2 and so $n$ will have order 4. –  lhf Aug 18 '12 at 17:34

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$.

-
I suspect that tags are ranked by the number of questions that use them; group-theory has 620, while elementary-number-theory has 310. (EDIT: Confirmed here) –  Zev Chonoles Jul 31 '11 at 19:52
@Pete: This seems more complicated than necessary. The order of $x$ divides $2^{k+1}$, but does not divide $2^k$ (as $p$ is odd), so the order must be $2^{k+1}$. –  Geoff Robinson Jul 31 '11 at 21:13
@Geoff: upon reflection I agree with you: it suffices to show that the order does not divide $2^k$, but if it did the $2^k$th power would be $1$, not $-1$. Oh, well -- perhaps the general setup will be useful to someone in some other context. –  Pete L. Clark Jul 31 '11 at 22:18
So, in the shortest term, since $x^{2^m} \equiv -1(mod p)$, the order of x modulo p is $2^{m+1}$, hence $p \equiv 1 (mod 2^{m+1})$, as the order of x is a divisor of $p-1$. –  awllower Aug 5 '11 at 9:40

If $$p \mid (n^k+1),$$ $$n^k \equiv -1 \pmod{p}$$ $$n^{2k} \equiv 1 \pmod{p}$$ If$$\operatorname{ord}_pn=d,$$ then $d \mid 2k$. If $d \mid k$, then $$n^k\equiv 1 \pmod{p}$$ $\Rightarrow$ $$-1\equiv 1 \pmod{p}$$ $\Rightarrow p\mid 2$ which is impossible as $p$ is odd prime $\Rightarrow d\nmid k$.

If $(k,2)=1$ i.e., $k$ is odd, $d$ can divide $2$ $\Rightarrow$ $d=2$ as $d \nmid k \Rightarrow d \neq 1$. In that case,$$p \mid (n^2-1) \text{, or } p \mid (n+1) \text{ as } d\neq 1.$$ Then $d$ will be $2k$ if $d \neq 2$ i.e., iff $p \nmid (n+1)$.

If $k$ is $2^r$ where integer r ≥1, then $d \nmid 2$ as $d \nmid k$, then $d=2k$.

But $d \mid (p-1) \Rightarrow p≡1 \pmod{2k}$ if $k$ is of the form $2^r$ where integer r ≥1.

-
Why does d = 2k, in the 2nd last line: "If k is even i.e., (k,2)>1, then d∤2 as d∤k, then d=2k." –  confused Aug 18 '12 at 7:21
As d|2k and (d∤k & d∤2 as d∤k k being even). –  lab bhattacharjee Aug 18 '12 at 8:05
Counterexample provided by @cocopuffs. Let k = 6, d = 4. Then d∤k, d∤2, and d|2k. but d ≠ 2k. –  confused Aug 18 '12 at 8:10
Thanks for your observation, I have rectified my answer and am waiting for verification. –  lab bhattacharjee Aug 18 '12 at 10:28