{"size": 23442, "ext": "scrbl", "max_stars_repo_path": "finite_fields.scrbl", "max_stars_repo_name": "charles-l/math-notes", "max_stars_repo_stars_event_min_datetime": null, "max_stars_repo_stars_event_max_datetime": null, "max_issues_repo_path": "finite_fields.scrbl", "max_issues_repo_name": "charles-l/math-notes", "max_issues_repo_issues_event_min_datetime": null, "max_issues_repo_issues_event_max_datetime": null, "max_forks_repo_path": "finite_fields.scrbl", "max_forks_repo_name": "charles-l/math-notes", "max_forks_repo_forks_event_min_datetime": null, "max_forks_repo_forks_event_max_datetime": null}
{"max_stars_count": null, "max_issues_count": null, "max_forks_count": null, "avg_line_length": 34.6775147929, "max_line_length": 278, "alphanum_fraction": 0.5240593806}
#lang scribble/base
@(require scribble-math)
@(require pict)
@(use-mathjax)
@(define (proof . s*)
                    (list
                     (italic "Proof")
                     (nested #:style 'inset s*)))

@(define (example . s*)
                    (list
                     (italic "Example")
                     (nested #:style 'inset s*)))

@(define (generator . s*)
                    (string-append "\\langle " (apply string-append s*) "\\rangle"))

@title{Abstract algebra and finite fields}

@section{Group}

Let @${G} be a set.

Let there be an operation @${* : G \times G \rightarrow G}

If the @${*} operation has associativity, an identity and an inverse, it is a group.

@section{Coset}

Let @${G} be a group and @${H} be a subgroup. Let @${g \in G}

@$${gH = \{gh, h \in H\}} is a left coset.
@$${Hg = \{hg, h \in H\}} is a right coset.

@section{Ring}

A ring is composed of:
@itemlist[@item{a set}
          @item{a @${+} operation (forming an abelien group - a.k.a. a commutative group)}
          @item{a @${*} operation (with associative and distributive properties)}]

@section{Ideal}

An ideal is a subgroup of a ring in addition.

A left ideal is @${RI \subseteq I} (where @${R * I} is defined by @${\forall r \in R, \forall i \in I, r * i \in I})

A right ideal is @${IR \subseteq I} (where @${I * R} is defined by @${\forall i \in I, \forall r \in R, i * r \in I})

@margin-note{Note: If the @${*} operation is commutative, the ideal will be two sided}
A two-side ideal is @${RI \subseteq I} and @${IR \subseteq I}

@bold{Example}

Let @${R} be a ring.

@$${R = \{2k : k \in \mathbb{Z}\} = 2\mathbb{Z}}
@$${I = 6\mathbb{Z} \subseteq 2\mathbb{Z}}
Note @${\forall r \in R, i \in I, r * i} is a multiple of 6 (since @${i} is a multiple of 6).

@$${\Rightarrow ri \in I}
@centered{@${\therefore RI \subseteq I} and @${IR \subseteq I}}

@margin-note{Note: if I is an ideal, then @${RI = I} if @${R} has the multiplicative identity}

@${(R,+)} is an abelian group. @${I} is a subgroup.

Cosets of @${I} are @${a + I} for some @${a \in R}

@bold{These cosets form a group.}

Bear in mind: @${a + I = a^\prime + I} iff @${a - a^\prime \in I}

@proof{
Claim: if @${i \in I} then @${i + I = I} (i.e. @${i + I \subseteq I} and @${I \subseteq i + I})

@$${\forall j \in I, i + j \in I}
@$${\therefore i + I \subseteq I}

And for the opposite direction:

@$${\forall j \in I, i + (j - i) \in i + I}

Because @${(j - i) \in I},

@$${\Rightarrow j \in i + I}
@centered{@${\therefore I \subseteq i + I} [@${*}]}

Which means @${i + I = I}

@centered{If @${a - a^\prime \in I}, then @${a + I = a^\prime + (a - a^\prime) + I}}
@centered{@${= a^\prime + I} (by @${*}) [@${**}]}

@centered{If @${a + I = a^\prime + I}, then @${a + 0 = a^\prime + j} for some @${j \in I}}
@centered{@${a - a^\prime = j \in I} by @${**}}
@centered{@${\therefore a + I = a^\prime + I} iff @${a - a^\prime \in I} ∎}
}

@section{Quotient ring}

The collection of cosets in @${I} is defined by:
@$${R/I = \{a + I : a \in R\}}

Define (where @${a, b \in R}):
@$${(a + I) + (b + I) = (a + b) + I}
@$${(a + I) * (b + I) = ab + I}

@italic{Example}

Consider @${\mathbb{Z}} (a ring) and @${6\mathbb{Z}} (multiples of 6 -- an ideal of @${\mathbb{Z}}), the quotient ring is @${\mathbb{Z}_{6} = \mathbb{Z}/6\mathbb{Z}}

A @bold{Principle ideal} is defined by: @${I = aR, a \in R = @generator{a}} (we say it is generated by A)

id @${a * 0 = 0 \in R}

inverse @${a * b + a * -b = a(b - b) = a * 0 = 0}

@${\Rightarrow a * -b} is the multiplicative inverse of @${a * b} in @${@generator{a}}

@${a * b + a * c = a(b + c) \in @generator{a}}

@${\forall b \in R, b * @generator{a} = baR = a(bR) \subseteq aR = @generator{a}}

@${\therefore R * @generator{a} \subseteq @generator{a}}

---

PID = principle ideal domain

F = field

F[X] is a PID

Commutative, unity, no zero divisor

@proof{
Let @${I} be an ideal of @${F[X]}, @${p(x) \in I} be a lowest degree non-zero polynomial.

Assume @${i(x) \in I} s.t. @${\nexists a(x) \in R} s.t. @${p(x)a(x) = i(x)}

@${i(x) = p(x) * q(x) + r(x)}

Degree of @${r(x)} < degree of @${p(x)}

Note @${i(x) \in I} and @${p(x)q(x) \in I}

@${r(x) = i(x) - p(x)q(x) \in I}

Degree of @${r(x)} can't be lower than the lowest nonzero polynomial in @${I}.

@${\therefore} contraction.
}

@${\mathbb{Z}_{n} = {0, 1, 2, \ldots, n - 1}} (@${+}, @${*} done mod n)

@${\mathbb{Z}_{n} \cong \mathbb{Z} / n\mathbb{Z}}
@margin-note{Note: @${n \mathbb{Z} = @generator{n}} i.e. the ideal of @${\mathbb{Z}} generated by n}

cosets: @${a + n\mathbb{Z}, a \in \mathbb{Z}} and @${a + n\mathbb{Z}, a + n \mathbb{Z}} if @${a - a^{\prime} \in n \mathbb{Z}}

Ideals can be viewed as partitions:

TODO: add arrows and merge stuff to this picture

@(let* ((first (rectangle 10 100))
          (first-lab (text "Ideal"))
          (combined (vl-append
                     (hc-append
                      (text "R=")
                      first
                      (rectangle 10 100)
                      (rectangle 10 100)
                      (rectangle 10 100)
                      (rectangle 10 100)
                      (rectangle 10 100)
                      (rectangle 10 100)
                      (rectangle 10 100)
                      (rectangle 10 100))
                     first-lab)))
          (pin-line combined first cc-find first-lab cc-find))

Each ideal gets merged into a single element. The first @${I \rightarrow 0}, then @${a + I \rightarrow a}, @${b + I \rightarrow b}, \ldots

TODO: do example of Z_9

---

Principle ideal domain is a ring with
@itemlist[@item{Commutative multiplication}
          @item{Unity for multiplication}
          @item{No zero divisors}
          @item{Every ideal can be generated by 1 element}]

So every ideal is @${a * R} for a certain @${a}

@${F} is a field. @${F[x] \supseteq F}.

@${F[x]} is a PID since every ideal you can find can be written as @${p(x) * F[x]}

@${F[x, y]} is not a PID

@margin-note{To find a subgroup @${H \subseteq G}, @${H} is a subgroup of G iff @${\forall h_{1}, h_{2} \in H,} @${h_{1}, h_{2}^{-1} \in H}}
@proof{
          @$${I = \{p(x, y) | p(0, 0) = 0\}}
          (i.e. all polynomails without constants)
          @$${q, r \in I}
          @$${q - r \in I}
          @${\forall q(x, y) \in F[x, y], \forall p (x, y) \in I} we want to show @${\nexists p(x, y) \in I} s.t @${\forall q(x, y) \in I, p(x, y)q(x, y) \in I}

          Lowest degree polynomials @${x} or @${y} can't be divided by anything but a constant, but constants aren't in @${I}, so @${F[x, y]} isn't a PID. ∎
}

@bold{Theorem 4.2}
Let @${F} be a field and @${f(x) \in F[x]} be an irreducible polynomial.
Then @${F[x]/@generator{f(x)}} is a field

@proof{
          @${F[x]/@generator{f(x)} \supseteq \{a + @generator{f(x)} : a \in F\} \cong F}
          Multiplicative identity is @${1 + @generator{f(x)}}

          Other axioms hold.

          Now to find the multiplicative inverse such that @${p(x)q(x) = 1 + s(x)f(x)}

          Since then @${(p(x) + @generator{f(x)})(q(x) + @generator{f(x)}) = p(x)q(x) + @generator{f(x)}}

          @${= 1 + s(x)f(x) + @generator{f(x)}}

          Note that @${s(x)f(x) + @generator{f(x)} \in @generator{f(x)}}

          For every coset of @${@generator{f(x)}} we need to find its multiplicative inverse. All cosets are in the form @${p(x) + f(x)} where @${\deg p(x) < \deg f(x)}.

          Note that then @${\gcd(p(x), f(x)) = 1} since @${f(x)} is irreducible.

          By the division algorithm, @${\exists q(x)s(x)} such that @${p(x)q(x) - s(x)f(x) = 1}

          @${\therefore \exists} a multiplicative inverse. ∎
}

We can view @${F[X]/@generator{f(x)}} as an exgension of the field.

@${K} is a field, @${F} is a subfield of @${K}.

@${K} can be viewed as a vector space over @${F}.

@proof{
          Axioms 1-5 are already met since K is a commutative group under addition.

          Axiom 6: @${\forall x \in K, \forall c \in F \subseteq K, c * x \in K}.

          Axiom 7: @${\forall c \in F, \forall x, y \in K, c(x + y) = cx + cy}

          Axiom 8: @${\forall c, d \in F, \forall x \in K, (c + d) * x = cx + dx}

          Axiom 9: @${\forall c, d \in F, \forall x \in K, (c * d) * x = c * (d * x)}

          Axiom 10: @${1 \in F, \forall x \in K, 1 * x = x}
}

@${K} has a basis (over @${F}).

@${\dim K} over @${F} denoted @${[K : F]} (a.k.a. extension degree of @${K} over @${F})

@${f(x) = a_{n}x^{n} + a_{n - 1}x^{n - 1} + \ldots + a_{1}x + a_{0}, a_{n} \neq 0, a_{0} \neq 0}

The elements in @${K} look like: @${b_{m}x^{m} + b_{m - 1}x^{m - 1} + \ldots + b_{1}x + b_{0} + @generator{f(x)}} where @${m < n} since a larger polynomial can be divided by @${f(x)} resulting in a smaller polynomial that is already in the set.

The basis of K over @${F = \{x^{n - 1} + @generator{f(x)}, x^{n - 2} + @generator{f(x)}, \ldots, 1 + @generator{f(x)}\}}

@margin-note{any polynomial that is a multiple of @${f(x)} becomes @${0}}

@${\therefore} the degree of the polynomial is @${n = \deg f}

---

@${K} is a field, @${F} is a subfield of @${K}.

If @${a \in K} is the root of a polynomial of @${F[x]}, then @${\alpha} is algebraic over @${F}.

@${\mathbb{R} = K, \mathbb{Q} = F}.

Consider @${\alpha = \sqrt{5 + \sqrt[3]{6}} \in \mathbb{R}} is algebraic over @${\mathbb{Q}} since it is a root of a polynomial in @${\mathbb{Q}[x]}

@example{
          @${x - \sqrt{5 + \sqrt[3]{6}}}

          @${\alpha} is a root. It is in @${\mathbb{R}[x]}, but @bold{not} in @${\mathbb{Q}}

          @$${x - \sqrt{5 + \sqrt[3]{6}} = 0}
          @$${x = \sqrt{5 + \sqrt[3]{6}}}
          @$${x^{2} = 5 + \sqrt[3]{6}}
          @$${x^{2} - 5 = \sqrt[3]{6}}
          @$${(x^{2} - 5)^{3} = 6}

          @${\alpha} is a root of @${x^6 - 15x^4 + 75x^2 - 131 = 0 \in \mathbb{Q}[x]}
}

Any element in @${K} that is not algebraic over @${F} is @italic{transcendental} over @${F}. e.g. @${\pi}, @${e}, @${0.101001000100001\ldots}

The set of algebraic numbers over @${\mathbb{Q}} is countable.

@$${|\mathbb{Q}| = |\mathbb{N}|}
@$${|\mathbb{R}| > |\mathbb{N}|}
The cardinality of the set of transcendental numbers @${> |\mathbb{N}|}

@centered{@${\alpha \in K} s.t. @${\alpha} is algebraic over @${F}.}
@${\alpha} is a root of the polynomial in @${F[x]}

The @italic{minimal polynomial} of @${\alpha} over @${F} is a monic, irreducible polynomial @${f(x) \in F[x]} s.t. @${\alpha} is a root of @${f}

@margin-note{@bold{monadic} the leading coefficient of the polynomial is 1}.

If @${a \in K} is algebraic over @${F}, then the minimal polynomial of @${\alpha} over @${F} is unique.
@proof{
          Let @${f(x), g(x)} be minimal polynomials. Assume @${g(x)} has the lowest degree among all minimum polynomials.
          If @${\deg f \neq \deg g}, without loss of generality, let @${\deg f > \deg g}
          @$${f(x) = q(x)g(x) + r(x), \deg r < \deg g}

          If @${r(x) \neq 0}, then it contradicts the fact that g has the lowest degree among all minimal polynomials.

          If @${r(x) = 0}, then @${f(x)} is not irreducible (contradiction)

          If @${\deg f = \deg g} then @${f(x) - g(x)} has a degree less than degree g.

          If @${f(x) - g(x) = 0} then since @${f(\alpha) - g(\alpha) = 0}.

          This contradicts that @${g} has the lowest degree.

          @${\therefore f(x) - g(x) = 0} i.e @${f(x) = g(x)} @${\therefore} the minimal polynomial is unique.
}

@example{
          @${\sqrt[3]{6}} satisfies @${4x^{3} - 24} @${\rightarrow} @${x^{3} - 6} is irreducible,
          so the minimal polynomial @${(x^{6} - 36) = (x^{3} - 6)(x^{3} + 6)} is not irreducible.
}

Any polynomial that @${\alpha} satisfies is a multiple of the minimal polynomial.

Let @${F} be a finite field.

Consider @${1, 1 + 1, 1 + 1 + 1, \underbrace{1 + \ldots + 1}_{n} = 0}

@${n} is referred to as the characteristic.

This @${n} is a prime.
@proof{
          Assume @${n = k * l}, @${k, l \neq 1}

          @${\underbrace{(1 + 1 + \ldots + 1)}_{l}\underbrace{(1 + 1 + \ldots + 1)}_{k}}

          But the first object is a zero divisor! @${\therefore} contradiction.
}

Now @${\{0, 1, 1 + 1, \ldots, \underbrace{1 + \ldots + 1}_{p - 1}\} \cong \mathbb{Z}p}

We can think of @${F} as an extension of @${\mathbb{Z}p}

Recall that @${F} is a vector space over @${\mathbb{Z}p}

Let the basis be @${\{b_{1}, \ldots, b_{m}\}}

@(define blank "\\underline{\\hspace{3mm}}")

@${F = \{@blank b_{1} + @blank b_{2} + \ldots + @blank b_{m} : @blank \in \mathbb{Z}p\}}

Since each @${b_i} has @${p} choices, the size of the set is @${\underbrace{p * p * \ldots * p}_{m}} @${\Rightarrow} @${|F| = p^m}

---

@${F^{\times} = F - \{0\}} is a multiplicative group (since @${0} doesn't have a multiplicative inverse)

Order is @${p^{n} - 1 \rightarrow \forall \in F^{\times}, a^{p^{n} - 1} = 1 \Rightarrow a^{p^{n}} = a \rightarrow a^{p^{n}} - a = 0}

Finite @${(G, *), \forall g \in G, \underbrace{g * g * \ldots * g}_{|G|} = e} (Lagrange's theorem)

@${\forall a \in F, a} is a root of @${x^{p^{n}} - x = 0}

Algebraic over @${\mathbb{Z}_p} means it is a root of a polynomial in @${\mathbb{Z}_p [X]}

@${k = \{0, 1, 1+1, 1+1+1, \ldots , \underbrace{1 + 1 + \ldots + 1}_{p - 1}\}}

@${F} is a finite field with characteristic @${p}.

@${K}, a prime subfield @${\cong} @${\mathbb{Z}_p}

@${\alpha} has a minimal polynomial @${f(x) = x^{r} + a_{r - 1} x^{r - 1} + \ldots + a_{1}x + a_0, a_i \in K, a_0 \neq 0}

@${f(x)^p = f(x^p)}

@proof{
          Notice that @${(x + y)^p = x^p + \binom{p}{1} x^{p - 1} y + \binom{p}{2} x ^ {p - 2} y^2 + \ldots + \binom{p}{p - 1} xy^{p - 1} + y^p}

          @${= x^p + y ^ p \in \mathbb{Z}_p} since all @${\binom{p}{i} \forall i \in \{1, \ldots, p - 1\}} are divisible by @${p} (a prime)

          @${f(x)^p = (x^r)^p + a^p_{r - 1}(x^{r - 1})^p + \ldots + a^p_1 + x^p + a^p_0}

          Coefficients come from @${k}, so @${i \in k, i^p = i}

          @${0 = f(\alpha)^p = f(\alpha^p)}

          (The minimum polynomial of @${\alpha ^ p}) @${| f(x)} where @${f(x)} is irreducible.

          The minimum polynomial of @${\alpha ^ p = f(x)}
}

Galois field @${F=GF(p^n)}

@${\mathbb{Z}_p^\times} e.g. @${\{1, 2, \ldots, 10\} = \mathbb{Z}_{11}^\times}

2 is a primitive, so it can be used to generate every element in the set with @${2^i} (@${i = \{1, 2, \ldots, 10\}})

@${\phi(n)} is the number of numbers less than @${n} that are relatively prime to @${n}

@${\phi(20) = 8}

@${\phi(p) = p - 1}

@${\phi(p^2) = p^2 - p}

@${\phi(p^3) = p^3 - p^2}

@${\phi(p^n) = p^n - p^{n - 1}}

@${\phi(p^n q^m) = (p^n - p^{n - 1})(q^m - q^{m - 1})}

@${\phi(p^\alpha p_2^{\alpha_2} \ldots p_r^{\alpha_r}) = (p^{\alpha_1}_1 - p^{\alpha_1 - 1}_1)(p^{\alpha_2}_2 - p^{\alpha_2 - 2}_2) \ldots (p^{\alpha_r}_r - p^{\alpha_r - 1}_r)}

@${\phi(a b) = \phi(a) \phi(b)} if @${\gcd(a, b) = 1}

@${\phi(2^2 * 5) = (2^2 - 2)(5 - 1) = 8}

Number of primitive elements is @${\phi(p^n - 1)}

Finitely generated abelian group theorem: @${G} is an abelian group. Then @${G \cong \mathbb{Z}^n \times \mathbb{Z}^{\alpha_1}_{k_1} \times \mathbb{Z}^{\alpha_2}_{k_2} \times \ldots \times \mathbb{Z}^{\alpha_m}_{k_m}} with addition as the operation.

@example{
          @${M_{2\times3} = \{\begin{bmatrix}
          a & b & c \\
          d & e & f
          \end{bmatrix} : a, b, c, d, e, f \in \mathbb{Z} \cong \mathbb{Z}^6\}}

          Polynomials up to degree 2 in @${\mathbb{Z} [X, Y] \cong \mathbb{Z}^6}
          @${= 1, X, X^2, Y, Y^2, XY}

          @${a_1 + a_2 X + a_3 X^2 + a_4 Y + a_5 Y^2 + a_6 XY \rightarrow (a_1, a_2, a_3, a_4, a_5, a_6)}
}

A finite abelian group

@${G \cong \mathbb{Z}^{\alpha_1}_{k_1} \times \mathbb{Z}^{\alpha_2}_{k_2} \times \ldots \times \mathbb{Z}^{\alpha_m}_{k_m}}

@${\mathbb{Z}_2 \times \mathbb{Z}_3 = \{(a, b) : a \in \mathbb{Z}_2, b \in \mathbb{Z}_3\}}

@${=\{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2)\} \cong \mathbb{Z}_6}

@${\mathbb{Z}_2 \times \mathbb{Z}_4 = \{(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3)\} \cong \mathbb{Z}_8}


@example{
          @smaller{@${\mathbb{Z}_2 \times \mathbb{Z}_3}}
          Starting with @${(0, 0)}, add @${(1, 1)}

          @${(0, 0) (1, 1) (0, 2) (1, 0) (0, 1) (1, 2)}

          @smaller{@${\mathbb{Z}_2 \times \mathbb{Z}_4}}
          @${(0, 0) (1, 1) (0, 2) (1, 3)}
}

@${\mathbb{Z}_a \times \mathbb{Z}_b \cong \mathbb{Z}_{a * b} \iff \gcd(a, b) = 1}

@${\mathbb{Z}_6 \times \mathbb{Z}_{72} \cong \mathbb{Z}_{18} \times \mathbb{Z}_{24}}

Since @${mathbb{Z}_6 \cong \mathbb{Z}_2 \times \mathbb{Z}_3} and @${mathbb{Z}_{72} \cong \mathbb{Z}_8 \times \mathbb{Z}_9}

So by recombining @${\mathbb{Z}_6 \times \mathbb{Z}_{72} \cong \mathbb{Z}_{18} \times \mathbb{Z}_{24}}

Theorem: a polynomial @${p(x) \in F[X]} has at most @${\deg p(x)} roots in @${F}.

@${\alpha is a root of @${p(x) \iff (x - \alpha) | p(x)}}

Lemma @${Z_t}, let @${d | t}. The number of elements with order dividing @${d} is exactly @${d}.

Theorem 4.3 @${F^\times} is cyclic.
@proof{
          @${F^\times} is a finite abelian multiplicative group

          @${F^\times \cong \mathbb{Z}_{k_1} \times \mathbb{Z}_{k_2} \times \ldots \times \mathbb{Z}_{k_m}}, where
          @${k_1 | k_2 | k_3 | \ldots | k_m}

          Number of elements dividing @${k_1 = \underbrace{k_1 + k_1 + \ldots + k_1}_{m} = m * k_1}

          @${x^{k_1} - 1 = 0}

          Number of roots is @${k_1 + k_1 + \ldots + k_1 = m k_1 > \deg \iff m > 1}

          Contradiction, so @${m = 1} so there can only be @${\mathbb{Z}_k}.
}

@${L} is a vector space over @${k} with basis @${\{l_1, l_2, \ldots, l_n\} \subseteq L}

@${\forall l \in L, l = k_1 l_1 + k_2 l_2 + \ldots + k_n l_n}

@${K} is a vector space over @${F} with basis @${\{b_1, b_2, \ldots, b_m\} \subseteq K}

@${\forall k \in K, k = f_1 b_1 + f_2 b_2 + \ldots + f_m b_m}

So @${\{b_1 l_n, b_2 l_n, \ldots, b_m l_n\} \subseteq L} is a basis of @${L} over @${F} where @${\deg = m * n}.

---

Finite field of size @${p^n}. All elements of @${GF(p^n)} are all the roots of @${\underbrace{x^{p^n} - x}_{\text{polynomial over} \mathbb{Z}_p} = 0}

@${GF(8)} (@${8 = 2^3}) @${\alpha} is a root of @${x^3 + x + 1 = 0}

@${GF(8) = \{0, 1, \alpha, \alpha + 1, \alpha^2, \alpha^2 + 1, \alpha^2 + \alpha, \alpha^2 + \alpha + 1\}}

@${\alpha^7 = 1}

@${\alpha^1 = \alpha}

@${\alpha^3 = \alpha + 1}

@${\alpha^2 = \alpha^2}

@${\alpha^6 = \alpha^2 + 1}

@${\alpha^4 = \alpha^2 + \alpha}

@${\alpha^5 = \alpha^2 + \alpha + 1}

@${\alpha^i} are all roots of @${\underbrace{x^{p^n} - x}_{\text{over} \mathbb{Z}_2} = 0}

And are roots of @${x^8 - x = 0 \Rightarrow x(x^7 - 1) = 0} so @${x^3 + x + 1 | x^7 + 1}

@${x(x^{p^n - 1} - 1) = 0} (by Langrange's theorem any element raised to @${p^n - 1} = 1)

@${GF(p^n) - \{0\}} is a multiplicative group with size @${p^n - 1}

@${\mathbb{B}} is a root of @${x^3 + x^2 + 1 = 0}.

@${GF(8) = \{0, 1, \beta, \beta + 1, \beta^2, \beta^2 + 1, \beta^2 + \beta, \beta ^ 2 + \beta + 1\}}

@${\beta^7 = 1}

@${\beta^1 = \beta}

@${\beta^5 = \beta + 1}

@${\beta^2 = \beta^2}

@${\beta^3 = \beta^2 + 1}

@${\beta^6 = \beta^2 + \beta}

@${\beta^4 = \beta^2 + \beta + 1}

@${\alpha \rightarrow \beta} is not an isomorphism of @${GF(8) \rightarrow GF(8)}

@${x^6 + x^5 + 1} is irreducible over @${\mathbb{B}}

@${\alpha} is a root of @${x^6 + x^5 + 1} (which is the minimal polynomial of @${\alpha})

@${GF(2^6) = span (1, \alpha, \alpha^2, \alpha^3, \alpha^4, \alpha^5)}.

Is @${\alpha} primitive? @${GF(2^6)^\times} is of size 63
To verify whether @${\alpha} is a primitive we need to ensure @${\alpha^1, \alpha^2, \ldots, \alpha^21} are not 1. (Only need to check the proper divisors of 63)

if @${a^3 = 1}, @${\alpha^3 - 1 = 0}.

Minimal polynomial of @${\alpha} (i.e. the lowest degree polynomial that has @${\alpha} as its root) divides any polynomial @${p(x)} s.t @${p(\alpha) = 0}

@${f(x) | x^{p^n - 1} - 1}
and @${f(x) \nmid x^k - 1 \forall k < p^n - 1}

@${f(x)} is primitive over @${GF(p)} if its root @${\alpha} generates @${GF(p^n)^x}

@${\alpha ^ k \neq 1 \forall k < p^n - 1}

@${f(x) | x^k - 1} for some @${k < p^n - 1} @${\iff} every root of @${f(x)} satisfies @${x^k - 1 = 0 \iff \alpha ^ k - 1 = 0}, where @${\alpha} is a root of @${f(x)}

@example{
          @${\mathbb{R}}

          |

          @${\mathbb{Q}(\sqrt{2})} <- @${a \sqrt{2} + b, a, b \in \mathbb{Q}}

          |

          @${\mathbb{Q}}

          @${\{a \sqrt{2} + b : a, b \in \mathbb{Q} = \mathbb{Q}[\sqrt{2}]\}}

          Note we only need one degree since it loops back around at @${\sqrt{2}^i, i > 1}
}

In general @${F[\alpha] \supseteq F(\alpha)}

@example{
          @${\mathbb{Q}[x] = \{a_nx^n + a_{n - 1}x^{n - 1} + \ldots + a_0 : a_i \in \mathbb{Q}\}}

          @${\mathbb{Q}(x) = \{\frac{a_nx^n + a_{n - 1}x^{n - 1} + \ldots + a_0}{b_mx^m + b_{m - 1}x^{m - 1} + \ldots + b_0} : a_i, b_i \in \mathbb{Q}, \text{not all } b_i = 0\}}

          So @${\mathbb{Q}(x)} has multiplicative inverses.

          @${\mathbb{Q}[\sqrt{2}] = \mathbb{Q}(\sqrt{2})} since @${\frac{1}{a \sqrt{2} + b} * \frac{a\sqrt{2} - b}{a\sqrt{2} - b} = \frac{a \sqrt{2} - b}{2a^2 - b^2} = \frac{a \sqrt{2}}{2a^2 - b^2} - \frac{b}{2a^2 - b^2} \in \mathbb{Q}(\sqrt{2})}

          @${F(\alpha)} is the smallest subfield containing @${F} and @${\alpha}

          @${\mathbb{Q}(x)(y) = \mathbb{Q}(x, y)}
}

@${f(x)} is a polynomial in @${F[x]}

@bold{Definition of splitting field}
@${K} is a splitting field of @${F[x]} if @${K} is the "smallest" field containing all the roots of @${f(x)}. In other words, @${f(x) = (x - \alpha_1)(x - \alpha_2)\ldots(x - \alpha_n),\, \alpha_1, \alpha_2, \ldots, \alpha_n \in K,\, K = F(\alpha_1, \alpha_2, \ldots, \alpha_n)}

@example{
          @${x^2 - 2} is irreducible over @${\mathbb{Q}}, @${\mathbb{Q}(2)} is the splitting field of @${x^2 - 2}

          @${F[x]}, @${f(x)} is an irreducible polynomial. @${@generator{f(x)}} is an ideal.
}

Claim: @${x + @generator{f(x)} = a_n(x + @generator{f(x)}^n + \ldots + a_1 (x + @generator{f(x)}) + a_0)}

@proof{
          @${= a_n (x^n + @generator{f(x)}) + \ldots a_1 (x + @generator{f(x)}) + a_0}

          Using ideal addition operation:

          @${= a_n x^n + \ldots + a_1 x + a_0 + @generator{f(x)} = f(x) + @generator{f(x)} = @generator{f(x)}}

          @${\therefore x + @generator{f(x)} = @generator{f(x)}} which is the identity

          @${\therefore x + @generator{f(x)} is a root of @${f(x)}}
}

Eisenstein's irreducible criterion: If a polynomial @${x^n + a_{n - 1} x^{n - 1} + \ldots + a_1 x + a_0} satisfies:
@itemlist[@item{@${\exists \text{prime} p \mid a_{n - 1}, a_{n - 2}, \ldots, a_1, a_0}}
          @item{@${p^2 \nmid  a_0}}]
Then the polynomial is irreducible.

@${\mathbb{Q}(\sqrt[4]{2} \cong \mathbb{Q}(\sqrt[4]{2}i))}

@$${x^4 - 2}
@$${= (x^2 + \sqrt{2})(x^2 - \sqrt{2})}
@$${= (x^2 + \sqrt{2})(x + \sqrt[4]{2})(x - \sqrt[4]{2}) \in \mathbb{Q}(\sqrt[4]{2})}

@${\mathbb{Q}(\sqrt[4]{2}, i)}. Note that @${1, i} is in the basis.

| degree 2

@${\mathbb{Q}(\sqrt[4]{2}, i)}. @${1, (\sqrt[4]{2})^2, (\sqrt[4]{2})^3} in the basis.

| degree 4

@${\mathbb{Q}(\sqrt[4]{2}, i)}. @${1, (\sqrt[4]{2})^2, (\sqrt[4]{2})^3} in the basis.

|

@${\mathbb{Q}}

Let @${f(x)} be irreducible over @${F}.

Let @${K} be the splitting field of @${f(x)}. Then

@${K}

| @${\deg | n!}

@${F}

@${f(x)} has @${\alpha_1, \alpha_2, \ldots, \alpha_n} as roots.

@${[F(\alpha_1, \ldots, \alpha_n) : ... : F(\alpha_1, \alpha_2) : F(\alpha_1) : F]}
