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

  • 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

16

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

  • 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
6

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
    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
    Thanks for your observation, I have rectified my answer and am waiting for verification.2012-08-18