Ed and I came up with this simple construction for fields of order p^2 yesterday. We thought we had one for fields of order p^n, but then we found out that we were using a theorem that only holds in characteristic 0. Anyway:
Suppose p=2. Let alpha be a root of x^2+x+1=0 in Z_2[x]. This polynomial is irreducible, as 0 and 1 do not satisfy it. Thus Z_2[alpha] is a field with four elements.
Now suppose p>2. Let k be a quadratic nonresidue modulo p. Then x^2-k is irreducible in Z_p[x], and let alpha be a root of x^2-k=0. Thus Z_p[alpha] is a field with p^2 elements.
(I had to break off the p=2 case because there are no quadratic nonresidues modulo 2.) The construction for p>2 seems a bit unfortunate, since quadratic reciprocity is a fairly powerful theorem, and I had wanted to use something less powerful to apply this construction. This construction doesn’t really seem to lend itself to constructions of fields of order p^n in general, but we can sometimes get higher ones.
If k_1, k_2, …, k_m are the quadratic nonresidues modulo p, then x^2-k_i is irreducible in Z_p[x] for each k_i. If alpha_i is a root of x^2k_i, then Z_p[alpha_1, alpha_2, …, alpha_m] will be a field with p^(2^m) elements.
I like this approach better than the normal way of doing things like Z_2[x]/(x^2+1) for a field of order 4, which seems very unnatural to me.