A finite field is not merely arithmetic modulo a prime: fields of orders , , and exist as well. Their construction makes polynomial factorization concrete and supplies a family in which field symmetries can be written down explicitly.
Motivation and scope
Most first encounters with fields use the rationals, the reals, or the complex numbers. In those fields the integer is never zero for . Finite fields behave differently. Adding to itself repeatedly must eventually return to , and this single fact controls the whole theory: it forces the number of elements to be a prime power, it forces the identity , and it produces a canonical symmetry, the Frobenius map, that has no analogue in characteristic zero.
This unit has three aims. The first is to settle which finite fields exist and to show that, for each admissible order, there is exactly one up to isomorphism. The second is to describe the lattice of subfields of a finite field and its automorphism group, using Frobenius as the single generator. The third is to make these results computational: to build , and explicitly, to multiply and invert in them, to factor , and to count irreducible polynomials.
Throughout, denotes a prime, , and with . We use the following standard facts without reproving them: the tower law for degrees of field extensions; uniqueness of splitting fields up to isomorphism; Lagrange's theorem; the fact that a nonzero polynomial of degree over a field has at most roots in that field. The cyclicity of the multiplicative group of a finite field is proved below.
Characteristic and the Frobenius map
Let be a finite field. The elements cannot all be distinct, so some positive multiple of vanishes. The least such multiple is a prime, because if with smaller than the least multiple then in a field forces one factor to vanish. This prime is the characteristic of .
Definition 4.1.1
(Frobenius map)
Let be a field of prime characteristic . The Frobenius map of is , . For the power is .
The map is multiplicative because is commutative, and . Additivity is the content of the "freshman's dream". The binomial coefficient is divisible by for , because divides the numerator but not the denominator . Hence every middle term of vanishes and . Iterating gives . Since is a ring homomorphism from a field, its kernel is a proper ideal of a field and hence zero, so is injective. When is finite, injectivity implies bijectivity. Moreover fixes every element of the prime field , since for by Lagrange's theorem applied to (and trivially for ).
These observations are used implicitly in the proofs below, which state them in compressed form.
Counterexample mode
Frobenius need not be surjective on an infinite field
Claim: the Frobenius map of every field of characteristic is an automorphism. Take , rational functions in an indeterminate . If with nonzero polynomials , then . The left side has degree and the right side ; these differ modulo . So is not a th power, and is injective but not surjective. Repair: is an automorphism whenever is finite, by the injective-implies-bijective step.
The multiplicative group is cyclic
Lagrange's theorem says that every nonzero element of has order dividing . Much more is true: some element has order exactly . The proof uses only one property of fields, that a polynomial of degree has at most roots, so it applies to every finite group of nonzero elements of any field.
For a positive integer , let denote Euler's function, the number of integers with and . We write rather than so that Euler's function is not confused with the Frobenius map.
Theorem 4.1.2
(Finite multiplicative groups in a field are cyclic)
Let be a field and let be a finite subgroup of of order . For every positive divisor of , the group has exactly elements of order . In particular is cyclic. Consequently the multiplicative group of a finite field is cyclic with exactly generators, and for every generator .
Proof
(Proof)
We first record two facts about integers and cyclic groups.
(i) If an element of a group has order , then has order . Put . Then exactly when , that is, when divides ; since and are coprime, this happens exactly when . Hence among exactly elements have order .
(ii) . Write each of the fractions with in lowest terms as . Then , and . Conversely each such pair arises from exactly one , namely . Counting the pairs according to gives the identity.
Now let be the number of elements of of order . By Lagrange's theorem every element has order dividing , so . Suppose and let have order . The distinct elements are roots of , and this polynomial has at most roots in the field . Every element of of order is also a root of , so it is a power of , and (i) gives . Thus for every , and
forces for every . In particular , so contains an element of order and is cyclic.
For a finite field take and . If generates , every nonzero element is a power of , so .
The proof shows that generators exist and counts them, but it gives no formula for one. In practice one tests candidates. If , then has order exactly when for every prime dividing : if the order were a proper divisor of , some prime would divide , and then and .
Worked example 4.1.3
(Generators of )
Here , with prime divisors and . For we have and , both different from , so has order . The generators are the powers with , that is . Since , and , the generators are . There are of them, as the theorem predicts. By contrast is not a generator, because .
Counterexample mode
The field hypothesis cannot be dropped
Claim: every finite group of units in a ring with identity is cyclic. In the units form a group of order in which every element squares to , so no element has order . The proof breaks exactly at root counting: has four roots in , which is possible because there. Commutativity matters as well: in the quaternions the elements form a noncyclic group of order , and has infinitely many roots. Repair: in a field, and more generally in an integral domain, a polynomial of degree has at most roots, and the theorem applies.
Existence and structure
Theorem 4.1.4
(Existence and size)
Every finite field has elements for a prime and integer . Conversely, for each such pair there is a field with elements, unique up to isomorphism.
Proof
(Proof)
A finite field has positive prime characteristic and contains the prime field . As a finite-dimensional vector space over it, the field has elements. Conversely put and take a splitting field of over . Its derivative is , so it has distinct roots. In characteristic , ; products, negatives and nonzero inverses of roots are also roots. Both and are roots. The roots form a field of order . If is any field of order , its nonzero elements form a group of order , so Lagrange's theorem implies for all . Thus is a splitting field of the same polynomial. Uniqueness of splitting fields gives the asserted isomorphism.
Theorem 4.1.5
(Frobenius and subfields)
Let . The map is an automorphism of of order . For each positive divisor of , has exactly one subfield of order , namely the roots in of ; these are all its subfields. The automorphisms of fixing are exactly .
Proof
(Proof)
The binomial theorem in characteristic makes a homomorphism; it is injective and therefore bijective on finite . Its th power is the identity by the preceding theorem. No smaller positive power is the identity, since the polynomial has at most roots. If , the integer divides , so divides . The latter splits over into distinct linear factors, so the former has distinct roots in ; these fixed points of form a subfield. Conversely a subfield has order for some , and the tower law gives ; all its elements are roots of , fixing it uniquely. Finally the multiplicative group of a finite field is cyclic (by the cyclicity theorem above); a generator generates as a field over . Its minimal polynomial has degree , so at most images are possible for under an automorphism. The distinct Frobenius powers already provide all of them.
Proof X-ray
Where finiteness and cyclicity enter
Finiteness is used twice: an injective map of a finite set is bijective, and because every element is a root of . The order is exactly by root counting alone. The subfield statement needs only the divisibility . The real idea is the last step: if , an automorphism fixing is determined by the image of , and that image must be a root of the degree- minimal polynomial of . Cyclicity only supplies such a ; any element generating over would do.
An example
Worked example 4.1.6
(Arithmetic in the field of four elements)
The polynomial has no root in and is irreducible. Write with . Its elements are , and , . Frobenius exchanges and and fixes . This is a field, whereas is not: there.
Constructing fields from irreducible polynomials
The existence theorem builds as a splitting field, which is convenient for proofs but awkward for calculation. For computation one uses a quotient of a polynomial ring.
Theorem 4.1.7
(Quotient construction)
Let be monic of degree . Then is a ring with exactly elements, and it is a field if and only if is irreducible over . If , then is irreducible if and only if has no root in .
Proof
(Proof)
Division with remainder shows that every class has a unique representative of degree less than , i.e. a unique expression with , where is the class of . There are such expressions. If is irreducible, then since is a principal ideal domain the ideal is maximal, so the quotient is a field. If with of positive degree less than , then the classes of and are nonzero (their degrees are below ) but have product zero, so the quotient is not an integral domain. For the last assertion, a root gives the factor , so a polynomial with a root and degree at least is reducible. Conversely a reducible polynomial of degree or is a product of two factors of positive degree whose degrees sum to at most , so one factor has degree and hence yields a root.
The criterion "no root" fails from degree on, as the counterexample section below shows. For degrees and one must also exclude quadratic factors.
A remark on consistency: the quotient construction produces a field of order whenever an irreducible polynomial of degree exists, and the existence theorem together with cyclicity guarantees one. Indeed, if generates , then , so the minimal polynomial of over has degree and is irreducible. Thus irreducible polynomials of every degree exist over every , a statement with no analogue over fields like , where irreducibles have degree at most .
A field of eight elements
Worked example 4.1.8
(The field of eight elements)
The cubic has no root in : its values at and are and . By the quotient construction it is irreducible, and with . Computing successive powers:
, , , , , , , .
So has multiplicative order and generates ; the seven powers are the seven nonzero elements. To invert we use , and the check confirms it. The Frobenius orbit of is , which has size . These are distinct roots of : by construction, , and applying Frobenius to that identity gives . A cubic has at most three roots. The field has no subfield of order , since ; its only subfields are and itself.
The example illustrates a general principle: the Galois conjugates of a root of an irreducible polynomial over are obtained by repeatedly raising it to the th power. The next theorem makes this precise.
Theorem 4.1.9
(The roots of an irreducible polynomial over )
Let be monic irreducible of degree , and let be a root of in some extension field of . Then are distinct, , and
Consequently is a splitting field of , the roots of are distinct, and the degree of over equals the size of its orbit under .
Proof
(Proof)
The field has degree over , hence elements. By the theorem on Frobenius and subfields, applied to , the map is an automorphism of of order exactly ; in particular . Write with . Each power is a ring homomorphism fixing every , so . Thus every is a root of .
Suppose with . Applying gives with , and . The automorphism then fixes and , hence every polynomial expression in with coefficients in , which is all of . This contradicts the fact that has order on . Hence the elements with are distinct roots of the monic polynomial of degree , so they are all of its roots and is their product. They lie in and generate it, so is a splitting field of . The orbit of under is exactly this set of elements.
Two consequences are used repeatedly. Every irreducible polynomial over has distinct roots, which the normality unit proves by a derivative argument. And a field of characteristic containing one root of an irreducible contains all of them, since it is closed under ; so every finite extension of obtained by adjoining one root is already a splitting field.
Fixed fields of powers of Frobenius
The second structure theorem says the automorphism group is cyclic of order , generated by . We now identify the fixed field of each subgroup.
Theorem 4.1.10
(Fixed fields of Frobenius powers)
Let and let be an integer. The set of elements with is the unique subfield of of order , where .
Proof
(Proof)
For the set is closed under addition, and under negation because is a bijection of finite order. So is a subgroup of . Since , we have for every . If , then , so the subgroup contains , which means . Conversely, since , implies . Therefore the fixed set of equals the fixed set of , namely the set of roots in of . Because , the preceding structure theorem says this set is the unique subfield of order .
For instance, in the map has fixed field of order , while has and fixes only . In particular , which generates the full automorphism group, moves every element outside .
The same computation describes the automorphisms that fix a larger subfield than .
Theorem 4.1.11
(Automorphisms over an intermediate finite field)
Let , let be a positive divisor of , and let denote the subfield of of order . The automorphisms of fixing pointwise are exactly the powers of . They form a cyclic group of order , and .
Proof
(Proof)
Every automorphism of fixes and hence every element of , so by the theorem on Frobenius and subfields it equals for exactly one with . Put . By the preceding theorem the fixed set of is the subfield of order , so fixes pointwise exactly when . If this inclusion holds, the tower law for gives . Conversely, if , then contains a subfield of order ; it is a subfield of of order , hence equal to by uniqueness. So fixes if and only if , and since this means . The automorphisms in question are therefore for , which are the distinct powers of . Finally by the tower law.
Writing , the theorem says that the automorphisms of fixing form a cyclic group of order , generated by . The subfield of order thus plays the role that the prime field played above. For example, the automorphisms of fixing are , and those fixing are . In each case the number of automorphisms equals the degree; in the Galois correspondence unit this makes finite fields the first family of examples, with the subfield lattice matching the subgroup lattice of a cyclic group.
Factoring and counting irreducible polynomials
The roots of are all elements of , so the polynomial must factor over according to how the field is built from its subfields.
Theorem 4.1.12
(Factorization of )
Over , the polynomial is the product of all monic irreducible polynomials whose degree divides , each occurring exactly once. Consequently, if denotes the number of monic irreducible polynomials of degree over , then .
Proof
(Proof)
The polynomial has derivative , so and is squarefree: no irreducible factor is repeated. It remains to show that a monic irreducible of degree divides if and only if .
Suppose . Put , a field of order , and let be the class of . By Lagrange's theorem , and iterating times gives . So is a root of . Since is irreducible and , is the minimal polynomial of , hence .
Suppose . Let , which contains all roots of . Then has a root , and is a subfield of degree over , hence of order . The subfield theorem gives .
Since is monic and squarefree and its irreducible factors are precisely the monic irreducibles of degree dividing , comparing degrees gives .
Worked example 4.1.13
(Factoring over and counting quartics)
Take , . The divisors of are and . The irreducibles of degree are and , so . The count formula gives , hence , and the two irreducible cubics are and (each has no root in ; checking the other monic cubics with constant term gives and ). Thus
To confirm, multiply the two cubics:
using modulo . Multiplying by gives , which equals in characteristic , and multiplying by gives .
Now take . The divisors are with , (namely ). Then , so . The three irreducible quartics are , , and . For the divisors are and , so .
The count has a pleasant interpretation. In there are elements outside the subfield , and each of the three irreducible quartics contributes exactly four of them as roots, giving . The elements of are sorted into Frobenius orbits, and an orbit of size corresponds to an irreducible polynomial of degree .
The counting identity determines every recursively. Two consequences can be read off without solving the recursion.
Proposition 4.1.14
(Prime degrees and a lower bound)
(a) If is prime, then . In particular divides .
(b) For every ,
In particular, irreducible polynomials of every degree exist over .
Proof
(Proof)
The monic irreducibles of degree are the polynomials , so . For (a), the divisors of are and , so the counting formula reads .
For (b), applying the counting formula to any and keeping only the term for itself gives ; with this is the upper bound. Every proper divisor of satisfies , so
For the last sum is empty. For put , so that , and
Part (b) proves the existence of irreducible polynomials of every degree without using the cyclicity of the multiplicative group, and it shows that roughly a fraction of the monic polynomials of degree are irreducible. Part (a) recovers the congruence , a case of Fermat's little theorem, from field theory alone.
The explorer below sorts , , , or into Frobenius orbits, shows the fixed set of against , and checks that each orbit's polynomial is irreducible of degree equal to the orbit size and that the sizes add up to .
Arithmetic in the field of nine elements
Odd characteristic behaves the same way, with one new feature: a quadratic may be irreducible because its constant term fails to be a square.
Worked example 4.1.15
(The field )
The squares in are and . Since is not a square, has no root and is irreducible over . Write with ; its nine elements are with . Frobenius is , since , and . So Frobenius acts as conjugation, and its fixed field is , as predicted.
The product of an element with its Frobenius image is . Thus has inverse . For we get , and in , so . The check succeeds.
To see that generates the cyclic group of order , compute , then . So while , and the order divides but not , so it equals .
Counterexamples and warnings
Common mistake
(Size does not determine an integer residue ring)
The notation denotes a field, not generally . For that residue ring has nonzero zero divisors. Also, a field of order has a subfield of order only when divides , not merely when .
Common mistake
(Absence of roots does not imply irreducibility in degree four)
Over the polynomial has no root, since its values at and are and . Yet in characteristic , so it is reducible. Consequently is not a field: the class of is nonzero, but its square is zero. The root test is valid only in degrees and .
Common mistake
(Unions and compositums of subfields)
The fields and both sit inside , but their union has elements, which is not a prime power, so it is not a field. The smallest subfield containing both is itself, of order . Likewise has order . Subfields of a finite field are closed under intersection but not under set-theoretic union.
A further warning concerns repeated factors. The ring has four elements, but over , so the class is a nonzero nilpotent element and the ring is not a field. A finite commutative ring with identity is a field if and only if it has no nonzero zero divisors; cardinality alone does not establish that property.
Concept lensStructural
Frobenius orbits and minimal polynomials
For an element of a finite field, repeatedly raising it to the characteristic moves among roots of its minimal polynomial. The first return to the element measures its orbit; in this setting that orbit length equals the degree of the minimal polynomial. Thus the same number has a dynamical meaning as well as a field-extension meaning.
No finite field is algebraically closed
Over every nonconstant polynomial has a root. No finite field has this property, and the reason is elementary.
Proposition 4.1.16
(Finite fields are not algebraically closed)
Let be a finite field. The polynomial has no root in . Hence no finite field is algebraically closed, and every algebraic closure of is infinite.
Proof
(Proof)
The polynomial has degree , so it is nonconstant. For the product contains the factor , so the polynomial takes the value at . An algebraic closure of is algebraically closed, so by what was just shown it cannot be finite.
For the polynomial is , the irreducible quadratic used to build .
Practice and solutions
Quick check
(List the possible subfield orders of .)
Solution · Answer
Since , the divisors give orders .
Quick check
(In above, calculate and the orbit of under Frobenius.)
Solution · Answer
Since , the inverse is . Frobenius sends to and then back to , giving the orbit .
Quick check
(In with , compute and express it as a power of .)
Solution · Answer
Expand directly: . This agrees with the power table, since and , so the product is using .
Quick check
(Find the number of monic irreducible quadratics over and list them.)
Solution · Answer
By the counting formula with , : and , so . A monic quadratic over is irreducible if and only if it has no root. Checking values at : takes ; takes (at : ); takes (at : ). None vanishes, so these three are irreducible, and by the count they are all of them.
Quick check
(Let . Describe the fixed field of and state how many elements of generate over .)
Solution · Answer
The fixed field of has order , so it is . An element generates over exactly when it lies in no proper subfield. The proper subfields of are and , and , so the generators are the elements outside . This agrees with the three irreducible quartics, each having four roots.
Quick check
(Let be a finite field. Compute the sum of all its elements and the product of its nonzero elements.)
Solution · Answer
The elements of are the roots of . If , the coefficient of is , so the sum of the roots is . If the sum is . The nonzero elements are the roots of , whose constant term is , so their product is . For odd this is . For even the characteristic is , where . In every case the product is . For this recovers , i.e. Wilson's theorem.
Quick check
(Prove that is a field with elements, and decide whether the class is a generator of its multiplicative group.)
Solution · Answer
The polynomial has no root in (values and ). It remains to exclude a quadratic factor. The only irreducible monic quadratic over is , and . Any factorization into two quadratics would be this square (a product of two irreducible quadratics, as both factors must be irreducible, hence equal to ), so none exists. Hence is irreducible, and the quotient is a field with elements. Let be the class of , so . The order of divides . Compute because has degree as a representative; and . The order divides ; since it is neither nor , and since it is not . Therefore it is . Hence generates .
Quick check
(How many generators does have? Find one and list them all.)
Solution · Answer
The group has order , so there are generators. The primes dividing are and , so an element is a generator exactly when and . For : and , so is a generator. The generators are with : , , and since . They are .
Quick check
(Let with . Prove that is irreducible over .)
Solution · Answer
Let be a root in some extension field. Then . Since fixes , induction gives for all . The elements with are distinct, because with forces ; and . So the orbit of under has exactly elements. By the theorem on roots of irreducible polynomials, the minimal polynomial of over has degree equal to this orbit size, namely . It divides , which is monic of the same degree, so the two are equal and is irreducible. For and this is .
Quick check
(Use the proposition on prime degrees to find and , and check against the counting formula.)
Solution · Answer
and . For the check, the divisors of give .
Quick check
(Which automorphisms of fix both and ? Explain the answer in terms of the field these two subfields generate.)
Solution · Answer
By the theorem on automorphisms over an intermediate field, with fixes exactly when , and fixes exactly when . Both conditions hold only for , so only the identity fixes both. This agrees with the fact that an automorphism fixing and fixes the smallest subfield containing both, which is itself.