*: GxG >
G
("multiplication"); a neutral element ("unit")
e
and an inverse i(x)=x^{1}
for
each element x
in G
. The rules are:
x*(y*z)=(x*y)*z
;i(x)*x = x*i(x) = e
;x*e = e*x = x
.The group is called abelian if the operation is commutative:
x*y = y*x
Subgroup is a subset containing e
and
closed under *
and i
.
Examples:
(Z, +, 0)
;(Q\{0}, *, 1)
;S_{n}
 the group of permutations of
n
elements; operation: composition; unit: identity
map.A ring is (R,+,0,*,1)
such that (R,+,0)
is an abelian group and (R\{0},1,*)
is a commutative
"semigroup", i.e., a "group without inverse". An additional condition
is distributivity:
x*(y+z) = x*y + x*z
.
Subring is a subset containing 1 and 0 and closed under
+,,*
.
Examples:
(Z,+,*)
;R[x]
;n
 Z/nZ
:
{0,1,...,n1}
with operations x+y := x+y mod
n
; x*y := x*y mod n
etc.Exercise: Prove that Z/nZ
is a ring.
A field (K,+,0,*,1)
is a ring such that
(K\{0},*,1)
is a group (called multiplicative group of a
field and denoted K^{*}
); i.e., every nonzero
element has a multiplicative inverse. Subfield is a subset containig
0 and 1 and closed under +,,*,/
.
Examples:
(Q,+,0,*,1)
;(R,+,0,*,1)
;R(x)
;p
: Z/pZ =
F_{p}
.Exercise: Prove that Z/pZ
is indeed a
field. Why Z/nZ
for a nonprime n
is not a
field?
Problem:
Q
is the idenity map.R
is the idenity map.#
.x
of a group G
: the
smallest integer number n
such that
x^{n}=1
. It is also equal to the order of the
subgroup generated by the element. The order of an element divides
the order of the group (if both are finite), since the following is
true for any subgroup H
: #G = #H * #(G/H)
(Prove it).Q
(rationals) and
F_{p} = Z/pZ
(for prime p
).Q
and p
if its simple subfield is
F_{p}
. Denoted: char
.
3. Prove that if char K = p
then for any
 the sum x
 element of K( x +
... + x ) (p items)
is 0.
p
: 1+1+...+1=0
(p
1's). Prove that p
is prime.K
. It contains 0 and 1.
Consider the sequence a_{n}
,
s.t. a_{0}=0; a_{1}=1;
a_{2}=1+1;
and, in general,
a_{n+1}=a_{n}+1
. (Sloppily we could
write it as a_{n}=n*1
; remember, the integer
number n
is not an element of K
). Either
all elements in this sequence are different, and then the subring
{a_{n}; a_{n}}
is isomorphic to
Z
(then K
contains a subfiels isomorphic
to Q
and its characteristic is 0), or there exists a
smallest k
such that a_{p}=0
.
Then {a_{l}  l=1..p}
is isomorphic to
Z/pZ
. If p=nm
is not a prime, we have
a_{n}*a_{m}=0
and K
is
not a field. Therefore any field contains a subfield isomorphic to
Q
or F_{p}
, i.e., up to
isomorphism, there are the only prime fields.p
units is 0  by the definition of the
characteristic: 1 lies in the simple subfield
F_{p}
.F_{p}
is infinite, but its characteristic is
finite and equal to p
.
F_{q}
;
#F_{q}=q
. Let char
F_{q}=p
. Prove that q=p^{k}
for
some integer k
.
F_{q}
as a vector space over its
subfield F_{p}
(i.e. F_{p}
is the field of scalars). Let its dimension be k
. (Why
is the dimension finite?) What is known about the structure of a
finite dimensional vector space? (Coordinates, basis...)
F_{p}
(its simple
subfield), F_{q}
(a finite
q
element field) is finitedimensional (since it's
finite), and thus isomorphic as a vector space to
(F_{p})^{k}
, with k=dim
F_{q}
. Thus q = #F_{q} =
p^{k}
.Consider a finite field F_{q}; char F_{q}=p;
q=p^{k}
; and let F: F_{q} >
F_{q}
be the following transformation:
F(x)=x^{p}
.
F
is a "field automorphism", i.e.,
F(xy)=F(x)F(y); F(x/y)=F(x)/F(y)
.
p

prime, k=1,...,p1
; p
divides
C(p,k)
(the binomial coefficient).
The statement F(x/y)=F(x)/F(y)
follows from the
usual properties of powers. Next,
(xy)^{p}=x^{p} + (y)^{p} +
Sum_{1}^{p1} C(p,k)x^{k}
y^{pk}
.
p
divides C(p,k)
for
k=1..p1
and prime p
, since we know that
C(p,k)=p!/k!(pk)!
, and p
divides the
numerator but does not divide the denominator. Thus the "Sum" term
is 0 and F(xy)=x^{p} + (y)^{p}
. If
p=2
then A+A=0
and A=A
thus
F(xy)=x^{2} + y^{2} = x^{2} 
y^{2}
. If p
is odd then
(y)^{p} = y^{p}
.
F(x+y)=F(x)+F(y);
F(xy)=F(x)F(y); F(x)=F(x); F(x^{1})=F(x)^{1};
F(1)=1; F(0)=0
. Prove it! You might think about which set of
conditions other than the one from the problem above will gurantee
that the map is an automorophism.
F(x)=x
iff (if and only if) x
lies in the simple subfield F_{p}
.
X^{p}X
and its roots.
X
in F_{p}
,
x^{p}=x
(see below). Since
X^{p}X
cannot have more than p
roots in F_{q}
(and all p
elements
of F_{p}
are its roots), no element of
F_{q}\F_{p}
can be a root.x
of field
F_{q}
we have x^{q}=x
;
i.e., P_{q}(x)=0
.t^{q1}=1
and for any l<q1;
t^{l} != 1
. This means that the multiplicative group
F_{q}^{*}
of the field
F_{q}
is isomorphic to Z/(q1)Z
(is "cyclic": each nonzero element of the field is some power of
the element t
, which is called "generator").F_{q}^{*} = F_{q} \ {0}
with the operation of multiplication. Take an arbitrary element and
multiply it by itself several times. You cannot always get a
different element, can you? This treats the first part, since the
order of an element must divide the order of the group
q1
.o(x)
to be the order of x
, i.e., the
smallest number l
such that
x^{l}=1
. Let o = max {o(x)  x in
F_{q}}
. Prove that for any x
we have
that o(x)
divides o
, i.e.,
x^{o}=1
. (This is true since
o(xy)<=lcm(o(x),o(y))
; lcm = Least Common Multiple).
Then if o<q1
, one must have a polynomial
P(x)=x^{o}1
with more than o
roots (namely, q1
).
Is it possible in a field? Why?Consider the polynomial
P(x)=P_{q}(x)/P_{p}(x)
(why is it a
polynomial?)
F_{p}
.
P(x)
is the product of all irreducible polynomials of
degree k
over F_{p}
. (recall that
q=p^{k}
).
z
in F_{q}\F_{p}
.
Let z_{0}=z
; and
z_{l+1}=F(z_{l})
(the Frobenius
automorphism), i.e.,
z_{l}=z^{pl}
; thus
z_{k}=z=z_{1}
. Therefore the polynomial
P_{z}(x)=
(xz_{0})(xz_{1})...(xz_{k1})
is
invariant under the Frobenius automorphism, thus its coefficients lie
in F_{p}
. These polynomials are irreducible
over F_{p}
. (Why? Apply the Frobenius
automorphism to its alleged irreducible factor. It cannot change
because of its coefficients  they lie in F_{p}
and thus are invariant under the Frobenius automorphism  and it has
to change because of its roots  they are not the whole set {z,
F(z)=z^{p}, F(F(z))=z^{p2}, ...,
F(F(...(F(z))...)) = z^{pk1}}
and thus
must change under the Frobenius automorphism). Any other irreducible
polynomial of degree k
has to be one of these. (It
cannot have roots in F_{p}
 then it's reducible
 so it has roots in the algebraic closure of
F_{p}
, but with a root z
it has to
have F(z), F(F(z)), F(F(F(z)))
etc. as roots, and it
cannot have more than k
roots, so
z^{p}^{k}=z^{q}=z
 and thus
z
lies in F_{q}
.)f: F_{q} >
F_{q}
there exist the unique polynomial
P_{f}
of degree no more than q1
such that for any x
in F_{q}
we
have P_{f}(x)=f(x)
. How many such functions are
there?
Aut(F_{q})
:F_{q}
. The operation is the composition, the
unit is the identity map, the inverse is the inverse map.
Aut(F_{q})
.
Aut(F_{q})
is isomorphic to
Z/kZ
, where q=p^{k}
; and the
generator of Aut(F_{q})
is the Frobenius
automorphism F
.
F
as an element of
Aut(F_{q})
is k
. Then prove that
there are only k
elements in this group.
Suppose the order of F
is l<k
. Then
F^{l} = id
and for each element x
of
the field F_{q}
we have
x^{pl} = x
, i.e., any element of the
field F_{q}
is a root of the polynomial
x^{pl}x
of degree
p^{l}<p^{k}=q
which is
impossible. Therefore for i=1,...,k1
we have
F^{i} != id
and
F^{0}=F^{k}=id
(since
F^{k}(x)=x^{q}=x
). This also implies that
the set {F^{l}  l=0,1,...,k1}
is a subgroup of
Aut(F_{q})
isomorphic to Z/kZ
.
Next, consider the generator t
of the field
F_{q}
. Recall that for each nonzero element
x
of the field F_{q}
there is a
unique number 0<=l<=q1
such that
x=t^{l}
. Suppose we have an automorphism
w
of the field F_{q}
and its value
on the generator t
is w(t)=t^{a}
for
some 0<=a<=q1
. Then w(x) = w(t^{l})
= w(t)^{l} = {t^{a}}^{l} = t^{al} =
{t^{l}}^{a} = x^{a}
. Thus the
automorphism w
is determined by the image of the
generator and furthemore, it can be represented in the form x
> x^{a}
. Now the only thing left to be proven is
that a
must be a power of p
.
Here we again use the Newton's binomial. Since w
is
an automorphism, we have the following identity for all x
from the field F_{q}
: w(x+1) = w(x) + w(1)
= w(x) + 1
. Therefore we have (x + 1)^{a} =
x^{a} + 1
or that the polynomial (x +
1)^{a}  x^{a}  1
is identical to 0. Since its
degree is less than q
, the coefficients must be 0, and
the coefficients are the binomial coefficients C(a,l)
for
l=1,...,a1
. They are 0 in the field
F_{q}
if and only if p
divides each
of them. Suppose that
a=p^{m}+b<p^{m+1}
. Careful
consideration of C(a,b)
shows that it is not divisible by
p
unless b=0
. The reader is encouraged to
actually perform the "careful consideration".
Sam Steingold<sds@gnu.org>  created: 19950101 