Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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,

share|improve this question
2  
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
add comment

3 Answers

up vote 13 down vote accepted

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

share|improve this answer
1  
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
show 2 more comments

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.