# Legendre Symbol Problem

I am doing revision for my number theory exam and I am stuck on the following question.

Let $x$ be an even integer. Show that every prime divisor $p$ of $x^4 + 1$ satisfies $\big(\frac{-1}{p}\big)$ = $\big(\frac{2}{p}\big) = 1$ where $\big(\frac{a}{p}\big)$ denotes the Legendre Symbol. Deduce that there are infinitely many primes $p \equiv 1 \pmod{8}$.

Hint: Observe that $x^4 + 1 = (x^2 + 1)^2 - 2x^2$

So as $x$ is even this means $x^4 + 1$ is odd, hence $p$ has to be an odd prime. Don't know where to go from here. How does the hint help?

Any advice would be very much appreciated!

-
One can give a more group theory flavoured solution without the hint. Let $p$ be an odd prime, and suppose that $x^4 \equiv -1 \pmod p$. Then $x$ has order $8$ modulo $p$, and therefore $8$ divides $p-1$. –  André Nicolas Mar 19 '12 at 21:26

If $p$ divides $x^4+1$, then it divides $(x^2+1)^2 - 2x^2$, hence $(x^2+1)^2\equiv 2x^2\pmod{p}$. Can you conclude from this that $\left(\frac{2}{p}\right)=1$?

And if $p$ divides $x^4+1$, then $x^4\equiv -1\pmod{p}$; can you conclude that $\left(\frac{-1}{p}\right) = 1$?

Since $\left(\frac{2}{p}\right) = 1$ if and only if $p\equiv \pm 1\pmod{8}$, and $\left(\frac{-1}{p}\right)=1$ if and only if $p\equiv 1\pmod{4}$, can you see why this forces $p\equiv 1\pmod{8}$? And why you can now conclude that there are infinitely many such primes?

-
I don't want to spoil it for the OP, but I'm curious how to finally conclude the infinitude of primes $p$ such that $p\equiv 1\pmod{8}$. If there were only finitely many, then all numbers of form $(2k)^4+1$ would have only finitely many distinct prime factors. Is there an obvious impossibility here? –  Nastassja Mar 19 '12 at 21:42
@Nastassja: Do you remember how one proves that any finite list of primes is not the full list of primes? Can you do something similar here? –  Arturo Magidin Mar 19 '12 at 21:44
Thank you very much! That all makes perfect sense but I am still not sure why we can conclude there are infinitely many such primes? –  Alex Kite Mar 19 '12 at 21:46
@AlexKite: Let me repeat what I just told Natassja: Do you remember how one proves that given a finite list of primes, there must be some prime not on the list? Suppose you are given finitely many primes that are congruent to $1$ modulo $8$. Can you construct some $x$ such that none of the primes in your list divides $x^4+1$? –  Arturo Magidin Mar 19 '12 at 21:48
@Alex Kite: Do you remember about $n!$? –  André Nicolas Mar 19 '12 at 21:50

This does not use the hint, so does not answer your question. But as part compensation, we prove a stronger result. Let $p$ be an odd prime that divides $x^{2^n}+1$. Then $x^{2^n}\equiv -1 \pmod{p}$. It follows that $x^{2^{n+1}}\equiv 1\pmod p$, and therefore the order of $x$ modulo $p$ divides $2^{n+1}$. But since $x^{2^n}\not\equiv 1\pmod{p}$, the order of $x$ is not $\le 2^n$. So the order of $x$ is exactly $2^{n+1}$, and therefore $2^{n+1}$ divides $p-1$, that is, $p\equiv 1 \pmod{2^{n+1}}$.

Now let $k$ be a large positive integer, let $K=(k!)^{2^n}+1$, and let $p$ a (necessarily odd) prime divisor of $K$. It is clear that $p>k$. By the result above, $p \equiv 1\pmod{2^{n+1}}$. Thus $p$ is prime $>k$ which is congruent to $1$ modulo $2^{n+1}$. So for every positive integer $n$, there are arbitrarily large primes congruent to $1$ modulo $2^{n+1}$.

-

Alternate proof that if an odd prime $p|n^4+1$ for some $n\in\mathbf{Z}$, then $p\equiv 1\pmod{8}$. We have $n^4\equiv -1\pmod{p}\implies n^8\equiv 1\pmod{p}$, so $\text{ord}_p(n)|8$. Note that $\text{ord}_p(n)\nleq 4$, so $\text{ord}_p(n)=8$. Additionally, by FLT $n^{p-1}\equiv 1\pmod{p}$, so $\text{ord}_p(n)|n-1\implies 8|p-1$, as desired.

This directly implies that $2$ is a quadratic residue in $\mathbf{Z}/p\mathbf{Z}$, so $\left(\frac{2}{p}\right)=1$.

-