Back to the on-screen lesson ·
Quotienting the polynomials over a prime field by an irreducible polynomial builds a field of prime-power size — the only sizes there are, with exactly one field of each.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to build a finite field as a quotient by an irreducible polynomial, count its elements as a prime raised to the degree, compute in it by reducing coefficients and then reducing modulo the polynomial, say why every finite field has prime-power size and why there is exactly one of each, distinguish it from the residues of the same size, and prove that the quotient by an irreducible polynomial is a field.
Quotients came from unit 4, ideals and maximality from unit 5, and irreducible polynomials from the last two lessons. This lesson puts them together in a single construction, and what comes out is a complete classification: exactly one finite field of each prime-power size, and none of any other size.
A finite field is a field with finitely many elements. Its characteristic is the prime $p$ such that $p$ copies of $1$ sum to $0$. A field with $q$ elements is often written $\mathbb{F}_q$ or $GF(q)$, the Galois field of order $q$. A primitive element is a generator of the cyclic group of non-zero elements.
Take $\mathbb{Z}_p$ for a prime $p$, and an irreducible $f \in \mathbb{Z}_p[x]$ of degree $n$. Then
$$\mathbb{Z}_p[x]/(f)$$
is a field with $p^{n}$ elements.
Why it is a field. $f$ is irreducible, so $(f)$ is a maximal ideal — the same argument as for a prime number in $\mathbb{Z}$, using the division algorithm — and a quotient by a maximal ideal is a field. Directly: for $g$ not divisible by $f$, coprimality gives $gu + fv = 1$ by Bézout, and reading that modulo $f$ makes $u$ the inverse of $g$.
Why it has $p^{n}$ elements. The elements are the remainders on dividing by $f$: polynomials of degree below $n$. There are $n$ coefficients, each free to be any of $p$ values, so $p^{n}$ in all.
How to compute in it. Multiply as polynomials, then reduce using the relation $f = 0$. In $\mathbb{Z}_2[x]/(x^{2} + x + 1)$, writing $\alpha$ for the class of $x$, the relation is $\alpha^{2} = \alpha + 1$, and the four elements are $0, 1, \alpha, \alpha + 1$.
Three theorems complete the picture, and only the first is proved here.
And the negative statement matters as much: there is no field with six elements, or ten, or twelve. Six is not a prime power, and the construction cannot be pushed to produce one.
Most of the theorems in this course are counting arguments wearing algebraic clothes. Cosets all have the same size, so a subgroup's order divides the group's; the remainders below a degree are a finite list, so a quotient by an irreducible polynomial is a finite field.
Another way: picture
Compare the two constructions side by side. To build $\mathbb{Z}_p$ you take the integers and declare a prime to be zero; what survives is the remainders, and there are $p$ of them. To build $\mathbb{F}_{p^n}$ you take the polynomials over $\mathbb{Z}_p$ and declare an irreducible polynomial to be zero; what survives is the remainders of lower degree, and there are $p^{n}$ of them. The same move, in a ring where smaller means lower degree.
Another way: steps
To build and use a field with $p^{n}$ elements: 1. Find an irreducible polynomial $f$ of degree $n$ over $\mathbb{Z}_p$ — in low degree, one with no root. 2. The elements are the polynomials of degree below $n$; there are $p^{n}$. 3. Add coefficientwise, reducing modulo $p$. 4. Multiply as polynomials, then reduce modulo $f$ using $f = 0$. 5. To invert an element, run Euclid's algorithm against $f$ and read off Bézout.
Take $p = 2$ and $f = x^{2} + x + 1$, which is irreducible over $\mathbb{Z}_2$ because it has no root there: at $0$ and at $1$ its value is $1$. Write $\alpha$ for the class of $x$, so the defining relation is
$$\alpha^{2} = \alpha + 1$$
(the signs do not matter, since $-1 = 1$ in characteristic $2$). The elements are $0, 1, \alpha, \alpha + 1$.
Addition is coefficientwise modulo $2$, so every element is its own negative and the additive group is the Klein four-group — not cyclic of order four. That is worth noticing: a field of characteristic $2$ has no element of additive order $4$, however many elements it has.
Multiplication on the three non-zero elements:
| $\times$ | $1$ | $\alpha$ | $\alpha + 1$ |
|---|---|---|---|
| $1$ | $1$ | $\alpha$ | $\alpha + 1$ |
| $\alpha$ | $\alpha$ | $\alpha + 1$ | $1$ |
| $\alpha + 1$ | $\alpha + 1$ | $1$ | $\alpha$ |
using $\alpha^{2} = \alpha + 1$ and $\alpha(\alpha + 1) = \alpha^{2} + \alpha = 1$. The multiplicative group is cyclic of order $3$, generated by $\alpha$, as theorem 3 promises.
So $\mathbb{F}_4$ is not $\mathbb{Z}_4$: the two have the same size and different additive structure, and only one of them is a field. The residues modulo $4$ have $2 \times 2 = 0$, which no field permits.
Finite fields are not a curiosity. $\mathbb{F}_{2^{8}}$ — the field with $256$ elements, built exactly this way from an irreducible polynomial of degree eight — is where the AES encryption standard does its arithmetic, and error-correcting codes on compact discs and in deep-space transmission are built from polynomials over finite fields. The construction in this lesson is the one running in that hardware.
Confusing $\mathbb{F}_{p^n}$ with $\mathbb{Z}_{p^n}$. The residues modulo $4$ are not a field: $2 \times 2 = 0$. Only when $n = 1$ do the two agree.
Expecting a field of any size. Six, ten and twelve are not prime powers, and no field has those sizes.
Thinking the choice of irreducible polynomial changes the field. It changes the coordinates. Any two fields of the same size are isomorphic.
Mixing up the additive and multiplicative groups. In $\mathbb{F}_4$ the additive group is the Klein four-group and the multiplicative group is cyclic of order $3$. The multiplicative group of a finite field is always cyclic; the additive group never is, once $n > 1$.
Forgetting to reduce twice. Coefficients reduce modulo $p$ and the polynomial reduces modulo $f$. Both are needed at every step.
Take $p = 3$ and $f = x^{2} + 1$, irreducible over $\mathbb{Z}_3$ because $0^2 + 1 = 1$, $1^2 + 1 = 2$ and $2^2 + 1 = 5 = 2$ — no root.
An irreducible quadratic.
The elements are $a + b\alpha$ with $a, b \in \{0, 1, 2\}$, so $3^{2} = 9$ of them, and the relation is $\alpha^{2} = -1 = 2$.
Nine elements.
Multiply: $(1 + \alpha)(2 + \alpha) = 2 + 3\alpha + \alpha^{2} = 2 + 0 + 2 = 4 = 1$. So those two elements are inverse to each other.
Reduce coefficients, then reduce the square.
Suppose $F$ is a field with six elements. Its characteristic is a prime $p$, and $F$ contains a copy of $\mathbb{Z}_p$.
Start from the characteristic.
$F$ is then a vector space over $\mathbb{Z}_p$ of some dimension $n$, so it has exactly $p^{n}$ elements.
The counting argument.
But $6 = 2 \times 3$ is not $p^{n}$ for any prime $p$. Contradiction, so no such field exists — and the same argument rules out $10$, $12$ and every other non-prime-power.
A whole family of sizes excluded at once.
The elements are the remainders: polynomials of degree below $5$, so with five coefficients.
Count the remainders.
Each coefficient is $0$ or $1$, chosen independently, giving $2^{5} = 32$.
Two choices, five times.
So it is the field with $32$ elements — the only one of that size, whichever irreducible quintic is used to build it.
Build the field with four elements as the polynomials over the integers modulo $2$, reduced by $x^{2} + x + 1$. Write $x$ as $2$ and $x + 1$ as $3$. Complete the multiplication table of the three non-zero elements; the row and column of $1$ are given.
| 1 | 2 | 3 | |
|---|---|---|---|
| 1 | 1 | 2 | 3 |
| 2 | 2 | ||
| 3 | 3 |
The polynomial $x^2 + 1$ is irreducible of degree $2$ over the integers modulo $3$. How many elements does the quotient by it have?
Answer:
Each of these is the size of a finite field. Match it to the prime and the degree that build it.
| characteristic $2$, degree $3$ | characteristic $3$, degree $2$ | characteristic $5$, degree $2$ | characteristic $2$, degree $4$ | characteristic $2$, degree $8$ | |
|---|---|---|---|---|---|
| $8$ elements | |||||
| $9$ elements | |||||
| $25$ elements | |||||
| $16$ elements |
Select every statement about finite fields that is true.
This task has no paper form; do it on a device.
Is there a field with exactly $6$ elements?
Build the proof that the polynomials over a field, quotiented by an irreducible polynomial, form a field.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Is there a field with exactly $9$ elements?
You can build a small finite field and compute in it, and you know which sizes are possible. Say in your own words why there is no field with six elements, and why the residues modulo four are not a field. That is the end of the course: groups, rings and fields, each built by quotienting a structure by the right kind of subobject.
9. Your turn: how many elements has the quotient of the polynomials over the integers modulo $2$ by an irreducible polynomial of degree $5$?, step 3