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

1. Oct 29, 2011

### 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

2. Oct 29, 2011

### 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.

3. Oct 29, 2011

### Bachelier

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

4. Oct 29, 2011

### Bachelier

Should I use Fermat for this part?

5. Oct 29, 2011

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

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

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.

6. Oct 29, 2011

### Bachelier

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

7. Oct 29, 2011

### 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.

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?

8. Oct 29, 2011

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

9. Oct 29, 2011

### Bachelier

got it. thx

10. Oct 29, 2011

### Deveno

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

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

what other elements of <a> 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)$$ ?

11. Oct 30, 2011

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

12. Oct 30, 2011

### 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
xd-1 = 0, so that's all there is, and can't have less, since every element of (Zp)x has SOME order).

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

but....if (Zp)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 x2 + 1 = 0 (so x2+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 x2+ 1 = 0 has no solutions, so it is irreducible (no linear factors).

13. Nov 1, 2011

### Bachelier

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