# Field

Let $S$ be a set, closed under binary operations $+$ (addition) and $\cdot$ (multiplication). It gives us the following algebraic structures if the corresponding set of axioms are satisfied.

Structures Axioms Operations
field commutative
ring
ring abelian
group
group monoid semigroup 1. Addition is associative: $\forall x,y,z\in S, (x+y)+z= x+(y+z).$ $+$
2. Existence of additive identity 0: $\forall x\in S, x+0= 0+x=x.$
3. Everyone has an additive inverse: $\forall x\in S, \exists -x\in S, \text{ s.t. } x+(-x)= (-x)+x=0.$
4. Addition is commutative: $\forall x,y\in S, x+y= y+x.$
5. Multiplication distributes over addition: $\forall x,y,z\in S, x\cdot(y+z)= x\cdot y+x\cdot z$ and $(y+z)\cdot x= y\cdot x+z\cdot x.$ $+,\cdot$
6. Multiplication is associative: $\forall x,y,z\in S, (x\cdot y)\cdot z= x\cdot (y\cdot z).$ $\cdot$
7. Existence of multiplicative identity 1: $\forall x\in S, x\cdot 1= 1\cdot x=x.$
8. Multiplication is commutative: $\forall x,y\in S, x\cdot y= y\cdot x.$
9. Every non-zero element has a multiplicative inverse: $\forall x\in S\setminus\{0\}, \exists x^{-1}\in S, \text{ s.t. } x\cdot x^{-1}= x^{-1}\cdot x=1.$

The semigroup, monoid, group and abelian group are given by $(S,+)$, and the ring, commutative ring, and field are given by $(S,+,\cdot)$.

Examples:

• Infinite fields: $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$ are fields. The integer set $\mathbb{Z}$ is a commutative ring but is not a field.
• Finite fields: Finite fields are called Galois fields. The number of elements of a finite field is called its order. A finite field of order $q$, is usually denoted as $\mathsf{GF}(q)$ or $\mathbb{F}_q$.
• Prime field ${\mathbb{Z}_p}$: For any integer $n\gt 1$, $\mathbb{Z}_n=\{0,1,\ldots,n-1\}$ under modulo-$p$ addition $+$ and multiplication $\cdot$ forms a commutative ring. It is called quotient ring, and is sometimes denoted as $\mathbb{Z}/n\mathbb{Z}$. In particular, for prime $p$, $\mathbb{Z}_p$ is a field. This can be verified by Fermat's little theorem.
• Boolean arithmetics $\mathsf{GF}(2)$: The finite field of order 2 $\mathsf{GF}(2)$ contains only two elements 0 and 1, with bit-wise XOR as addition and bit-wise AND as multiplication. $\mathsf{GF}(2^n)$
• Other examples: There are other examples of finite fields, for instance $\{a+bi\mid a,b\in \mathbb{Z}_3\}$ where $i=\sqrt{-1}$. This field is isomorphic to $\mathsf{GF}(9)$. In fact, the following theorem holds for finite fields of given order.
 Theorem A finite field of order $q$ exists if and only if $q=p^k$ for some prime number $p$ and positive integer $k$. Moreover, all fields of a given order are isomorphic.

# Polynomial over a field

Given a field $\mathbb{F}$, the polynomial ring $\mathbb{F}[x]$ consists of all polynomials in the variable $x$ with coefficients in $\mathbb{F}$. Addition and multiplication of polynomials are naturally defined by applying the distributive law and combining like terms.

 Proposition (polynomial ring) $\mathbb{F}[x]$ is a ring.

The degree $\mathrm{deg}(f)$ of a polynomial $f\in \mathbb{F}[x]$ is the exponent on the leading term, the term with a nonzero coefficient that has the largest exponent.

Because $\mathbb{F}[x]$ is a ring, we cannot do division the way we do it in a field like $\mathbb{R}$, but we can do division the way we do it in a ring like $\mathbb{Z}$, leaving a remainder. The equivalent of the integer division for $\mathbb{Z}$ is as follows.

 Proposition (division for polynomials) Given a polynomial $f$ and a nonzero polynomial $g$ in $\mathbb{F}[x]$, there are unique polynomials $q$ and $r$ such that $f =q\cdot g+r$ and $\mathrm{deg}(r)\lt \mathrm{deg}(g)$.

The proof of this is by induction on $\mathrm{deg}(f)$, with the basis $\mathrm{deg}(f)\lt \mathrm{deg}(g)$, in which case the theorem holds trivially by letting $q=0$ and $r=f$.

As we turn $\mathbb{Z}$ (a ring) into a finite field $\mathbb{Z}_p$ by taking quotients $\bmod p$, we can turn a polynomial ring $\mathbb{F}[x]$ into a finite field by taking $\mathbb{F}[x]$ modulo a "prime-like" polynomial, using the division of polynomials above.

 Definition (irreducible polynomial) An irreducible polynomial, or a prime polynomial, is a non-constant polynomial $f$ that cannot be factored as $f=g\cdot h$ for any non-constant polynomials $g$ and $h$.