16
$\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,

$\endgroup$
3
  • 2
    $\begingroup$ What happens with your last statement if $p=5$? Does $p\equiv 1 \pmod{4}$ imply $p\equiv 1 \pmod{8}$? $\endgroup$
    – M.B.
    Apr 17, 2011 at 1:16
  • $\begingroup$ @M.B: Thank you. I got it. $\endgroup$
    – roxrook
    Apr 17, 2011 at 1:26
  • $\begingroup$ 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. $\endgroup$
    – awllower
    Aug 5, 2011 at 10:10

3 Answers 3

17
$\begingroup$

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

$\endgroup$
7
  • 1
    $\begingroup$ Thanks a lot. I was so close to the answer. $\endgroup$
    – roxrook
    Apr 17, 2011 at 3:54
  • $\begingroup$ @lhf could you please explain how we arrive at: p≡1mod4 $\endgroup$
    – confused
    Aug 18, 2012 at 9:17
  • $\begingroup$ @confused, the OP did that. $\endgroup$
    – lhf
    Aug 18, 2012 at 11:02
  • $\begingroup$ @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? $\endgroup$
    – confused
    Aug 18, 2012 at 11:38
  • 1
    $\begingroup$ Doesn't n^2 have order 4? since the term (n^2)^2 must be squared again to become congruent to 1 (mod p)? $\endgroup$
    – confused
    Aug 18, 2012 at 22:10
6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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) $\endgroup$ Jul 31, 2011 at 19:52
  • $\begingroup$ @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}$. $\endgroup$ Jul 31, 2011 at 21:13
  • $\begingroup$ @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. $\endgroup$ Jul 31, 2011 at 22:18
  • $\begingroup$ 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$. $\endgroup$
    – awllower
    Aug 5, 2011 at 9:40
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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." $\endgroup$
    – confused
    Aug 18, 2012 at 7:21
  • $\begingroup$ As d|2k and (d∤k & d∤2 as d∤k k being even). $\endgroup$ Aug 18, 2012 at 8:05
  • $\begingroup$ Counterexample provided by @cocopuffs. Let k = 6, d = 4. Then d∤k, d∤2, and d|2k. but d ≠ 2k. $\endgroup$
    – confused
    Aug 18, 2012 at 8:10
  • $\begingroup$ Thanks for your observation, I have rectified my answer and am waiting for verification. $\endgroup$ Aug 18, 2012 at 10:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .