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

**Problem statement**

Let n be a whole number of the form with , and p an odd prime that divides n.

Proof: .

**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?

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

Use Euler's criterion. is a quadratic residue is even

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! (Bow)

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

Sylvia, sorry, I don’t get your advice. What’s Euler’s criterion?

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

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

Quote:

Originally Posted by

**TDA120** Sylvia, sorry, I don’t get your advice. What’s Euler’s criterion?

Welcome to MHF, TDA120! :)

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

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 , if p is prime and is not a multiple of p.

The question becomes, what about , assuming p is odd?

That would be either -1 or +1.

And that is basically what Euler's criterion says.

The notation is just a fancy way of writing .

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|(x^{2}+1) is another way of saying that we have a square root of -1 in Z_{p}.

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

now, since p is prime U(Z_{p}) 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(Z_{p}) can have no element a of order 4, or else |<a>| = 4 would divide |U(Z_{p})| = 4n + 2, by Lagrange's theorem.

note that in Z_{p}[x], x^{4} - 1 = (x^{2} + 1)(x^{2} - 1). since 1 and -1 account for the roots of x^{2} - 1, we are left with the roots of x^{2} + 1. but if a^{2} = -1, then a is of order 4, and we have no such elements.

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/pZ^{x}?

When I thought about it (for a long while!), I realized that if p|x^{2}+1, that means that x^{2}=-1 mod p.

In turn that means that |x|=4 in Z/pZ^{x}.

Since |x| must divide the order of Z/pZ^{x} (Lagrange), it follows that 4|p-1.

Therefore p=1 mod 4.