12
$\begingroup$

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,

  • 2
    What happens with your last statement if $p=5$? Does $p\equiv 1 \pmod{4}$ imply $p\equiv 1 \pmod{8}$?2011-04-17
  • 0
    @M.B: Thank you. I got it.2011-04-17
  • 0
    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.2011-08-05

3 Answers 3

14

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

  • 1
    Thanks a lot. I was so close to the answer.2011-04-17
  • 0
    @lhf could you please explain how we arrive at: p≡1mod42012-08-18
  • 0
    @confused, the OP did that.2012-08-18
  • 0
    @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?2012-08-18
  • 0
    @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.2012-08-18
  • 0
    Doesn't n^2 have order 4? since the term (n^2)^2 must be squared again to become congruent to 1 (mod p)?2012-08-18
  • 0
    @confused, you're right. From $n^4 \equiv -1 \bmod p$ we can conclude that $n$ has order 8 and so $8$ divides $p-1$.2012-08-20
5

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

  • 0
    I suspect that tags are ranked by the number of questions that use them; [group-theory has 620](http://math.stackexchange.com/questions/tagged/group-theory), while [elementary-number-theory has 310](http://math.stackexchange.com/questions/tagged/elementary-number-theory). (EDIT: Confirmed [here](http://blog.stackoverflow.com/2011/08/improved-tagging/))2011-07-31
  • 0
    @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}$.2011-07-31
  • 0
    @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.2011-07-31
  • 0
    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$.2011-08-05
0

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.

  • 0
    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."2012-08-18
  • 0
    As d|2k and (d∤k & d∤2 as d∤k k being even).2012-08-18
  • 0
    Counterexample provided by @cocopuffs. Let k = 6, d = 4. Then d∤k, d∤2, and d|2k. but d ≠ 2k.2012-08-18
  • 0
    Thanks for your observation, I have rectified my answer and am waiting for verification.2012-08-18