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

Bachelier

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

Deveno

there are some "intermediate steps" you should prove first:

Z_p-{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.

Bachelier

let me try. the second part is a direct application of Lagrange.

Bachelier

Should I use Fermat for this part?

Deveno

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 gⁿ = e, what is the order of g^(n/k)?).

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

Fermat only shows that the order of the elements of (Z_p)^x divide p-1, you need to show that one of them actually HAS order p-1.

Bachelier

Well isn't like you said, a in Z_p)^* has order k is a^k [itex]\equiv[/itex] 1 (mod p)

so per Fermat, a^{[itex]\Phi (p)[/itex]} [itex]\equiv[/itex] 1 (mod p), hence for all a in
Z_p)^* a has order p-1 since [itex]\Phi (p)[/itex] = p-1

Deveno

no, we only know that for a ≠ 0 in Z_p, that a^p-1= 1 (mod p).

we don't know that some smaller number won't work, rather than p-1.

for example, consider (Z₁₃)^x.

clearly 3¹² = 1 (mod 13).

but 3³ = 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?

Bachelier

can we also say, let a in Zp*
consider <a> = { 1, a, a^2, ...}
since <a> belongs to Zp*, then order <a> divides p-1 the order of Zp*
hence |<a>|= p-1
hence for all a, |<a>|= Zp*

Bachelier

got it. thx

Deveno

to continue, suppose d|(p-1).

IF we have an element a in Z_p of order d, we can look at <a>.

what other elements of <a> have order d? a^k, where gcd(k,d) = 1.

that's φ(d) elements, right?

isn't it true that:

[tex]p-1 = \sum_{d|(p-1)} \phi(d)[/tex] ?

Bachelier

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?

Deveno

ok, so if we add up all the elements of order d, we get φ(d) of them (can't have more because if a is of order d, then all the elements of <a> are the d solutions to
x^d-1 = 0, so that's all there is, and can't have less, since every element of (Z_p)^x has SOME order).

so we actually have φ(p-1) generators of order p-1 (although we only needed 1 to show that (Z_p)^x is cyclic).

but....if (Z_p)^x is cyclic and p = 4k+1, then p-1 = 4k, we have a cyclic group of 4k, which means we have a subgroup of order 4 (since 4 divides 4k), which is cyclic, so we have an element of order 4.

and such an element of order 4 satisfies x² + 1 = 0 (so x²+1 is reducible, see?).

on the other hand, if p = 4k+3, then p-1 = 4k+2, and 4 does NOT divide 4k+2, our group is still cyclic, but cannot have a subgroup of order 4 (by Lagrange, finally we can use it), so cannot have an element of order 4, and thus x²+ 1 = 0 has no solutions, so it is irreducible (no linear factors).

Bachelier

Thank you Brother. I truly did learn a lot from your explanations.
:)