Motivation
A code can require an alphabet with eight or sixteen symbols while still needing division by every nonzero symbol. Integer arithmetic modulo eight or sixteen does not supply that property: nonzero elements can multiply to zero. A finite field provides a different arithmetic on the required number of symbols. Before using it as an evaluation alphabet, we should know which sizes are possible and why a field of the chosen size exists.
We will construct fields from polynomial residues, prove existence in every prime-power size, and identify the subfields used in extension-field parity checks. The proofs need polynomial division and elementary vector spaces. We recall the needed root-count fact: a nonzero degree- polynomial over a field has at most roots, because each root removes a linear factor and induction bounds the remainder.
Uniqueness here means uniqueness up to an isomorphism preserving addition and multiplication. It does not choose a polynomial basis or a canonical label for each symbol. An encoder and decoder still need an agreed representation; that agreement is different from the abstract field-size theorem.
Definitions
Definition 14.1.1
(Field and characteristic)
A field has distinct zero and one and allows inversion of every nonzero element. Its characteristic is the least positive integer with , when one exists. A finite field necessarily has positive characteristic. In characteristic , the multiples of one form a copy of .
Definition 14.1.2
(Polynomial quotient)
For a monic polynomial of degree , the quotient consists of polynomial residues. Every residue has a unique representative of degree less than , by division. The residue of is denoted by . At this point the quotient is a ring; it is a field only when is irreducible.
Definition 14.1.3
(Minimal polynomial)
For a finite-field element, its minimal polynomial over the prime field is the monic polynomial of least positive degree vanishing there. It is irreducible, since a factorization would make a smaller factor vanish in a field. Polynomial division shows it divides every other polynomial vanishing at that element.
Definition 14.1.4
(Frobenius polynomials, subfields and the Frobenius map)
For positive , write . Its derivative is minus one in characteristic , so it has no repeated irreducible factors. A subfield shares the larger field's zero and one and is closed under its operations. In a field of size , the map is the Frobenius map.
Theorem/proposition
Theorem 14.1.5
(Polynomial quotients and possible field sizes)
Every finite field has size for a prime and an integer . The quotient by a monic degree- polynomial over is a field exactly when the polynomial is irreducible; in that case its size is .
Theorem 14.1.6
(Existence, uniqueness and cyclic nonzero elements)
For every prime and every , a field of size exists and is unique up to isomorphism. The multiplicative group of every finite field is cyclic.
Theorem 14.1.7
(Frobenius and subfields)
On a field of size , Frobenius is an automorphism of exact order . For every positive divisor of , there is exactly one subfield with elements, namely the roots in of . There are no other subfield sizes.
Proof sketch or proof idea
Construct the arithmetic and restrict the possible sizes
Proof
(Prime characteristic and the irreducibility criterion)
If a finite field's characteristic were composite, say with , the nonzero elements would multiply to zero, contradicting the field property. Thus its characteristic is prime. Viewing the field as a finite-dimensional vector space over its prime subfield gives elements, one for each list of coefficients. A basis exists by repeatedly adjoining independent elements until the finite set is spanned.
If is irreducible, every nonzero representative of degree less than has gcd one with . The polynomial Euclidean algorithm gives , so the residue of is its inverse. Conversely if with both factors of positive degree less than , their residues are nonzero and multiply to zero. The quotient is therefore a field exactly in the irreducible case. The unique representatives give its cardinality .
A finite multiplicative subgroup has a generator
Proof
(Cyclic units and the exact period of Frobenius)
Let be the nonzero elements of a finite field. For each prime occurring in some element order, choose the largest power of that prime dividing such an order. Taking the appropriate power of a selected element gives an element with exactly that prime-power order. Multiplying these elements gives an element of order , the lcm of all element orders: the factors commute, and their orders are pairwise coprime. To check the order claim, raise the product to divided by one prime-power factor; all other components vanish, forcing that prime power to divide any exponent annihilating the product.
Every element of satisfies . The root-count bound gives , while an element of order already has distinct powers in . Hence and those powers are the entire group. This proof uses commutativity and a field root bound; it is not true that every finite group is cyclic.
It follows that every element of a size- field satisfies . Frobenius preserves addition by the characteristic- binomial identity, preserves multiplication, and is injective because a field has no nonzero element with . Finiteness makes it surjective. Its th power is the identity. If its th power were the identity for , all elements would be roots of the smaller-degree polynomial , impossible. Thus its order is exactly .
The root-count bound is the step that genuinely needs a field, as the following ring shows.
Counterexample mode
Finite commutative rings can have non-cyclic unit groups
Claim: the unit group of every finite commutative ring is cyclic. In the units are , and
Every unit has order at most two, so no unit has order four and the group is not cyclic. The proof above fails at one line: has the four roots modulo eight, more than its degree, because exhibits zero divisors. Here the lcm of the orders is , smaller than . The corrected statement is the one proved: a finite subgroup of the nonzero elements of a field is cyclic.
Count irreducibles to prove existence
Proof
(An irreducible of every degree)
Let be any monic irreducible of degree , and use the field quotient already constructed from it. Its element generates that field over . Therefore exactly when divides : if Frobenius fixes , it fixes every polynomial in , hence the whole field; reduce modulo its exact period . Polynomial division now shows
Factor into monic irreducibles over . This factorization exists by repeatedly factoring a reducible polynomial into lower degrees; the Euclidean algorithm supplies the usual uniqueness. Since has no repeated factors, it is exactly the product of all monic irreducibles with degrees dividing .
Let count monic irreducibles of degree . Comparing degrees gives , and in particular . For , every proper positive divisor is at most , so
The final inequality follows from the finite geometric sum: for , that sum is less than . Degree one is immediate from . Thus an irreducible of every positive degree exists, and its quotient constructs the desired field. We have not assumed an algebraically closed ambient field to obtain existence.
Proof X-ray
Where the counting argument uses each fact
Two facts carry the whole count. First, has derivative , so it has no repeated irreducible factor; this turns divisibility into an exact product and makes the degree identity an equality rather than an inequality. Second, the equivalence uses the exact Frobenius period on the field built from itself. That field has size with the degree of a polynomial already in hand, so nothing about size is assumed and the argument is not circular.
The non-obvious move is to bound the unknown divisor terms crudely by . Every proper divisor of is at most , so the subtracted terms form at most a geometric sum ending at , which is smaller than . Positivity of closes the argument: one irreducible of degree exists, and the quotient criterion already proved turns it into a field of size . Uniqueness is a separate step, proved next by splitting .
Identify fields and their subfields
Proof
(Uniqueness and the classification of subfields)
Let both have size . A multiplicative generator of generates the whole field, so its minimal polynomial over has degree and divides . The polynomial splits into its distinct roots in , because every element of is a root. Its factor that is the minimal polynomial of therefore has a root in . Evaluation sends to and gives an injective field map from the degree- quotient into . Equal finite sizes make this an isomorphism.
For , the irreducible-factor description shows . Thus has all its distinct roots in . Its root set is closed under addition, subtraction and multiplication by Frobenius identities, and under inversion for a nonzero root. It is a subfield of size .
Conversely any subfield has size , and a vector-space basis of over gives , so . Every element of is a root of . There are exactly such roots in , so they are all of , proving uniqueness for each possible size.
Concept lensStructural
Subfields as fixed points of powers of Frobenius
Every automorphism of is a power of . Take a multiplicative generator , with minimal polynomial of degree . An automorphism fixes , so is a root of . The elements are distinct roots, since a coincidence would make a smaller positive power of fix and hence . So and . The automorphisms form a cyclic group of order , and the subfield of size is the fixed set of : subfields match the subgroups .
Worked examples
Worked example 14.1.8
(Four symbols with field arithmetic)
Over , the polynomial has no root and is irreducible. Its quotient has symbols , with and . Thus . Squaring exchanges and and fixes zero and one, giving Frobenius order two. Integer arithmetic modulo four has the nonzero zero divisor two, so it cannot be substituted for this alphabet.
Worked example 14.1.9
(Count binary irreducibles of small degree)
There are two monic linear irreducibles, so . The degree identities give , hence , and , hence . At degree four the proper divisors are one and two, so and . These counts concern monic irreducibles, not the number of labeled field multiplication tables or the number of field elements.
Worked example 14.1.10
(A visible four-element subfield inside sixteen symbols)
Use . The modulus has no linear root and is not divisible by the only binary irreducible quadratic ; its remainder there is one. Thus it is irreducible. Put . From we obtain , so is a copy of the four-element field and equals the roots of in .
The possible subfield sizes are two, four and sixteen, corresponding to divisors one, two and four. In contrast, a field of size eight has only its two-element prime subfield and itself, because three has no proper divisor except one. A subset of four elements inside an eight-element field cannot be a subfield merely because its cardinality looks plausible.
Common mistakes
Common mistake
(A prime power is a size, not an integer modulus)
The symbols of a field of size are polynomial residues with coefficients in . Its characteristic is , not . Using integers modulo when introduces zero divisors and invalidates division, root bounds and decoding arguments that require a field.
Common mistake
(An irreducible modulus need not give a primitive element)
Generating the field as an algebra is different from generating its nonzero multiplicative group. In , the modulus is irreducible because minus one is not a square in . The element generates the entire field together with the prime field, but and , so its multiplicative order is four rather than eight. An irreducible degree- modulus therefore does not automatically make its residue variable a primitive multiplicative element. A BCH construction requiring an element of a specified order must check that additional property. The uniqueness proof above deliberately chose a multiplicative generator, whose existence had already been established, rather than assuming that every field generator has that order.
The same distinction between abstract classification and concrete labels appears with isomorphisms.
Common mistake
(Unique up to isomorphism is not a unique isomorphism)
An isomorphism need not be unique. In the four-element example, sending to or to gives two prime-field-preserving isomorphisms from the field to itself. Both preserve arithmetic. Choosing a concrete basis and bit representation fixes the convention used by an actual calculation, while the classification theorem only supplies the abstract possibility.
Summary
Finite fields have exactly prime-power sizes. Irreducible polynomial quotients construct them, a factor-counting argument proves existence at every degree, and the roots of a Frobenius polynomial prove uniqueness up to isomorphism. Frobenius periods and vector-space dimensions then determine every subfield. These results justify the alphabets and subfield checks used throughout the coding chapters.
Exercises
Quick check
(Why can the characteristic of a finite field not be zero?)
Consider the multiples of one.
Solution · Answer
In characteristic zero the multiples are all distinct, producing infinitely many elements. Finiteness forces a positive repetition and hence positive characteristic.
Quick check
(Why does a field with elements have exactly roots of ?)
Use the order of the multiplicative group and the degree of .
Solution
Every nonzero element has multiplicative order dividing the cyclic group's size , so it satisfies ; zero does too. There are elements and the polynomial has that degree with derivative minus one, so these are all its distinct roots.
Quick check
(List the possible subfield sizes of a field with elements.)
Write as a prime power and list the divisors of the exponent.
Solution · Answer
Here . Divisors one, two, three and six give sizes two, four, eight and sixty-four, exactly one subfield of each size. Neither sixteen nor thirty-two occurs as a subfield size.
Quick check
(Does the existence proof provide a fast algorithm for locating an irreducible polynomial of degree ? Explain the distinction.)
Ask what the positivity of does and does not tell an implementation.
Solution
No. Positive counting proves that some irreducible exists. An implementation still needs a search strategy and an irreducibility test, with a stated cost. The companion arithmetic unit proves a concrete test; this classification argument by itself supplies neither an optimized search nor a chosen representation.