Editing Finite field (section)

=== Example: GF(64) ===
The field <math>\mathrm{GF}(64)</math> has several interesting properties that smaller fields do not share: it has two subfields such that neither is contained in the other; not all generators (elements with [[Minimal polynomial (field theory)|minimal polynomial]] of degree <math>6</math> over <math>\mathrm{GF}(2)</math>) are primitive elements; and the primitive elements are not all conjugate under the [[Galois group]].

The order of this field being {{math|2<sup>6</sup>}}, and the divisors of {{math|6}} being {{math|1, 2, 3, 6}}, the subfields of {{math|GF(64)}} are {{math|GF(2)}}, {{math|1=GF(2<sup>2</sup>) = GF(4)}}, {{math|1=GF(2<sup>3</sup>) = GF(8)}}, and {{math|GF(64)}} itself. As {{math|2}} and {{math|3}} are [[coprime]], the intersection of {{math|GF(4)}} and {{math|GF(8)}} in {{math|GF(64)}} is the prime field {{math|GF(2)}}.

The union of {{math|GF(4)}} and {{math|GF(8)}} has thus {{math|10}} elements. The remaining {{math|54}} elements of {{math|GF(64)}} generate {{math|GF(64)}} in the sense that no other subfield contains any of them. It follows that they are roots of irreducible polynomials of degree {{math|6}} over {{math|GF(2)}}. This implies that, over {{math|GF(2)}}, there are exactly {{math|1=9 = {{sfrac|54|6}}}} irreducible [[monic polynomial]]s of degree {{math|6}}. This may be verified by factoring {{math|''X''<sup>64</sup> − ''X''}} over {{math|GF(2)}}.

The elements of {{math|GF(64)}} are primitive <math>n</math>th roots of unity for some <math>n</math> dividing <math>63</math>. As the 3rd and the 7th roots of unity belong to {{math|GF(4)}} and {{math|GF(8)}}, respectively, the {{math|54}} generators are primitive {{math|''n''}}th roots of unity for some {{math|''n''}} in {{math|{9, 21, 63}<nowiki/>}}. [[Euler's totient function]] shows that there are {{math|6}} primitive {{math|9}}th roots of unity, <math>12</math> primitive <math>21</math>st roots of unity, and <math>36</math> primitive {{math|63}}rd roots of unity. Summing these numbers, one finds again <math>54</math> elements.

By factoring the [[cyclotomic polynomial]]s over <math>\mathrm{GF}(2)</math>, one finds that:
* The six primitive <math>9</math>th roots of unity are roots of <math display="block">X^6+X^3+1,</math> and are all conjugate under the action of the Galois group.
* The twelve primitive <math>21</math>st roots of unity are roots of <math display="block">(X^6+X^4+X^2+X+1)(X^6+X^5+X^4+X^2+1).</math> They form two orbits under the action of the Galois group. As the two factors are [[reciprocal polynomial|reciprocal]] to each other, a root and its (multiplicative) inverse do not belong to the same orbit.
* The <math>36</math> primitive elements of <math>\mathrm{GF}(64)</math> are the roots of <math display="block">(X^6+X^4+X^3+X+1)(X^6+X+1)(X^6+X^5+1)(X^6+X^5+X^3+X^2+1)(X^6+X^5+X^2+X+1)(X^6+X^5+X^4+X+1).</math> They split into six orbits of six elements each under the action of the Galois group.

This shows that the best choice to construct <math>\mathrm{GF}(64)</math> is to define it as {{math|GF(2)[''X''] / (''X''<sup>6</sup> + ''X'' + 1)}}. In fact, this generator is a primitive element, and this polynomial is the irreducible polynomial that produces the easiest Euclidean division.