# Math Help - Proof p=1 mod 4 if p|x^2+1

1. ## Proof p=1 mod 4 if p|x^2+1

Problem statement

Let n be a whole number of the form $n=x^2+1$ with $x \in Z$, and p an odd prime that divides n.
Proof: $p \equiv 1 \pmod 4$.

Attempt at a solution

The only relevant case is if p=3 (mod 4).

If I try to calculate mod 3, or mod 4, or mod p, I'm not getting anywhere.

Help?

2. ## Re: Proof of p=1 mod 4 if p|(x^2+1)

Use Euler's criterion. $p\mid x^2+1$ $\implies$ $-1$ is a quadratic residue $\mod p$ $\implies$ $1=\left(\frac{-1}p\right)=(-1)^{\frac{p-1}2}$ $\implies$ $\frac{p-1}2$ is even $\implies$ $p\equiv1\mod4.$

3. ## Re: Proof of p=1 mod 4 if p|(x^2+1)

Thanks!
I was not aware of Euler's criterion yet.
Now I am!

6. ## Re: Proof p=1 mod 4 if p|x^2+1

Originally Posted by TDA120
Welcome to MHF, TDA120!

@Sylvia: Not bad, a response time of 6 minutes!

7. ## Re: Proof p=1 mod 4 if p|x^2+1

Let me make an attempt to explain in a little more detail.
(Burn me down if I'm wrong.)

From Fermat's little theorem we know that $a^{p-1} \equiv 1 \pmod p$, if p is prime and is not a multiple of p.
The question becomes, what about $a^{p-1 \over 2}$, assuming p is odd?

That would be either -1 or +1.
And that is basically what Euler's criterion says.
The notation $\left({a \over p}\right)$ is just a fancy way of writing $a^{p-1 \over 2}$.

8. ## Re: Proof p=1 mod 4 if p|x^2+1

here is the way i look at it:

odd primes come in two flavors, 4n+3 and 4n+1 (since all odd numbers only come in these two flavors).

saying p|(x2+1) is another way of saying that we have a square root of -1 in Zp.

so if we can show that if p = 4n + 3 there is no such root, we are done.

now, since p is prime U(Zp) is a multiplicative group of order p - 1. if p = 4n + 3, then p - 1 = 4n + 2.

this is not divisible by 4, so in this case, U(Zp) can have no element a of order 4, or else |<a>| = 4 would divide |U(Zp)| = 4n + 2, by Lagrange's theorem.

note that in Zp[x], x4 - 1 = (x2 + 1)(x2 - 1). since 1 and -1 account for the roots of x2 - 1, we are left with the roots of x2 + 1. but if a2 = -1, then a is of order 4, and we have no such elements.

9. ## Re: Proof p=1 mod 4 if p|x^2+1

Thanks!

Actually, I recently got the hint: what is the order of x in Z/pZx?

When I thought about it (for a long while!), I realized that if p|x2+1, that means that x2=-1 mod p.
In turn that means that |x|=4 in Z/pZx.

Since |x| must divide the order of Z/pZx (Lagrange), it follows that 4|p-1.
Therefore p=1 mod 4.