## Zp[x]/(x^2 + 1) is a field iff p is a prime p ≠ 1 (mod 4)

I am stuck on this proof.

Zp[x]/(x^2 + 1) is a field iff p is a prime p = 3 (mod 4)

We're assuming p is odd, so p is either 4m + 1 or 4m + 3.

==>/ let Zp[x]/(x^2 + 1) be a field
I need to find that x^2 + 1 is reducible if p =4m+1

I can see it for Z5, Z13, Z17 for instance but I don't seem to be able to generalize it. Any advice.

<==/ if p = 3 (mod 4), we must show x^2 + 1 is irreducible over Zp

I assume otherwise, then x^2 + 1 = (x+a)(x+b)
gives me, ab ≡ 1 (mod p)
a+b≡ 0(mod p)

where should I go after this?

Thanks
 PhysOrg.com science news on PhysOrg.com >> Ants and carnivorous plants conspire for mutualistic feeding>> Forecast for Titan: Wild weather could be ahead>> Researchers stitch defects into the world's thinnest semiconductor
 Recognitions: Science Advisor there are some "intermediate steps" you should prove first: Zp-{0} is a cyclic group, under multiplication mod p. if k divides the order of a cyclic group G, then G has a subgroup of order k.

 Quote by Deveno there are some "intermediate steps" you should prove first: Zp-{0} is a cyclic group, under multiplication mod p. if k divides the order of a cyclic group G, then G has a subgroup of order k.
let me try. the second part is a direct application of Lagrange.

## Zp[x]/(x^2 + 1) is a field iff p is a prime p ≠ 1 (mod 4)

 Quote by Deveno Zp-{0} is a cyclic group, under multiplication mod p.
Should I use Fermat for this part?

Recognitions:
no, not really. it's a special case that ONLY holds for cyclic groups. Lagrange's theorem says this: if H is a subgroup of G, then |H| divides |G|. Lagrange's theorem does not guarantee that if k divides the order of G, G has a subgroup of order k. for example S5 is of order 120, and 30 divides 120, but S5 has no subgroups of order 30 (or of order 15, for that matter).

but this IS true, if G is cyclic (and you should PROVE this! it's bad mathematics to just take people's word for stuff. i could be lying, or i could just have "woke up stupid" today, and be giving you bad advice).

(a hint: if G = <g>, and |G| = n, and k divides n, so that gn = e, what is the order of g(n/k)?).

proving that (Zp)x is cyclic, is a bit trickier (but still important!).

 Quote by Bachelier Should I use Fermat for this part?
Fermat only shows that the order of the elements of (Zp)x divide p-1, you need to show that one of them actually HAS order p-1.

 Quote by Deveno Fermat only shows that the order of the elements of Zpx divide p-1, you need to show that one of them actually HAS order p-1.
Well isn't like you said, a in Zp)* has order k is ak $\equiv$ 1 (mod p)

so per Fermat, a$\Phi (p)$ $\equiv$ 1 (mod p), hence for all a in
Zp)* a has order p-1 since $\Phi (p)$ = p-1
 Recognitions: Science Advisor no, we only know that for a ≠ 0 in Zp, that ap-1= 1 (mod p). we don't know that some smaller number won't work, rather than p-1. for example, consider (Z13)x. clearly 312 = 1 (mod 13). but 33 = 1 (mod 13) so the order of 3 is NOT 12. i'll give you a push in the right direction: consider how many elements of order d, where d|(p-1) you must have. add these up, for every divisor d of p-1. how many elements is that?
 can we also say, let a in Zp* consider = { 1, a, a^2, ...} since belongs to Zp*, then order divides p-1 the order of Zp* hence ||= p-1 hence for all a, ||= Zp*

 Quote by Deveno no, we only know that for a ≠ 0 in Zp, that ap-1= 1 (mod p). we don't know that some smaller number won't work, rather than p-1. for example, consider (Z13)x. clearly 312 = 1 (mod 13). but 33 = 1 (mod 13) so the order of 3 is NOT 12.
got it. thx
 Recognitions: Science Advisor to continue, suppose d|(p-1). IF we have an element a in Zp of order d, we can look at . what other elements of have order d? ak, where gcd(k,d) = 1. that's φ(d) elements, right? isn't it true that: $$p-1 = \sum_{d|(p-1)} \phi(d)$$ ?

 Quote by Deveno to continue, suppose d|(p-1). IF we have an element a in Zp of order d, we can look at . what other elements of have order d? ak, where gcd(k,d) = 1. that's φ(d) elements, right? isn't it true that: $$p-1 = \sum_{d|(p-1)} \phi(d)$$ ?
I get it, but where are we going with this?

How do I prove that if p is congruent to 1 mod 4, that the field Z* mod p contains elements with order 4?
 Thank you Brother. I truly did learn a lot from your explanations. :)