\documentclass[%
version=last,%
%a4paper,landscape,twocolumn,%
a5paper,twoside,%
12pt,%
bibliography=totoc,%
index=totoc,%
%titlepage=no,%
reqno,%
cleardoublepage=empty,%
openany,%
draft=true,%
%DIV=12,%
headinclude=false,%
pagesize]%
{scrbook}

%\usepackage[notref,notcite]{showkeys}

\usepackage{multicol}

%\renewcommand{\sectionmark}[1]{\markleft{#1}} % used with scrartcl
\usepackage{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\refoot{Finite fields 2018}
\lofoot{\leftmark} % needs \sectionmark redefined as above in scrartcl
\ofoot{\pagemark}

\usepackage{moredefs,lips}
%\makeindex
%\usepackage{makeidx}

\usepackage[perpage,symbol]{footmisc}
%\renewcommand{\captionformat}{. }

%\usepackage{chngcntr}
%\counterwithout{figure}{chapter}
%\counterwithout{table}{chapter}

\usepackage{graphicx} % allows \rotatebox
\usepackage{rotating}
\usepackage{verbatim}

\usepackage{relsize} % Here \smaller scales by 1/1.2; \relscale{X} scales by X

\renewenvironment{quote}{\begin{list}{}
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}}
\item\relax}
{\end{list}}

\renewenvironment{quotation}{\begin{list}{}%
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}
\setlength{\listparindent}{1em}
\setlength{\itemindent}{\listparindent}
\setlength{\parsep}{\parskip}}
\item\relax}
{\end{list}}

\usepackage{pstricks,pst-node,pst-plot,pst-math,pst-eucl}

\usepackage{amsmath,amsthm,amssymb,bm,upgreek}

\DeclareMathOperator{\characteristic}{char}
\newcommand{\Char}[1]{\characteristic(#1)}
\DeclareMathOperator{\lcm}{lcm}

\swapnumbers
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{Rec}[theorem]{Recursion Theorem}
\newtheorem{Fun}[theorem]{Fundamental Theorem of Arithmetic}
\newtheorem{CRT}[theorem]{Chinese Remainder Theorem}
\newtheorem{WOTh}[theorem]{Well Ordering Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{Euclem}[theorem]{Euclid's Lemma}
\newtheorem{Eugen}[theorem]{Euclid's Lemma, generalized}
\newtheorem{Bezout}[theorem]{B\'ezout's Lemma}
\newtheorem{Division}[theorem]{Division Theorem}
\newtheorem{FT}[theorem]{Fermat's Theorem}
\newtheorem{LT}[theorem]{Lagrange's Theorem}
\newtheorem{ET}[theorem]{Euler's Theorem}
%\newtheorem{Cfag}[theorem]{Classification of finite abelian groups}
\newcommand{\Theorem}[1]{Theorem \ref{#1}}
\newcommand{\Theorems}[1]{Theorems \ref{#1}}

%\allowdisplaybreaks
\DeclareMathOperator{\Endo}{End}
\newcommand{\End}[1][V,+]{\Endo(#1)}

\DeclareMathOperator{\identity}{id} % gives weird spacing
\newcommand{\id}[1][V]{\identity_{#1}}
%\newcommand{\id}[1][V]{\mathsf{id}_{#1}}
\newcommand{\inv}{^{-1}}
%\renewcommand{\phi}{\varphi}
\newcommand{\divides}{\mid}
\newcommand{\bigdivides}{\mathrel{\left.\vphantom{\frac xx}\right|}}
\newcommand{\ndivides}{\nmid}
\newcommand{\gpgen}[1]{\langle#1\rangle}
\newcommand{\euphi}{\upvarphi}
\newcommand{\included}{\subseteq}
\newcommand{\pincluded}{\subset}
\renewcommand{\vec}[1]{\bm{#1}}

\newcommand{\C}{\mathbb C}
\newcommand{\R}{\mathbb R}
\newcommand{\Q}{\mathbb Q}
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\F}[1][p]{\mathbb F_{#1}}
\newcommand{\units}[1]{#1{}^{\times}}
%\DeclareMathOperator{\dee}{d}
\renewcommand{\setminus}{\smallsetminus}
\DeclareMathOperator{\automorphisms}{Aut}
\newcommand{\Aut}[1]{\automorphisms(#1)}
\DeclareMathOperator{\genlin}{GL}
\newcommand{\GL}[1][n]{\genlin_{#1}(\Z)}
\DeclareMathOperator{\diagonal}{diag}
\newcommand{\diag}[1]{\diagonal(#1)}
\newcommand{\alg}[1]{#1{}^{\mathrm{alg}}}
\DeclareMathOperator{\matrices}{M}
\newcommand{\Mat}[1][K]{\matrices_n(#1)}
\DeclareMathOperator{\Identity}{I}
\newcommand{\Id}[1][n]{\Identity_{#1}}
\DeclareMathOperator{\adjoint}{adj}
\newcommand{\adj}[1][B]{\adjoint(#1)}
\DeclareMathOperator{\Span}{span}
\DeclareMathOperator{\symmetric}{Sym}
\newcommand{\Sym}[1][n]{\symmetric(#1)}
\DeclareMathOperator{\signum}{sgn}
\newcommand{\sgn}[1][\sigma]{\signum(#1)}

\newcommand{\mi}{\,\mathrm i\,}
\newcommand{\Zmod}[1][n]{\Z_{#1}}

\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\Forall}[1]{\forall#1\;}

\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\emptyset}{\varnothing}
%\renewcommand{\epsilon}{\varepsilon}
%\newcommand{\gid}{\mathrm e}

\usepackage[all]{xy}

\usepackage[polutonikogreek,english]{babel}
%\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}{#1}}
\usepackage{gfsporson} % this conflicts with bm, not allowing a boldface digit 0
%\usepackage{gfsneohellenic} % so does this, more so, since it changes the digits anyway
\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}{%
\relscale{0.9}%
\textporson{#1}}}

\usepackage{yfonts}
\newcommand{\blackletter}[1]{\textgoth{\larger#1}}
\newcommand{\blackemph}[1]{\textswab{\larger#1}}
\newcommand{\blackfrak}[1]{\textfrak{\larger#1}}

\newcommand{\enquote}[1]{``#1''}

%\newcommand{\grm}[1]{\ensuremath{\text{\foreignlanguage{polutonikogreek}{#1}}}}
%\newcommand{\grm}[1]{\ensuremath{\text{\gr{#1}}}}
%\newcommand{\myXi}{X}

\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\size}[1]{\abs{#1}}
\newcommand{\ord}[1]{\abs{#1}}


\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}
\usepackage{url}

\begin{document}

\subtitle{A winter course at the Nesin Matematik K\"oy\"u}
\title{Finite fields 2018}
\author{David Pierce}
\date{January 22--28, 2018\\
  Edited January 29, 2018\\
Revised March 20, 2018}
\publishers{Matematik B\"ol\"um\"u\\
Mimar Sinan G\"uzel Sanatlar \"Universitesi\\
%\.Istanbul\\
\url{mat.msgsu.edu.tr/~dpierce/}\\
%\url{dpierce@msgsu.edu.tr}
}

\uppertitleback{\centerline{Abstract}
We do some algebra as it arises from number theory.
We prove the basic theorems about finite fields 
by analogy with some basic theorems about the integers.}

\maketitle
%\thispagestyle{empty}

\chapter*{Preface}

The course was scheduled for 9:00--10:30 in the Langlands \emph{dersli\u gi.}
I have given the scheduled dates for the course, Monday to Sunday;
but I cancelled Sunday's class so I could go home Saturday night.
Of the seven students who attended at least one lecture each, 
only one was left on Saturday anyway.

This was my third winter teaching a similar course.
The present notes are edited from a version prepared
from the notes of last year's course
for my use during this course.
Because all but one or two of the students this year were in graduate programs,
I apparently went faster than in previous years,
and I added the final section, on automorphism groups,
in response.
In the beginning, after the Introduction, 
I skipped ahead to \S\ref{sect:measurement}.


\tableofcontents
%\listoffigures


%\section{Monday}

\chapter{Introduction}

\begin{itemize}
\item 
$\Q$, $\R$, and $\C$ are \emph{fields.}
\item
Every field is a \emph{ring.}
\item
$\Z$ is a ring that is not a field.
\item
The ring $\Zmod$ of integers \emph{modulo} $n$ is a field
if and only if $n$ is a prime $p$.
\item
From $\Zmod[p]$, we shall create new finite fields
as $\C$ is created from $\R$.
\item
An important tool will be the \emph{Euclidean Algorithm.}
\item
This will be part of an analogy between $\Z$ and the ring $K[X]$
of polynomials in $X$ over a field $K$.
\end{itemize}

\chapter{Rings}

\section{Ordered ring of integers}\label{sect:Peano}

This section is a summary of things the reader may already already aware of.
Some terminology may be new.

The \textbf{integers} or \textbf{whole numbers}
compose the structure denoted by
\begin{equation*}
  \Z
\end{equation*}
for the German \blackfrak{Zahl} \enquote{number.}
The structure is a \textbf{commutative ring}
for having the following three properties.
\begin{compactenum}
\item
$\Z$ is a \textbf{commutative monoid}
with respect to multiplication,
because this is commutative and associative
and has an \emph{identity} or neutral element, 
so that the following equations are \emph{identities}---%
are universally true---in $\Z$:
\begin{equation}
  \label{eqn:monoid}
  \left.\quad
\begin{gathered}
    xy=yx,\\
x(yz)=(xy)z,\\
x\cdot1=x.
  \end{gathered}
\quad\right\}
\end{equation}
\item
$\Z$ is an \textbf{abelian group}
with respect to addition, 
because it is a commutative monoid 
in which every element has a \textbf{negative}
or additive inverse, 
so that the following are identities:
\begin{equation}
  \label{eqn:group}
  \left.\quad
\begin{gathered}
    x+y=y+x,\\
x+(y+z)=(x+y)+z,\\
x+0=x,\\
x-x=0.
  \end{gathered}
\quad\right\}
\end{equation}
\item
Multiplication distributes over addition in $\Z$:
\begin{equation}\label{eqn:dist}
x\cdot(y+z)=xy+xz.  
\end{equation}
\end{compactenum}
These three properties make $\Z$ a commutative ring.
There are non-commutative rings,
such as the ring of $2\times2$ matrices
with entries from $\Z$.
We shall not be looking at any such rings.
Therefore, for us, 
\begin{center}
\fbox{the word \textbf{ring} shall always mean commutative ring.}
\end{center}

The ring $\Z$ is \textbf{linearly ordered,}
because it has a subset, denoted by
\begin{equation*}
  \N
\end{equation*}
for \enquote{number,}
that
\begin{compactenum}[1)]
  \item
 is closed under addition and multiplication,
\item
does not contain $0$,
\item
contains the negative of its every nonzero non-element.
\end{compactenum}
The elements of $\N$ are the \textbf{positive integers}
or \textbf{counting-numbers.}
The linear ordering of $\Z$ is given by
\begin{equation*}
  x<y\iff y-x\in\N.
\end{equation*}
As an ordering, or more precisely a \emph{strict} ordering,
the relation $<$ is irreflexive and transitive,
so that the following formulas are universally true:
\begin{gather*}
  x\not<x,\\
x<y\And y<z\implies x<z.
\end{gather*}
In addition to being transitive,
the associated relation $\leq$ is reflexive and antisymmetric:
\begin{gather*}
  x\leq x,\\
x\leq y\And y\leq x\implies x=y.
\end{gather*}
The ordering is linear, because
\begin{equation*}
  y\not\leq x\implies x<y.
\end{equation*}
We shall see other ordered rings.
$\Z$ is determined among them 
by the first of the following three properties of $\N$. 
To define these properties,
we describe $x+1$ as the \textbf{successor} of $x$.
Then the following three statements are true about the set $\N$.
\begin{compactenum}
  \item
The only subset that both
\begin{compactenum}[(i)]
  \item
contains $1$ and 
\item
contains the successor of its every element
\end{compactenum}
is the whole set:
this is the \textbf{inductive property.}
\item
The successor of no element is $1$.
\item
No element is the successor of more than one element.
\end{compactenum}
These three properties can be called the \textbf{Peano Axioms.}
They involve only the element $1$
and the singulary operation $x\mapsto x+1$ of succession.

One can prove from the Peano Axioms that, on $\N$,
\begin{compactenum}[1)]
\item
there is a commutative, associative binary operation of addition, 
\item
there is a commutative, associative binary operation of multiplication
that distributes over addition, and
\item
there is a linear ordering $<$ such that always $x<x+y$.
\end{compactenum}
One way to do this,\label{one-way}
but not the only way,
is to start by proving the following.

\begin{Rec}
If a set $A$ is given with an element $b$ and a singulary operation $f$,
then there is a unique function $g$ from $\N$ to $A$,
defined by \textbf{recursion}, so that
\begin{compactenum}[(i)]
  \item
$g(1)=b$, and
\item
$g(n+1)=f(g(n))$ for all $n$ in $\N$.
\end{compactenum}
\end{Rec}

Then for example addition is defined by requiring,
for each $k$ in $\N$, that
\begin{compactenum}[(i)]
  \item
$k+1$ be the successor of $k$, and
\item
$k+(n+1)$ be the successor of $k+n$.
\end{compactenum}
The desired properties of addition are proved by induction.

One ultimately proves:

\begin{WOTh}
$\N$ is \textbf{well ordered,}
in the sense that every nonempty subset of $\N$
has a least element.
\end{WOTh}

Proving everything from the Peano Axioms is not easy 
and is sometimes not well understood.
We shall take the proofs for granted.

\section{Fields}

If $a$ and $b$ are counting-numbers,
we can form from them the positive \textbf{fraction} denoted by
\begin{equation*}
  \frac ab
\end{equation*}
or $a/b$.  By formal definition,
this is the equivalence class of the pair $(a,b)$
with respect to the equivalence relation $\sim$ given by
\begin{equation*}
  (a,b)\sim(x,y)\iff ay=bx.
\end{equation*}
One has to prove that $\sim$ is indeed an equivalence relation,
in the sense of being reflexive, symmetric, and transitive.
The positive fractions, along with their negatives and $0$
compose the structure
\begin{equation*}
  \Q
\end{equation*}
(for \enquote{quotient}),
which is an ordered ring in the natural way learned in school.
Since, moreover, every nonzero fraction $a/b$
has a \textbf{reciprocal} or multiplicative inverse,
namely $b/a$, the ordered ring $\Q$ is an ordered \textbf{field.}
The ring $\Z$ is a sub-ring of $\Q$
when we identify every $n$ in $\Z$ with the fraction $n/1$.
The ordering of $\Z$ agrees with that of $\Q$.
The elements of $\Q$ are the \textbf{rational numbers.}

From the rational numbers,
one obtains the ordered field $\R$ of \textbf{real numbers}
by an infinitary process.
One can understand real numbers as Dedekind cuts,
or as equivalence classes of Cauchy sequences,
or Laurent series (and their negatives) 
in $10^{-1}$ or some other base.

We shall not need real numbers as such,
but the example of obtaining from $\R$ 
the field $\C$\label{C} 
of \textbf{complex numbers} will be useful.
$\C$ is first of all the real vector space $\R\oplus\R\mi$,
which has basis $\{1,\mi\}$.
One defines a commutative, 
associative operation of multiplication on this space
by the rule
\begin{equation*}
  \mi^2+1=0.
\end{equation*}
Then every nonzero complex number $a+b\mi$ has the reciprocal
$(a-b\mi)/(a^2+b^2)$,
so $\C$ is a field.
From given finite fields, 
we shall obtain larger finite fields in a similar way.

\section{Measurement}\label{sect:measurement}

The word arithmetic derives from the Greek \gr{>arijm'os},\label{arithmos}
which denotes a \emph{number of things,}
as opposed to a pure or abstract number.
In ordinary language, a number \emph{of things}
means some \emph{whole} number of them, and at least two.

Instead of developing numbers \emph{arithmetically,}
ultimately by the Peano Axioms as in \S\ref{sect:Peano},
we can work geometrically.
The third proposition of Book \textsc i of Euclid's \emph{Elements}
\cite{MR17:814b}
allows us to add line segments by placing them end to end.
By one of the so-called common notions of Euclid,
we can just place one segment on top of another,
in order to decide whether they are \emph{equal.}
Fixing one point as $0$
on an infinite straight line,
we obtain a binary operation of addition,
so that, as in Figure \ref{fig:add},
\begin{figure}
  \centering
  \begin{pspicture}(-3,-0.5)(5,0.5)
    \psline(-3,0)(5,0)
\psdots(-3,0)(0,0)(2,0)(5,0)
\uput[u](-3,0){$B$}
\uput[u](0,0){$O$}
\uput[u](2,0){$C$}
\uput[u](5,0){$A$}
\uput[d](-3,0){$\vphantom0b$}
\uput[d](0,0){$0$}
\uput[d](2,0){$\vphantom0c$}
\uput[d](5,0){$\vphantom0a$}
  \end{pspicture}
  \caption{Geometric addition}
  \label{fig:add}
\end{figure}
if $AC$ and $OB$ are equal as \emph{directed} segments,
then
\begin{equation*}
  a+b=c.
\end{equation*}
 commutative, associative operation of addition
on the points of the line,
so that these points compose an abelian group.
If in addition we designate one direction along the line,
or one side of $0$, as positive,
this gives us a linearly ordered abelian group.

To define a commutative, associative operation of \emph{multiplication}
on the infinite line that distributes over addition,
we need to select a positive point as $1$,
and we need to pass to a second dimension
and define a notion of proportion,
so as to prove what is known as Thales's Theorem
\cite{Pierce-Thales-9}.
Ultimately the straight line becomes the field of real numbers.
The idea seems to be due to Descartes 
\cite{Descartes-Geometry,Descartes-Geometrie}.

Without going so far,
we can recursively define multiplication of real numbers 
\emph{by} counting-numbers by the rules
\begin{gather*}
  a\cdot1=a,\\
a\cdot(m+1)=a\cdot m+a.
\end{gather*}
By induction,
\begin{align*}
  a\cdot(k+m)&=a\cdot k+a\cdot m,&
a\cdot(k\cdot m)&=(a\cdot k)\cdot m.
\end{align*}
In a product $a\cdot n$, 
\begin{compactitem}
  \item
the real number $a$ is the \textbf{multiplicand,}
while 
\item
the counting-number $n$ is the \textbf{multiplier.}
\end{compactitem}
If we write $a\cdot n$ as $b$, then we say
\begin{compactitem}
  \item
 $n$ \textbf{divides} $b$, while
\item
$a$ \textbf{measures} $b$ and is a \textbf{submultiple} of $b$,
while $b$ is a \textbf{multiple} of $a$.
\end{compactitem}
When $a$ is itself a counting-number,
then
\begin{equation*}
  a\cdot n=n\cdot a,
\end{equation*}
though again one has to prove this by induction.
When we multiply two counting-numbers then,
we may forget the distinction between dividing and measuring.

Still the distinction may be useful.
When we \emph{measure} $8$ by $3$,
we end up with a remainder of $2$, as in Figure \ref{fig:8-meas}.
\begin{figure}
  \centering
  \begin{pspicture}(0,-0.6)(8,1)
%\psgrid
\psset{arrowsize=10pt 2,arrowlength=0.5}
    \psaxes(8,0)
\pcline{<->}(0,0.8)(3,0.8)
\ncput*{$3$}
\pcline{<->}(3,0.8)(6,0.8)
\ncput*{$3$}  
\pcline{<->}(6,0.8)(8,0.8)
\ncput*{$2$}  
\end{pspicture}
  \caption{Measurement by $3$}
  \label{fig:8-meas}
\end{figure}
We can exactly \emph{divide} any number---conceived as a line segment---by $3$,
as $AB$ is divided into the three equal parts $AC$, $CD$, and $DB$
in Figure \ref{fig:div}.
\begin{figure}
  \centering
  \begin{pspicture}*(-0.5,-1)(8.5,3)
%\psgrid
\psset{PointSymbol=none}
  \pstTriangle[PointNameC=none](0,0)A(8,0)B(5,3)F
\pstHomO[HomCoef=0.333,PointName=none]AF[G]
\pstHomO[HomCoef=0.667,PointName=none]AF[H]
\pstSegmentMark AG
\pstSegmentMark GH
\pstSegmentMark HF
\pstTranslation[PointName=none]FB{G,H}
\psset{linestyle=dashed,PosAngle=-120}
\pstLineAB G{G'}
\pstLineAB H{H'}
\pstInterLL ABG{G'}C
\pstInterLL ABH{H'}D
  \end{pspicture}
  \caption{Division by $3$}
\label{fig:div}
\end{figure}

If again $b=a\cdot n$,
we may conceive $a$ as a \emph{number of things,}
while $n$ is a pure number, or at least a number of some other kind of thing,
but $b$ is a number of the same kind of thing as $a$.
Here $a$ might be three apples, while $n$ is a number of children, say four;
then $b$ is twelve apples.
We can \emph{divide} twelve apples among four children,
so that each child ends up with three apples.
We can \emph{measure} twelve apples by three apples,
ending up with four piles, each consisting of three apples.

Using the Euclidean language of measurement,
in a letter to Bernard Fr\'enicle de Bessy (1605--1675)
written Thursday, October 18, 1640, 
Pierre de Fermat (1601--65)
describes
\cite[p.\ 209]{Fermat-Oeuvres-2}
what we now know as Fermat's Theorem
(and shall prove on page \pageref{thm:Fermat}).
The emphasis is mine:
\begin{quote}
  Tout nombre premier \textbf{mesure infailliblement}
  une des puissances $-$ 1
  de quelque progression que se soit,
  et l'exposant de la dite puissance
  est \textbf{sous-multiple} du nombre premier donn\'e $-$ 1;
  et, apr\`es qu'on a trouv\'e
  la premi\`ere puissance qui satisfait \`a la question,
  toutes celles dont les exposants sont multiples
  de l'exposant de la premi\`ere satisfont
  tout de m\`eme \`a la question.
\end{quote}
In his
\emph{Source Book in Mathematics, 1200--1800}
\cite[p.\ 28]{Fermat-theorem},
Struik translates Fermat
as saying ``is a factor of'' instead of measures evenly,
``divisor'' instead of submultiple.
\begin{quote}
Every prime number is always a factor
[\emph{mesure infailliblement}]
of one of the powers of any progression minus $1$,
and the exponent of this power is a divisor
of the prime number minus $1$.
After one has found the first power that satisfies the proposition,
all those powers of which the exponents
are multiples of the exponent of the first power
also satisfy the proposition. 
\end{quote}
Struik misdates the letter as being of October 10, 1640;
but such mistakes may be inevitable in such a compilation as his.
He modernizes Fermat's language,
but this may mean losing the \emph{geometrical}
sense of numbers that Fermat inherited from Euclid.

\section{Division}

In $\Z$ or any ring, when an equation
\begin{equation*}
  ax=b
\end{equation*}
is soluble, one says that $a$ \textbf{divides} $b$,
or $a$ is a \textbf{divisor} or \textbf{factor} of $b$,
but also $b$ is a \textbf{multiple} of $a$.
In this case we use the abbreviation
\begin{equation*}
  a\divides b.
\end{equation*}
I propose to say also that $a$ \textbf{measures} $b$
or is a \textbf{submultiple} of $b$.
We may refer to the relation $\divides$ itself
as \textbf{dividing} or \textbf{divisibility} or \textbf{measuring.}
We shall use the following all the time,
especially \eqref{eqn:lin}.

\begin{theorem}
  In any ring,
  \begin{gather}\notag
    a\divides 0,\\\notag
  0\divides a\implies a=0,\\\notag
a\divides a,\\\notag
a\divides b\And b\divides c\implies a\divides c,\\\label{eqn:lin}
a\divides b\And a\divides c\implies a\divides bx+cy.
\end{gather}
\end{theorem}

The ring $\Z$ is special among rings
for having the ordering that makes the following possible.

\begin{theorem}\label{thm:|=><}
In $\N$,
\begin{equation*}
  a\divides b\implies a\leq b.
\end{equation*}
In particular, measuring (${}\divides{}$) is an ordering of $\N$
(though not linear).
\end{theorem}

The number of factors of an integer is finite.
In particular, of two integers $a$ and $b$,
not both $0$,
there is a common factor that is \emph{greatest} 
with respect to the usual linear ordering $<$.
This \textbf{greatest common divisor}
(or factor, or submultiple) is denoted by
\begin{equation*}
  \gcd(a,b).
\end{equation*}
We shall show that this is greatest with respect to divisibility 
(${}\divides{}$) as well.

The following is also called the Division \emph{Algorithm,}
but it is rather a lemma that makes possible the \emph{Euclidean Algorithm}
described afterwards.
Given two lengths $a$ and $b$, the former being less,
we can subtract $a$ from $b$ until what is left is less than $a$,
again as in Figure \ref{fig:8-meas}.
This is \emph{measuring} $b$ by $a$,
and perhaps it is the performance of an algorithm;
the following theorem proves that the algorithm works.

\begin{Division}\label{thm:div}
For all integers $a$ and $b$,
where $a\neq0$,
either $a\divides b$, or else the system
\begin{equation*}
b=ax+y\And 0<y<\abs a
\end{equation*}
has a unique solution.
\end{Division}

\begin{proof}
Assuming $a\ndivides b$,
let $A$ be the subset
\begin{equation*}
\{b-ax\colon x\in\Z\}\cap\N
\end{equation*}
of $\N$.
Then $A$ is nonempty (why?);
so it has a least element, $r$,
and then for some $q$,
\begin{equation}\label{eqn:b=aq+r}
b=aq+r.
\end{equation}
If $r\geq\abs a$, so that $0\leq r-\abs a<r$,
then, since also
\begin{equation*}
  b=a(q\pm1)+(r-\abs a),
\end{equation*}
we have that $r-\abs a\in A$,
but is less than the least element,
which is absurd.
Therefore $0\leq r<\abs a$.
Uniqueness is an exercise.
\end{proof}

In \eqref{eqn:b=aq+r}, 
$r$ is the \textbf{remainder} of $b$
after measurement (or division) by $a$,
and $q$ is the \textbf{quotient} of $b$ by $a$.

Euclid gives the following as a \emph{porism}
(a corollary of the proof)
of the second proposition of Book \textsc{vii}
of the \emph{Elements.}
It is a consequence of the possibility of applying the
\textbf{Euclidean Algorithm,}
whereby we can compute the greatest common measure of 
$942$ and $180$ as follows.
\begin{equation}
  \label{eqn:EA}
\left.\qquad
\begin{gathered}
942=180\cdot5+42\\
180=42\cdot4+12\\
42=12\cdot3+6\\
12=6\cdot2,
\end{gathered}
\qquad\right\}
\end{equation}
and therefore $\gcd(942,180)=6$, since 
\begin{compactitem}
  \item
$6$, measuring $12$,
measures in turn $42$, $180$, and $942$;
\item
any common measure of $942$ and $180$
measures in turn $42$, $12$, and $6$.
\end{compactitem}

\begin{theorem}\label{thm:gcd}
The greatest common measure of two counting-numbers
is measured by their every common measure.
\end{theorem}

\begin{proof}
Given two unequal counting-numbers,
we continually replace the larger
by its remainder after measurement by the smaller,
if this remainder exists.
Thus if the original numbers are $a_1$ and $a_2$,
the former being greater,
if possible we let
\begin{equation*}
  a_1=a_2x_1+a_3\And a_2>a_3,
\end{equation*}
and in general, as far as possible,
\begin{equation*}
  a_k=a_{k+1}x_k+a_{k+2}\And a_{k+1}>a_{k+2}.
\end{equation*}
Every common measure of $a_1$ and $a_2$
is a common measure of $a_3$, $a_4$, and so on, by \eqref{eqn:lin}.
Since the counting-numbers are well ordered,
the strictly decreasing sequence of $a_k$ must terminate in some $a_n$,
so that
\begin{gather*}
  a_{n-2}=a_{n-1}x_{n-2}+a_n,\\
a_{n-1}=a_nx_{n-1}.
\end{gather*}
Then $a_n$ measures $a_{n-1}$, and $a_{n-2}$, and so on up to $a_1$.
Thus $a_n$ is a common measure of $a_2$ and $a_1$,
and, since it is measured by every common measure, 
it must have been the greatest of these.
\end{proof}

Evidently we can apply the Euclidean Algorithm to arbitary integers,
as long as one of them is not $0$.
As we have proved it,
\Theorem{thm:gcd} has the next result as a porism.
Thus from the computations \eqref{eqn:EA},
working backwards we have
\begin{align*}
  6&=42-12\cdot3=42-(180-42\cdot4)\cdot3\\
&=42\cdot13-180\cdot3=(942-180\cdot5)\cdot13-180\cdot3\\
&=942\cdot13-180\cdot68.
\end{align*}

\begin{Bezout}
In $\Z$, when $a$ and $b$ are not both $0$, the equation
\begin{equation*}
\gcd(a,b)=  ax+by.
\end{equation*}
is soluble.
\end{Bezout}

We can also prove \Theorem{thm:gcd}
as a corollary of B\'ezout's Lemma,
since there is a non-constructive proof of B\'ezout's Lemma,
not relying on our first proof of \Theorem{thm:gcd}.

\begin{proof}[Abstract proof of B\'ezout's Lemma.]
  The set
\begin{equation}\label{eqn:ax+by}
  \{ax+by\colon(x,y)\in\Z\times\Z\}
\end{equation}
of integers
has positive elements, such as $\abs a+\abs b$;
therefore the set has a least positive element.
Let this be $as+bt$ or $d$.
If now $r$ is the remainder of $a$ after measurement by $d$,
and $q$ the quotient,
then
\begin{equation*}
  r=a-dq=a\cdot(1-sq)-btq.
\end{equation*}
Then $r$ belongs to the set in \eqref{eqn:ax+by},
so $r=0$ by minimality of $d$.
Thus $d\divides a$, and in the same way, $d\divides b$.
Then $d$ must be $\gcd(a,b)$.
\end{proof}

There is a third way to prove \Theorem{thm:gcd}.
It is the method that Landau uses in his \emph{Elementary Number Theory}
\cite[p.\ 14]{MR0092794},
and it will be useful to us.
Since the product $ab$ of any two counting-numbers $a$ and $b$ 
is a common multiple of them,
$a$ and $b$ have a \textbf{least common multiple,} denoted by
\begin{equation*}
  \lcm(a,b).
\end{equation*}

\begin{theorem}\label{thm:lcm}
  The least common multiple of any two counting-numbers
measures every common multiple.
\end{theorem}

\begin{proof}
  The remainder of a common multiple of $a$ and $b$
after measurement by $\lcm(a,b)$
is itself a common multiple of $a$ and $b$,
so it must be $0$.
\end{proof}

\begin{corollary}\label{cor:lcm}
  For any counting-numbers $a$ and $b$,
their every common measure measures $ab/\lcm(a,b)$,
which itself is $\gcd(a,b)$.
\end{corollary}

\begin{proof}
Note first that $ab/\lcm(a,b)$
is a common measure of $a$ and $b$,
since for example $\lcm(a,b)/b$ is an integer and
\begin{equation*}
  \frac{ab}{\lcm(a,b)}\cdot\frac{\lcm(a,b)}b=a.
\end{equation*}
For any common measure $c$ of $a$ and $b$,
$ab/c$ is a common multiple of $a$ and $b$, so
\begin{align*}
  \lcm(a,b)&\bigdivides\frac{ab}c,&
c&\bigdivides\frac{ab}{\lcm(a,b)}.
\end{align*}
Letting $c=\gcd(a,b)$,
by \Theorem{thm:|=><}
we conclude that the common measure $ab/\lcm(a,b)$ of $a$ and $b$
is greater than the greatest common measure,
and so the two measures are equal.
\end{proof}

\chapter{Analogy}

\section{Congruence}

Gauss defined the terminology and notation of 
\emph{modulus} and \emph{congruence} at the beginning of the 
\emph{Disquisitiones Arithmeticae}
\cite{Gauss-Latin,Gauss}.
In $\Z$, with respect to a given element $n$ of $\N$ as a \textbf{modulus}
(\enquote{little measure} in Latin),
we define the relation of \textbf{congruence} by
\begin{equation*}
  a\equiv b\iff n\divides a-b.
\end{equation*}
If we need to make $n$ explicit, instead of just $a\equiv b$
we write
\begin{equation*}
  a\equiv b\pmod n.
\end{equation*}
Gauss does not use the following notation;
but,
assuming we have verified that congruence \emph{modulo} $n$
is indeed an equivalence relation,
we may denote the congruence class of any $k$ by $[k]$,
and then we may define
\begin{equation*}
  \Zmod=\{[x]\colon x\in\Z\},
\end{equation*}
the set of congruence classes \emph{modulo} $n$.

We prove now that $\Zmod$ is a ring with precisely $n$ distinct elements,
namely $[0]$, \dots, $[n-1]$.

\begin{theorem}\label{thm:Zn}
For all $n$ in $\N$,
\begin{gather*}
  \Zmod=\{[x]\colon0\leq x<n\},\\
\size{\Zmod}=n.
\end{gather*}
\end{theorem}

\begin{proof}
The first equation follows from the Division Theorem.
For the second equation,
if $0\leq a<b<n$, then $0<b-a<n$, so $n\ndivides b-a$,
and so $a\not\equiv b\pmod n$.
\end{proof}

\begin{theorem}\label{thm:+.}
For all $n$ in $\N$,
for all $a$, $b$, $c$, and $d$ in $\Z$,
if, \emph{modulo} $n$,
\begin{equation*}
a\equiv c\And b\equiv d,
\end{equation*}
then
\begin{equation*}
a+b\equiv c+d\And ab\equiv cd.
\end{equation*}
\end{theorem}

This means the following definitions are valid on $\Zmod$:
\begin{align*}
[x]+[y]&=[x+y],&
[x]\cdot[y]&=[xy].	
\end{align*}
Then the identies \eqref{eqn:monoid}, \eqref{eqn:group},
and \eqref{eqn:dist} that make $\Z$ a ring
must be true in $\Zmod$ as well, so this is a ring.

I said on page \pageref{one-way}
that one can define addition and multiplication on $\N$
by means of the Recursion Theorem.
However, the inductive property of $\N$ alone suffices for the definition,
as Landau shows implicitly in
\emph{Foundations of Analysis} \cite[I, \S\S2, 4]{MR12:397m}.
If we accept Landau's proofs, then,
since $\Zmod$ also has the inductive property\label{Fermat}
(and we shall use it in proving Fermat's Theorem on page \pageref{thm:Fermat}),
we automatically obtain \Theorem{thm:+.}.

\section{Prime numbers}

In any ring,
the elements with reciprocals are called \textbf{units.}
The units of a ring compose an abelian group with respect to multiplication,
and if the ring is $R$,
the group of units can be denoted by
\begin{equation*}
  \units R,
\end{equation*}
where the superscript $\times$ is a multiplication sign.
The ring $R$ is a field if and only if $\units R=R\setminus\{0\}$.

Two integers are called \textbf{prime to one another}
(or \emph{relatively prime,} or \emph{co-prime}) 
if their greatest common divisor is $1$.

By \eqref{eqn:lin}, \emph{modulo} $n$,
\begin{equation*}
  x\equiv y\implies\gcd(x,n)=\gcd(y,n).
\end{equation*}
Thus the following makes sense.

\begin{theorem}\label{thm:Znx}
  $\units{\Zmod}=\{[x]\in\Zmod\colon\gcd(x,n)=1\}$.
\end{theorem}

\begin{proof}
If $[a]\in\units{\Zmod}$, so that, \emph{modulo} $n$, the congruence
\begin{equation}\label{eqn:ax=1}
 ax\equiv1 
\end{equation}
is soluble,
then
\begin{equation}
  \label{eqn:gcd(a,n)=1}
  \gcd(a,n)=1
\end{equation}
since $\gcd(a,n)$,
\begin{compactitem}
  \item
measuring $a$, measures $ax$;
\item
measuring $n$, measures $ax-1$.
\end{compactitem}
Conversely, if \eqref{eqn:gcd(a,n)=1}, then by B\'ezout's Lemma, 
the equation
\begin{equation*}
  ax+ny=1
\end{equation*}
is soluble,
so \eqref{eqn:ax=1} is soluble.
\end{proof}

By definition,
the \textbf{Euler phi-function} on $\N$ is such that,
for every $n$ greater than $1$,
$\euphi(n)$ is the number of counting numbers
less than $n$ that are prime to $n$.
Symbolically,
\begin{equation*}
  \euphi(n)=\size{\{x\in\N\colon x\leq n\And\gcd(x,n)=1\}}.
\end{equation*}
We can replace the requirement $x\leq n$
with $x<n$ unless $n=1$.
By Theorems \ref{thm:Zn} and \ref{thm:Znx},
\begin{equation}\label{eqn:Znx}
  \euphi(n)=\size{\units{\Zmod}}.
\end{equation}
We shall show how to calculate this number
in \Theorems{thm:phi(p^n)} and \ref{thm:phi(km)}.

In any ring $R$, two nonzero elements $a$ and $b$ are \textbf{associates}
if the equation $ax=b$ is soluble by a unit.
Being associated this way is an equivalence relation.
A nonzero non-unit is called \textbf{irreducible}
if its only factors are units and associates.
Thus if a nonzero element $\pi$ of a ring $R$ is irreducible, this means
\begin{gather*}
  \pi\notin\units R,\\
  \pi=ab\And b\notin\units R\implies a\in\units R.
\end{gather*}
Euclid refers to each positive irreducible of $\Z$
as \gr{pr~wtos} \enquote{first,} 
or in Anglicized Latin \textbf{prime,}
because the irreducibles in $\N$
are first in measuring (${}\divides{}$).
Here it is worthwhile to recall from page \pageref{arithmos}
that $1$ is not an \gr{>arijm'os}.
By the well-ordering of $\N$,
along with its relation to measuring given by \Theorem{thm:|=><},
every element has a \textbf{prime factorization,}
meaning it can be written as a product of primes.
Even $1$ is the product of the empty set of primes.

\begin{theorem}\label{thm:field}
The ring $\Zmod$ is a field if and only if $n$ is prime.
\end{theorem}

\begin{proof}
There are three possibilities for $n$.
\begin{asparaenum}
  \item
Having but a single element, $\Zmod[1]$ is not a field,
since $1\neq0$ in every field.
\item
If $a>1$ and $b>1$,
then, \emph{modulo} $ab$,
$a\not\equiv0$, but $ab\equiv0$,
so $a$ has no inverse in $\Zmod[ab]$,
and this cannot be a field.
\item
For all primes $p$,
by \Theorem{thm:Znx}, 
\begin{equation*}
 \units{\Zmod[p]}=\{[x]\in\Zmod[p]\colon0<x<p\}=\Zmod[p]\setminus\{0\}.\qedhere 
\end{equation*}
\end{asparaenum}
\end{proof}

To emphasize that it is a field,
we shall write $\Zmod[p]$ as
\begin{equation*}
  \F[p].
\end{equation*}

The following is Proposition 30 of Book \textsc{vii} of the \emph{Elements.}

\begin{Euclem}\label{thm:Euc-2} 
In $\Z$, for all primes $p$,
\begin{equation}\label{eqn:p|ab}
  p\divides ab\And p\ndivides a\implies p\divides b.
\end{equation}
\end{Euclem}

\begin{proof}[Proof from \Theorem{thm:field}.]
  We can rewrite \eqref{eqn:p|ab}
in terms of congruence \emph{modulo} $p$:
\begin{equation}\label{eqn:Zp-field}
  ab\equiv0\And a\not\equiv0\implies b\equiv0.
\end{equation}
This is true since $\F[p]$ is a field.
\end{proof}

\begin{proof}[Proof from B\'ezout's Lemma.]
By hypothesis, $\gcd(p,a)=1$, 
so by B\'ezout's Lemma we can solve the equations
\begin{gather*}
  px+ay=1,\\
pbx+aby=b.
\end{gather*}
Since $p$ divides the left member of the latter equation,
it must divide $b$.
\end{proof}

Before continuing, let us note some applications of Euclid's Lemma.

\begin{Fun}\label{thm:Fun}
Prime factorizations of counting-numbers are unique.  
\end{Fun}

\begin{proof}
Suppose $p_1\cdots p_m=q_1\cdots q_n$,
where each $p_i$ or $q_j$ is prime, and
\begin{align*}
  p_1\leq\dots&\leq p_m,&q_1\leq\dots&\leq q_n.
\end{align*}
Then $p_1\divides q_1\cdots q_n$,
so by Euclid's Lemma, 
$p_1$ divides one of the $q_j$
and is therefore equal to it.
Likewise, $q_1$ is equal to some $p_i$.
Then
\begin{equation*}
  p_1=q_j\geq q_1=p_i\geq p_1,
\end{equation*}
so $p_1=q_1$.  Now $p_2=q_2$, and so forth, and $m=n$.
\end{proof}

In some rings, irreducible factorizations exist,
but they are not unique.
Thus for example when we define
\begin{equation}\label{eqn:-5}
\Z[\surd{-5}]=  \{x+y\surd{-5}\colon(x,y)\in\Z\times\Z\}
\end{equation}
this is a sub-ring of $\C$ in which
\begin{equation*}
  2\cdot3=6=(1+\surd{-5})(1-\surd{-5}).
\end{equation*}
The two different factorizations of $6$ are irreducible,
as one can prove by means of the multiplicative function 
$z\mapsto\abs z^2$ from $\Z[\surd{-5}]$ to $\N\cup\{0\}$.
However, none of the irreducible factors 
$2$, $3$, and $1\pm\surd{-5}$ is prime.
Apparently the term ``ring'' comes from examples like $\Z[\surd{-5}]$, 
where, in squaring $\surd{-5}$, we \emph{circle back} to $\Z$.

\begin{theorem}\label{thm:phi(p^n)}
  If $p$ is prime and $n\in\N$, then
  \begin{equation*}
    \euphi(p^n)=p^n-p^{n-1}.
  \end{equation*}
\end{theorem}

\begin{proof}
We use that
\begin{equation*}
    \euphi(p^n)
=p^n-\size{\{[x]\in\Zmod[p^n]\colon\gcd(p^n,x)>1\}}.
\end{equation*}
By Euclid's Lemma, the only prime factor of $p^n$ is $p$, so
\begin{equation*}
  \gcd(p^n,x)>1\iff p\divides x.
\end{equation*}
This yields the claim.
\end{proof}

By \Theorem{thm:lcm},
numbers are congruent \emph{modulo} $k$ and $m$
if and only if they are congruent \emph{modulo} $\lcm(k,m)$.
This gives uniqueness in the following.


\begin{CRT}
  If $\gcd(k,m)=1$, then every system
  \begin{align*}
    z&\equiv a\pmod k,&z&\equiv b\pmod m
  \end{align*}
has a solution that is unique \emph{modulo} $km$.
\end{CRT}

\begin{proof}
  The desired solution is
  \begin{equation*}
    z\equiv amy+bkx\pmod{km},
  \end{equation*}
where $kx+my=1$.
\end{proof}

\begin{corollary}
If $\gcd(k,m)=1$,
then the ring homomorphism
\begin{equation}\label{eqn:xxx}
[x]\mapsto([x],[x])  
\end{equation}
from $\Zmod[km]$ to $\Zmod[k]\times\Zmod[m]$
is an isomorphism.
\end{corollary}

\begin{theorem}\label{thm:phi(km)}
If $\gcd(k,m)=1$, then
\begin{equation*}
  \euphi(km)=\euphi(k)\cdot\euphi(m).
\end{equation*}
\end{theorem}

\begin{proof}
Restricted to $\units{\Zmod[k]}$,
The isomorphism in \eqref{eqn:xxx}
is surjective onto $\units{\Zmod[k]}\times\units{\Zmod[m]}$
by Euclid's Lemma: if $\gcd(k,x)$ and $\gcd(m,x)$ are both $1$,
then $\gcd(km,x)$ must be $1$.
\end{proof}

The property \eqref{eqn:Zp-field} of $\F[p]$
that is analogous with \eqref{eqn:p|ab}
can be written as
\begin{equation*}
xy=0\And x\neq0\implies y=0  
\end{equation*}
for an arbitrary field.
A \emph{ring} where this holds along with $0\neq1$
is called an \textbf{integral domain.}
All fields are integral domains,
but $\Z$ is an integral domain that is not a field.
The example $\Zmod[4]$ is not even an integral domain.

\begin{theorem}\label{thm:fin-id-field}
Every finite integral domain is a field.
\end{theorem}

\begin{proof}
Let $R$ be a finite integral domain and $a\in R\setminus\{0\}$.
The function $x\mapsto ax$ having domain $R\setminus\{0\}$
has range included in $R\setminus\{0\}$,
since if $b\neq0$ in $R$, then $ab\neq0$.
Similarly, the function is injective:
\begin{equation*}
ab=ac\implies a(b-c)=0\implies b-c=0\implies b=c.
\end{equation*}
By the Pigeonhole Principle,\label{PP}
the function must be surjective.
In particular, the equation $ax=1$ must have a solution.
\end{proof}

By analogy with the rules for an integral domain,
and especially considering Euclid's Lemma,
we say a nonzero element $\pi$ of an arbitrary ring $R$ is \textbf{prime}
if
\begin{gather*}
  \pi\notin\units R,\\
\pi\divides xy\And\pi\ndivides x\implies\pi\divides y.
\end{gather*}
In these terms,
Euclid's Lemma is that positive irreducibles of $\Z$ are prime
and that, when $p$ is such, then $\Zmod[p]$ is an integral domain.
There is a partial converse that holds more generally:

\begin{theorem}
In an integral domain,
primes are irreducible.
\end{theorem}

\begin{proof}
  In an integral domain,
suppose a prime $\pi$ is equal to $ab$.
Then $\pi\divides ab$, so we may assume $\pi\divides a$,
and so there is $x$ such that $\pi x=a$.
Then
\begin{gather*}
  \pi xb=ab=\pi,\\
xb=1
\end{gather*}
since we are in an integral domain.
In particular, $b$ is a unit.
\end{proof}

The proof fails for arbitrary rings.
Thus in $\Zmod[6]$, $2$ is prime,
since the multiples of $2$ are $0$, $2$, and $4$,
and these are products as follows:
\begin{align*}
&  \begin{aligned}
  0&=2\cdot3\\
&=3\cdot4\\
&=0x,
\end{aligned}&
\begin{aligned}
2&=2\cdot4\\
&=4\cdot5,                 
\end{aligned}&
&\begin{aligned}
4&=2\cdot2\\
&=4\cdot4\\
&=4\cdot5,                 
\end{aligned}
\end{align*}
and $2$ measures a factor in each case.
However, since $2=2\cdot4$,
it is not irreducible.

\section{Polynomials}

It will now be useful to define
\begin{equation*}
\upomega=\{0,1,2,\dots\}=\{0\}\cup\N=\{x\in\Z\colon x\geq0\},
\end{equation*}
the set of \textbf{natural numbers}
or \textbf{non-negative integers.}
(Here $\upomega$ is the minuscule Greek omega.)

For any field $K$,
we can form an infinite-dimensional vector-space over $K$
having the formal basis $\{X^n\colon n\in\upomega\}$.
An arbitrary element $f$ of this space can be written as
\begin{equation*}
  \sum_{n\in\upomega}f_nX^n,
\end{equation*}
where $f_n=0$ for all but finitely many $n$.
The least $n$ such that $f_n\neq0$
is called the \textbf{degree} of $f$ and can be denoted by
\begin{equation*}
  \deg(f).
\end{equation*}
Then $f_{\deg(f)}$ is the \textbf{leading coefficient} of $f$.
For completeness, we may define
\begin{equation*}
\deg(0)=-\infty.
\end{equation*}
We can define a multiplication on the whole space 
by first setting
\begin{equation*}
  X^k\cdot X^m=X^{k+m},
\end{equation*}
then extending to ensure commutativity,
associativity, and distributivity.
This gives
\begin{equation*}
  fg=\sum_{n\in\upomega}\sum_{i+j=n}f_ig_jX^n.
\end{equation*}
This operation makes the space into the ring
\begin{equation*}
  K[X]
\end{equation*}
of \textbf{polynomials in $X$ over} $K$.
There is strong analogy between $K[X]$ and $\Z$.
The ring $K[X]$ is not ordered,
but the degrees of its elements are.

\begin{Division}[for polynomials]\label{thm:div-pol}
For all fields $K$,
for all $f$ in $K[X]$ and $g$ in $K[X]\setminus\{0\}$,
there are some $q$ and $r$ in $K[X]$ such that
\begin{equation*}
f=gq+r\And\deg(r)<\deg(g).
\end{equation*}
Moreover, $\deg(r)$ is uniquely determined by $f$ and $g$.
\end{Division}

\begin{proof}
Follow the pattern of the proof of \Theorem{thm:div},
letting $r$ be an element of $\{f-g\cdot\xi\colon\xi\in K[X]\}$
having minimal degree.
If $\deg(r)\geq\deg(g)$,
then the set also contains
\begin{equation*}
  r-\frac{r_{\deg(r)}}{g_{\deg(g)}}\cdot g,
\end{equation*}
whose degree is strictly less than $\deg(r)$.
\end{proof}

Of two polynomials,
at least one of which is not $0$,
there is a common divisor of maximal degree.
We can find such a common divisor
by performing the Euclidean Algorithm;
and then every common divisor will divide it,
as follows.

\begin{Bezout}[for polynomials]
For all fields $K$,
for all $f$ and $g$ in $K[X]$, not both $0$,
for every element $h$ of the set
\begin{equation*}
\{f\cdot\xi+g\cdot\eta\colon(\xi,\eta)\in K[X]\times K[X]\}
\end{equation*}
having minimal degree,
\begin{compactenum}[(i)]
\item
$h\divides f$ and $h\divides g$;
\item
if $k\divides f$ and $k\divides g$,
then $k\divides h$.
\end{compactenum}
\end{Bezout}

The polynomial $h$ in the theorem is a 
greatest common divisor of $f$ and $g$
and is unique up to multiplication by a nonzero scalar.
As we could prove Euclid's Lemma from B\'ezout's Lemma
in the original case of integers,
so we can do it for polynomials:

\begin{Euclem}[for polynomials]
For every field $K$,
every irreducible of $K[X]$ is prime.
\end{Euclem}

\section{Quotients}

The theory of congruence carries over to an arbitrary ring $R$.
If $a$ is a nonzero element of this ring,
two elements $b$ and $c$ can be called congruent \emph{modulo} $a$
if $a\divides b-c$.
The set of congruence classes of elements of $R$
is then denoted by
\begin{equation}\label{eqn:R/(a)}
  R/(a).
\end{equation}
Thus $\Zmod$ becomes $\Z/(n)$.

It is not important for us,
but the notation in \eqref{eqn:R/(a)} can be analyzed,
and $(a)$ is the set of elements of $R$ that are congruent to $0$;
this set is just $\{ax\colon c\in R\}$.
Thus, \emph{modulo} $a$,
\begin{equation*}
  b\equiv c\iff b-c\in(a).
\end{equation*}
Then $R/(a)$ is the \textbf{quotient} of $R$ by $(a)$,
which itself is called an \textbf{ideal} of $R$,
because it is closed under addition
and under multiplication by elements of $R$.
More precisely, $(a)$ is a \textbf{principal ideal,}
because it consists of the multiples of a single element.
In any ring, such as $\Z$ or $K[X]$ where $K$ is a field,
in which B\'ezout's Lemma is true,
all ideals are principal;
but in the ring $\Z[\surd{-5}]$ defined in \eqref{eqn:-5}
on page \pageref{eqn:-5},
when we define
\begin{multline*}
  (1+\surd{-5},1-\surd{-5})\\
=\{(1+\surd{-5})x+(1-\surd{-5})y\colon{}\\
(x,y)\in\Z[\surd{-5}]\times\Z[\surd{-5}]\},
\end{multline*}
this is a non-principal ideal,
as again one can show by means of $z\mapsto\abs z$.

Corresponding to \Theorem{thm:field}, 
by the same proof,
we have the following.

\begin{theorem}
For all fields $K$,
for all nonzero $f$ in $K[X]$,
\begin{equation*}
K[X]/(f)\text{ is a field}\iff f\text{ is irreducible.}
\end{equation*}
\end{theorem}

We looked at the example of $\C$ on page \pageref{C};
now we can write
\begin{equation*}
  \C=\R[X]/(X^2+1).
\end{equation*}
However, over $\F[2]$,
\begin{equation*}
  X^2+1=(X^2-1)=(X+1)(X-1)=(X+1)^2,
\end{equation*}
so it is not irreducible.
Nonetheless, $X^2+X+1$ is irreducible over $\F[2]$,
since it can factorize only as $(X-a)(X-b)$,
where $a$ and $b$ are zeros of the polynomial;
and there are no such zeros in $\F[2]$.
If we denote the congruence class of $X$ in $\F[2][X]$
\emph{modulo} $X^2+X+1$ by $\alpha$, then
\begin{equation*}
  \alpha^2+\alpha+1=0.
\end{equation*}
Thus $\alpha^2=\alpha+1$.
We can write
\begin{equation*}
  \F[2](\alpha)=\F[2][X]/(X^2+X+1).
\end{equation*}
Here $X^2+X+1$ is a \textbf{minimal polynomial} of $\alpha$ over $\F[2]$,
since $\alpha$ is a root of it, 
but not of any nonzero polynomial of less degree,
since if $\alpha$ is also a root of $f$,
then $\alpha$ is a root of $\gcd(X^2+X+1,f)$,
so this is not $1$,
so it must be $X^2+X+1$, since this is irreducible.

As a vector space over $\F[2]$, the field is $\F[2]\oplus\F[2]\alpha$.
Addition and multiplication in $\F[2](\alpha)$
are as in Figure \ref{fig:F4}.
\begin{figure}

  \begin{gather*}
      \begin{array}{|c|cccc|}\hline
        +&0&1&\alpha&\alpha+1\\\hline
        0&0&1&\alpha&\alpha+1\\
        1&1&0&\alpha+1&\alpha\\
        \alpha&\alpha&\alpha+1&0&1\\
        \alpha+1&\alpha+1&\alpha&1&0\\\hline
      \end{array}\\
           \begin{array}{|c|ccc|}\hline
             \times&1&\alpha&\alpha+1\\\hline
             1&1&\alpha&\alpha+1\\
             \alpha&\alpha&\alpha+1&1\\
             \alpha+1&\alpha+1&1&\alpha\\\hline
           \end{array}
         \end{gather*}
         
  \caption{Arithmetic in $\F[2][\alpha]$ where $\alpha^2=\alpha+1$}
  \label{fig:F4}
\end{figure}
Note that $\units{\F[2][\alpha]}\cong\Zmod[3]$.
Also
\begin{equation*}
  (X-\alpha)(X-\alpha-1)
=X^2+X+1,
\end{equation*}
and thus
\begin{multline*}
  \prod_{t\in\F[2][\alpha]}(X-t)=X(X-1)(X^2+X+1)\\
=X(X^3-1)=X^4-X.
\end{multline*}
Still over $\F[2]$, there are four polynomials of degree $3$
that do not have the factor $X$, namely
\begin{align*}
  &X^3+1,&
&X^3+X+1,&
&X^3+X^2+1,&
&X^3+X^2+X+1.
\end{align*}
The first and last have factor $X+1$;
the middle two do not, since $1$ is not a zero of them,
and therefore they are irreducible.
We can now understand $\F[2]/(X^3+X+1)$ as $\F[2](\beta)$,
where
\begin{equation*}
  \beta^3=\beta+1.
\end{equation*}
As a vector space, the field is $\F[2]\oplus\F[2]\beta\oplus\F[2][\beta^2]$,
with eight elements.
To understand multiplication in the field,
we may observe that the powers of $\beta$ are thus:
\begin{equation*}
  \begin{array}{c|cccccccc}
      k&0&1&2&3&4&5&6&7\\\hline
\beta^k&1&\beta&\beta^2&\beta+1&\beta^2+\beta&\beta^2+\beta+1&\beta^2+1&1
  \end{array}
\end{equation*}
Hence an abbreviated multiplication table
can be written out as in Figure \ref{fig:F8}.
\begin{sidewaysfigure}
  \begin{equation*}
\renewcommand{\arraystretch}{2.7}
    \begin{array}{|c|cccccc|}\hline
\times&\beta&\beta^2&\beta+1&\beta^2+\beta&\beta^2+\beta+1&\beta^2+1\\\hline
\beta&\beta^2&\beta+1&\beta^2+\beta&\beta^2+\beta+1&\beta^2+1&1\\
\beta^2&\beta+1&\beta^2+\beta&\beta^2+\beta+1&\beta^2+1&1&\beta\\
\beta+1&\beta^2+\beta&\beta^2+\beta+1&\beta^2+1&1&\beta&\beta^2\\
\beta^2+\beta&\beta^2+\beta+1&\beta^2+1&1&\beta&\beta^2&\beta+1\\
\beta^2+\beta+1&\beta^2+1&1&\beta&\beta^2&\beta+1&\beta^2+\beta\\
\beta^2+1&1&\beta&\beta^2&\beta+1&\beta^2+\beta&\beta^2+\beta+1\\\hline
    \end{array}
  \end{equation*}
  \caption{Multiplication in $\F[2][\beta]$ where $\beta^3=\beta+1$}
  \label{fig:F8}
\end{sidewaysfigure}

For one more example,
we note that $X^2+1$ is irreducible over $\F[3]$,
since it has no zero there.
Then $\F[3][X]/(X^2+1)=\F[3](\gamma)$, where
\begin{equation*}
  \gamma^2=-1,
\end{equation*}
and so $\gamma^4=1$.
However, $\gamma+1$ has the following powers.
\begin{equation*}
\begin{array}{c|*5c}
             k & 0& 1     & 2    & 3     & 4\\\hline
   (\gamma+1)^k & 1&\gamma+1&-\gamma&1-\gamma&-1\\
(\gamma+1)^{4+k}&-1&-(\gamma+1)&\gamma&\gamma-1&1
\end{array}
\end{equation*}
Writing $\gamma+1$ as $\delta$, we have
$\gamma=\delta-1$, so
\begin{gather*}
  0=(\delta-1)^2+1=\delta^2+\delta-1,\\
\F[3](\gamma)=\F[3](\delta)=\F[3][X]/(X^2+X-1).
\end{gather*}
In fact
\begin{multline*}
  X^8-1=(X-1)(X+1)(X^2+1)(X^4+1)\\
	(X-1)(X+1)(X^2+1)(X^2+X-1)(X^2-X-1)
      \end{multline*}
      over $\F[3]$.
Any of the three irreducible polynomials $X^2+1$
and $X^2\pm X-1$ will give us $\F[9]$.



If $f$ in $K[X]$ is irreducible of degree $n$,
then, as a vector space over $K$, $K[X]/(f)$
is isomorphic to the space with basis\label{K[X]/(f)}
\begin{equation*}
  \{X^k\colon0\leq k<n\}.
\end{equation*}
In particular, in case $K$ is $\F$,
the space has finite size $p^n$;
see \Theorem{thm:p^n}.
We shall show that such irreducibles $f$ exist for all positive $n$,
and moreover, finite fields arise in no other way.

\chapter{Characterization}

\section{Characteristic}

Every commutative ring $R$ contains all of the sums
\begin{equation*}
\underbrace{1+\dots+1}_n,
\end{equation*}
where $n\in\N$.
If the sum is $0$ for some $n$,
then the least such $n$ is called the \textbf{characteristic} of $R$, or
\begin{equation*}
\Char R.
\end{equation*}
If $R$ is an integral domain, then $\Char R$ must be a prime $p$.
In this case, we may suppose $\F\included R$;
and then $R$ is a vector space over $\F$.

\begin{theorem}\label{thm:p^n}
The size of every finite field is a prime power.
\end{theorem}

\begin{proof}
If $K$ is a finite field,
then, by what we have just seen,
$K$ is a vector space over some $\F$.
As such, $K$ has a basis of some finite size $n$;
and then, as at the end of the last section, $\size K=p^n$.
\end{proof}

We are going to prove Fermat's Theorem
by induction, as mentioned on page \pageref{Fermat}.
By recursive definition,
\begin{align*}
  0!&=1,&(n+1)!&=n!\cdot(n+1).
\end{align*}
If $0\leq k\leq n$, then by non-recursive definition,
\begin{equation*}
  \binom nk=\frac{n!}{k!\cdot(n-k)!}.
\end{equation*}
This is the number of $k$-element subsets of a set of size $n$.
If one accepts this, then $\binom nk$ is automatically a counting-number.
Alternatively, one may observe
\begin{align*}
  \binom n0&=1,&\binom nn&=1,
\end{align*}
while if $0\leq k<n$, then by computation
\begin{equation*}
  \binom nk+\binom n{k+1}=\binom{n+1}{k+1},
\end{equation*}
so by induction, each $\binom nk$ is a counting-number.
One may also prove by induction the \textbf{Binomial Theorem,}
\begin{equation*}
  (x+y)^n=\sum_{k=0}^n\binom nkx^{n-k}y^k,
\end{equation*}
and note that the coefficients must be counting-numbers.

\begin{lemma}\label{lem:p}
When $0<k<p$, then
\begin{equation*}
p\left|\binom pk.\right.
\end{equation*}
\end{lemma}

\begin{proof}
The \enquote{intuitive} proof is that,
if $A$ is a proper nonempty subset of $\Zmod[p]$,
and $\sigma$ is the permutation $x\mapsto x+1$ of this set,
then the sets $\sigma^n[A]$ all differ 
as $n$ itself ranges over $\Zmod[p]$;
thus the number of subsets of $\Zmod[p]$ having the size of $A$
must be divisible by $p$.

The more formal proof is that, first of all,
since $\binom pk$ is a whole number,
\begin{equation*}
k!\cdot(p-k)!\divides(p-1)!\cdot p.
\end{equation*}
By Euclid's Lemma, since $0<k<p$ and $p$ is prime,
\begin{equation*}
p\ndivides k!\cdot(p-k)!.
\end{equation*}
By the Fundamental Theorem (page \pageref{thm:Fun}),
we must therefore have
\begin{equation*}
	k!\cdot(p-k)!\divides(p-1)!.\qedhere
\end{equation*}
\end{proof}

\begin{theorem}\label{thm:dream}
  In any field having characteristic $p$,
  \begin{equation*}
    (x+y)^p=x^p+y^p.
  \end{equation*}
\end{theorem}

\begin{proof}
  This is an immediate consequence of the Binomial Theorem
and Lemma \ref{lem:p}.
\end{proof}

\begin{FT}\label{thm:Fermat}
For all primes $p$ and all $a$ in $\Z$,
if $p\ndivides a$, then
\begin{equation*}
a^{p-1}\equiv1\pmod p.
\end{equation*}
\end{FT}

\begin{proof}
The claim is that,  in $\F$,
\begin{equation*}
a\neq0\implies a^{p-1}=1,
\end{equation*}
or equivalently, for all $a$ in $\F$,
\begin{equation}\label{eqn:a^p=a}
a^p=a.
\end{equation}
We can prove this by induction.
Immediately \eqref{eqn:a^p=a} holds when $a=1$.
Suppose \eqref{eqn:a^p=a} is true when $a=b$, so $b^p=b$.
By \Theorem{thm:dream},
\begin{equation*}
(b+1)^p
=b^p+1=b+1
\end{equation*}
in $\F$,
so \eqref{eqn:a^p=a} is true when $a=b+1$.
By induction, \eqref{eqn:a^p=a} is true for all $a$ in $\F$.
\end{proof}

We can also derive Fermat's Theorem as a special case of Euler's Theorem below.

The \textbf{order} of a finite group is just its size.
The \textbf{order} of an element $a$
is the least non-negative exponent $n$ such that $a^n=1$ in the group;
but this is just the order of the subgroup
$\{a^n\colon n\in\Z\}$, which is denoted by
\begin{equation*}
  \gpgen a,
\end{equation*}
of the original group.  So the order of $a$ is $\size{\gpgen a}$;
we just write this as
\begin{equation*}
  \ord a.
\end{equation*}


\begin{LT}
  In any finite group,
the order of any element divides the order of the group.
\end{LT}

\begin{proof}
Let $G$ be the group and $a$ the element,
and let $n=\ord a$.
We can construct a matrix
\begin{equation*}
  \begin{pmatrix}
     1&      a&      a^2&\cdots&a^{n-1}\\
b_1   &   b_1a&    b_1a^2&\cdots&b_1a^{n-1}\\
\vdots& \vdots&   \vdots&      &\vdots\\
b_{k-1}&b_{k-1}a&b_{k-1}a^2&\cdots&b_{k-1}a^{n-1}
  \end{pmatrix}
\end{equation*}
with entries from $G$,
line by line, left to right within each line,
so that every element of $G$ appears exactly once.
In particular, $\ord G=nk$.
\end{proof}


\begin{ET}\label{thm:ET}
For all $n$ in $\N$, for all $a$ in $\Z$, if
\begin{equation*}
  \gcd(a,n)=1,
\end{equation*}
then
\begin{equation*}
a^{\euphi(n)}\equiv1\pmod n.
\end{equation*}
\end{ET}

\begin{proof}
By \Theorem{thm:Znx} and \eqref{eqn:Znx}, 
the claim is a consequence of Lagrange's Theorem.
\end{proof}

\section{Units of finite fields}

If $K$ is a field included in a ring $R$,
and $a\in R$,
then there is a homomorphism
\begin{equation*}
  f\mapsto f(a)
\end{equation*}
from $K[X]$ to $R$ that is uniquely determined by the requirement that
$f(a)$ be $a$ when $f$ is $X$.
If $f(a)=0$, then $a$ is called a \textbf{root} or \textbf{zero} of $f$.
By Fermat's Theorem,
every element of $\F$ is a root of the polynomial
\begin{equation*}
  X^p-X.
\end{equation*}
Using Lagrange's Theorem,
we generalized Fermat's Theorem to Euler's Theorem.
A similar generalization will be that,
if $K$ is a finite field of size $q$, 
then every element of $K$ is a root of the polynomial
\begin{equation*}
  X^q-X.
\end{equation*}
We shall use this to construct and characterize finite fields.

\begin{theorem}\label{thm:deg}
For any field $K$,
for any $f$ in $K[X]\setminus\{0\}$,
\begin{equation*}
\size{\{x\in K\colon f(x)=0\}}\leq\deg(f).
\end{equation*}
\end{theorem}

\begin{proof}
Suppose $f(\alpha)=0$.
By the Division Theorem for polynomials (\Theorem{thm:div-pol}),
for some $g$ in $K[X]$,
\begin{equation}\label{eqn:f=(x-a)g}
f=(X-\alpha)\cdot g.
\end{equation}
If $\beta\neq\alpha$ and $f(\beta)=0$, then $g(\beta)=0$.
Thus $f$ can have at most one more zero than $g$ has.
If $\deg(g)=0$, then $g$ has no zeros.
By induction, the proof is complete.
\end{proof}

\begin{lemma}\label{lem:lcm}
Suppose an abelian group (written additively) 
has elements $g$ and $h$ of orders $a$ and $b$ respectively.
\begin{compactenum}
  \item
If $\gcd(a,b)=1$, then $g+h$ has order $ab$.
\item
In general,
$\gcd(a,b)\cdot g+h$ has order $\lcm(a,b)$.
\end{compactenum}  
\end{lemma}

\begin{proof}
We have $ab(g+h)=bag+abh=0+0=0$.
Conversely, if $n(g+h)=0$,
then $ng$, which is $-nh$, belongs to both $\gpgen g$ and $\gpgen h$.
If $\gcd(a,b)=1$,
then by Lagrange's Theorem,
$\gpgen a$ and $\gpgen b$ have only the trivial subgroup in common,
so $n$ must be a common multiple of $a$ and $b$,
and here this just means $ab\divides n$.
This yields the first claim.
For the more general claim,
we note that $\gcd(a,b)g$ has order $a/\gcd(a,b)$,
which is prime to $b$,
and the product of the two orders is $\lcm(a,b)$.
\end{proof}

\begin{theorem}\label{thm:cyclic}
For every finite field $K$,
for some nonzero element $\alpha$ of $K$,
\begin{equation*}
  \units K=\gpgen \alpha.
\end{equation*}
\end{theorem}

\begin{proof}
Suppose $\size K=q$,
and let $\alpha$ be an element of $\units K$ of maximal order.
If $\beta\in\units K$,
then by Lemma \ref{lem:lcm}
the group has an element of order $\lcm(\ord{\alpha},\ord{\beta})$.
This must be $\ord{\alpha}$ by its own maximality,
and so $\ord{\beta}$ must divide $\ord{\alpha}$.
If this order is $m$, then we now have
\begin{equation*}
\units K=\{x\in K\colon x^m=1\}.
\end{equation*}
By \Theorem{thm:deg},
the size $q-1$ of this set is at most $m$.
Also $m\divides q-1$, so $m=q-1$,
and this yields the claim.
\end{proof}

\section{Splitting fields}

We noted on page \pageref{K[X]/(f)} that
if $f$ in $K[X]$ is irreducible of degree $n$,
then the field $K[X]/(f)$
has dimension $n$ as a vector space over $K$.
Moreover, the congruence class of $X$ in the field
must be a root of $f$.
If $K$ is included in some field $L$
that contains a root $\alpha$ of $f$,
we denote by
\begin{equation*}
  K(\alpha)
\end{equation*}
the smallest subfield of $L$ that includes $K$ and contains $a$.
Then $K(a)$ and $K[X]/(f)$ are isomorphic as vector spaces
and indeed as fields,
and there is an isomorphism from $K(\alpha)$ to $K[X]/(f)$ 
that is the identity on $K$
and that takes $\alpha$ to the congruence class of $X$.

If now $K$ and $\alpha$ are as in \Theorem{thm:cyclic},
and $\Char K=p$, while $q=p^n$, then
\begin{equation}\label{eqn:Fp(a)}
  K=\F(\alpha).
\end{equation}
Moreover, $\alpha$ must be a root of an irreducible factor of $X^{q-1}-1$
that has degree $n$.

We shall show that there is always such a factor,
for every $p$ and $n$.

For an arbitrary field $K$,
for any $n$ in $\N$,
for any polynomial $f$ of degree $n$ over $K$,
a \textbf{splitting field} of $f$ over $K$
is a field extending $K$
containing elements $\alpha_k$ such that
\begin{equation*}
  f=\prod_{k<n}(X-\alpha_k).
\end{equation*}

\begin{theorem}
Splitting fields always exist.  
\end{theorem}

\begin{proof}
In the notation just used,
we have seen that $f$ has a root $\alpha$ in some field $K(\alpha)$.
Over this field, as in the proof of \Theorem{thm:deg},
there is a polynomial $g$ such that \eqref{eqn:f=(x-a)g} holds.
Here $g$ may not be irreducible, but it has an irreducible factor,
which has a root $\beta$ in some field $K(\alpha,\beta)$.
Then $f=(X-\alpha)\cdot(X-\beta)\cdot h$ for some $h$,
and so forth.
\end{proof}

If, in its complete factorization in a splitting field,
a polynomial has no repeated factor,
the polynomial is called \textbf{separable.}
To test for separability,
we can take formal derivatives.
The derivative $f'$ of a polynomial $f$
is just what one expects from the rules of calculus.
By formal definition, the map $\xi\mapsto\xi'$ from $K[X]$ to itself
is the unique linear transformation 
that takes $X^n$ to $nX^{n-1}$ when $n\in\N$,
but takes $1$ to $0$.
The multiplication rule
\begin{equation*}
  (fg)'=f'g+fg'
\end{equation*}
holds when $f$ and $g$ are powers of $X$
and therefore, by linearity, for all $f$ and $g$.

\begin{theorem}\label{thm:sep}
A polynomial is separable if and only if it is prime to its derivative.
\end{theorem}

\begin{proof}
  We can write a separable polynomial as $(X-\alpha)^2\cdot g$,
and $X-\alpha$ is a common factor of this and its derivative.

However, if $\alpha$ is not a root of $f$,
then it is not a root of the derivative of $(X-\alpha)\cdot f$,
which is $f+(X-\alpha)\cdot f'$.
Thus a separable polynomial can share no roots with its derivative.
\end{proof}

Over a field of characteristic $p$, 
a polynomial $X^p-a$ is not separable, since its derivative is $0$.
If $b$ is a root of the polynomial, then
\begin{equation*}
  (X-b)^p=X^p-b^p=X^p-a
\end{equation*}
by \Theorem{thm:dream}, so the polynomial has a unique root.
Thus the function $x\mapsto x^p$\label{p-power}
from the field to itself is injective.
If the field is finite, 
then the function must also be surjective,
by the Pigeonhole Principle as on page \pageref{PP}.
In this case, $X^p-a$ is never irreducible.

\begin{theorem}\label{thm:existence}
  For each prime $p$ and counting-number $n$,
there is a field having size $p^n$.
\end{theorem}

\begin{proof}
  Let $q=p^n$.
By \Theorem{thm:sep}, the polynomial $X^q-X$
is separable, since its derivative, $-1$, is a unit.
Let $L$ be a splitting field of the polynomial,
and let
\begin{equation*}
  K=\{x\in L\colon x^q=x\}.
\end{equation*}
Then $\size K=q$.
Moreover, $K$ is a field by \Theorem{thm:dream},
since if $K$ contains $\alpha$ and $\beta$, then
\begin{gather*}
  (\alpha\pm\beta)^q=\alpha^q\pm\beta^q=\alpha\pm\beta,\\
(\alpha\beta)^q=\alpha^q\beta^q=\alpha\beta,
\end{gather*}
and also, if $\alpha\neq0$,
\begin{equation*}
  \alpha^{q-2}\alpha=1,
\end{equation*}
so $K$ is closed under addition, subtraction, multiplication, and inversion.
\end{proof}

\section{Isomorphism}

By what we saw at the beginning of the last section,
if $\alpha$ and $\beta$ are both roots 
of the same irreducible polynomial $f$ over $K$,
then the map from $K(\alpha)$ to $K(\beta)$
that is identical on $K$ and takes $\alpha$ to $\beta$
must be an isomorphism.

We also saw that any finite field can be written as in \eqref{eqn:Fp(a)},
as $\F(\alpha)$.
The field having size $q$,
let $f$ be the irreducible factor of $X^q-X$
of which $\alpha$ is a root.
Any other field of size $q$ contains a root $\beta$ of $f$,
and then the field itself must be $\F(\beta)$,
and this is isomorphic to $\F(\alpha)$.

Thus we have:

\begin{theorem}
  For every prime power, all fields of that size are isomorphic.
\end{theorem}

\enquote{The} field of size $q$ can be called
\begin{equation*}
\F[q].
\end{equation*}

\begin{theorem}\label{thm:m|t}
The finite fields of characteristic $p$
are ordered by inclusion
as the exponents of their sizes are ordered by divisibility.
Thus for all $m$ and $t$ in $\N$,
\begin{equation*}
\F[p^m]\included\F[p^t]\iff m\divides t.
\end{equation*}
\end{theorem}

\begin{proof}
By the same proof as when $K=\F$, 
if $K$ and $L$ are two finite fields
such that $K\included L$, then for some $n$ in $\N$,
\begin{equation*}
\size L=\size K^n.
\end{equation*}
In particular, if $\size K=p^m$,
then $\size L=p^t$ for some $t$, where $m\divides t$.

Suppose conversely $m\divides t$.
Then $t=mk$ for some $k$, and so
\begin{equation*}
	p^t-1=(p^m)^k-1
	=(p^m-1)\cdot n,
\end{equation*}
where
\begin{equation*}
n= (p^m)^{k-1}+\dots+1.
\end{equation*}
Now
\begin{align*}
  X^{p^t}-X
&=X\cdot(X^{p^t-1}-1)\\
&=X\cdot\bigl((X^{p^m-1})^n-1\bigr)\\
&=X\cdot(X^{p^m-1}-1)\cdot\bigl((X^{p^m-1})^{n-1}+\dots+1\bigr)\\
&=X\cdot(X^{p^m-1}-1)\cdot\bigl((X^{p^m-1})^{n-1}+\dots+1\bigr)\\
&=(X^{p^m}-X)\cdot\bigl((X^{p^m-1})^{n-1}+\dots+1\bigr),
\end{align*}
so by the proof of \Theorem{thm:existence},
$\F[p^m]\included\F[p^t]$.
\end{proof}

\chapter{Galois Theory}

On a field of characteristic $p$
the function $x\mapsto x^p$ discussed on page \pageref{p-power}
is an \textbf{endomorphism}
(an injective homomorphism from the field into itself)
by \Theorem{thm:dream}.
If the field is finite, as discussed before, 
the function is therefore an \textbf{automorphism}
(an isomorphism of the field with itself, or a surjective endomorphism),
called the \textbf{Frobenius Automorphism.}
Let us denote it by \fbox{$\upsigma$.}
By Fermat's Theorem, $\upsigma$ is the identity on $\F$.
Indeed, this field can have no nontrivial automorphism,
since the elements of the field are just finite sums of the element $1$.
In any case, $\upsigma$ belongs to the group
\begin{equation*}
  \Aut{\F[p^n]}
\end{equation*}
of automorphisms of $\F[p^n]$.

\begin{theorem}
  For all primes $p$, for all $n$ in $\N$,
  \begin{equation*}
    \Aut{\F[p^n]}=\{\upsigma^i\colon0\leq i<n\}\cong\Zmod.
  \end{equation*}
\end{theorem}

\begin{proof}
We know 
\begin{equation}\label{eqn:uFpn}
\units{\F[p^n]}=\gpgen{\alpha}
\end{equation}
for some $\alpha$ in $\units{\F[p^n]}$.
In this case we have
\begin{equation*}
  \F[p^n]=\F(\alpha).
\end{equation*}
The minimal polynomial $f$ of $\alpha$ over $\F[p^n]$ is
\begin{equation*}
  \sum_{k=0}^nb_kX^k
\end{equation*}
for some $b_k$ in $\F[p^n]$.
Since $f(\alpha)=0$, we have also
\begin{equation*}
  0=f(\alpha)^p=\sum_{k=0}^nb_k{}^p(X^k)^p
=\sum_{k=0}^nb_k(X^p)^k=f(\alpha^p)
\end{equation*}
by Fermat's Theorem.
In the same way, 
all elements of the set $\{\alpha^{p^i}\colon 0\leq i<n\}$
are roots of $f$.
Then the set has $n$ distinct elements;
for if $0\leq i\leq j<n$
and
\begin{equation*}
  \alpha^{p^i}=\alpha^{p^j},
\end{equation*}
then
\begin{equation*}
  \alpha^{p^{n+i-j}}=\alpha^{p^n}=\alpha,
\end{equation*}
and so $\alpha$ belongs to $\F[p^{n+i-j}]$,
which it does not, by \eqref{eqn:uFpn}, unless $i=j$.
If $\tau\in\Aut{\F}$,
then as with the Frobenius automorphism,
writing $x^{\tau}$ for $\tau(x)$ we have
\begin{equation*}
  0=f(\alpha)^{\tau}=f(\alpha^{\tau}),
\end{equation*}
so $\alpha^{\tau}=\alpha^{p^i}=\alpha^{\upsigma^i}$ for some $i$.
Since every nonzero element of $\F[p^n]$ is a power of $\alpha$,
we can conclude $\tau=\upsigma^i$.
\end{proof}

We define
\begin{equation*}
  \alg{\F}=\bigcup_{n\in\N}\F[p^n],
\end{equation*}
where $\F[p^m]\included\F[p^t]$ when $m\divides t$ as in \Theorem{thm:m|t}.
Then $\alg{\F}$ is a field, the \textbf{algebraic closure} of $F$,
since it is the smallest field including $\F$ 
in which every polynomial splits.
We have now a map
\begin{equation*}
  \zeta\mapsto(z_n\colon n\in\N)
\end{equation*}
from $\Aut{\alg{\F}}$ to the product
\begin{equation*}
  \prod_{n\in\N}\Zmod
\end{equation*}
of groups given by
\begin{equation*}
  \zeta\restriction{\F[p^n]}=\upsigma^{z_n}.
\end{equation*}
Thus the $z_n$ meet the condition
\begin{equation*}
  m\divides t\implies z_m\equiv z_t\pmod m.
\end{equation*}
We can build up such $z_n$ step by step,
by the Chinese Remainder Theorem.
Indeed, suppose
\begin{equation}\label{eqn:zkmd}
  z_k\equiv z_m\pmod d,
\end{equation}
where
\begin{equation*}
    d=\gcd(k,m).
\end{equation*}
We can let
\begin{equation}\label{eqn:z=zk+zm}
  z\equiv z_k\cdot\frac md\cdot y+z_m\cdot\frac kd\cdot x\pmod{\lcm(k,m)},
\end{equation}
where
\begin{equation}\label{eqn:kx+my=d}
  kx+my=d.
\end{equation}
Then
\begin{align}\label{eqn:mod}
  z&\equiv z_k\mod{\frac kd},&
z&\equiv z_m\mod{\frac md}.
\end{align}
Moreover, since $d\divides\lcm(k,m)$,
by \eqref{eqn:z=zk+zm} and \eqref{eqn:kx+my=d} we have
\begin{equation}
  z\equiv z_k\cdot\frac md\cdot y+z_k\cdot\frac kd\cdot x
  %\equiv z_k\cdot\frac{my+kx}d
  \equiv z_k\pmod d,
\end{equation}
and in the same way $z\equiv z_m\pmod d$.
This and \eqref{eqn:mod} give
\begin{align*}
  z&\equiv z_k\pmod k,&
z&\equiv z_m\pmod m.
\end{align*}
Thus we can let
\begin{equation*}
z_{\lcm(k,m)}=z.
\end{equation*}

Now we know that $\Aut{\alg{\F}}$
is isomorphic to the product
\begin{equation*}
  \prod_{\ell\text{ prime}}\Z_{(\ell)},
\end{equation*}
where
$\Z_{(\ell)}$ is the subgroup of
\begin{equation*}
\prod_{n\in\N}\Z_{\ell^n}
\end{equation*}
consisting of
\begin{equation*}
  (a_n\colon n\in\N)
\end{equation*}
such that
\begin{equation*}
  i\leq j\implies a_i\equiv a_j\pmod{\ell^i}.
\end{equation*}
Under this condition, we can recursively define
\begin{align*}
  b_0&=a_1,&b_n=\frac{a_{n+1}-a_n}{\ell^n}.
\end{align*}
In this case
\begin{equation*}
  a_n=\sum_{k=0}^{n-1}b_k\ell^k.
\end{equation*}
We can now write the group element as
\begin{equation*}
  \sum_{k=0}^{\infty}b_k\ell^k,
\end{equation*}
because this reflects the group structure:
\begin{equation*}
  \sum_{k=0}^{\infty}b_k\ell^k
+ \sum_{k=0}^{\infty}c_k\ell^k
= \sum_{k=0}^{\infty}d_k\ell^k
\end{equation*}
if and only if, for all $n$ in $\N$,
\begin{equation*}
  \sum_{k=0}^{n-1}b_k\ell^k
+ \sum_{k=0}^{n-1}c_k\ell^k
\equiv \sum_{k=0}^{n-1}d_k\ell^k\pmod{\ell^n}.
\end{equation*}




\AfterBibliographyPreamble{\relscale{0.9}}
%\bibliographystyle{plain}
%\bibliography{../../../references}

\begin{thebibliography}{10}

\bibitem{Descartes-Geometry}
Ren{\'e} Descartes.
\newblock {\em The Geometry of {R}en{\'e} {D}escartes}.
\newblock Dover Publications, New York, 1954.
\newblock Translated from the French and Latin by David Eugene Smith and Marcia
  L. Latham, with a facsimile of the first edition of 1637.

\bibitem{Descartes-Geometrie}
Ren{\'e} Descartes.
\newblock {\em La G{\'e}om{\'e}trie}.
\newblock Jacques Gabay, Sceaux, France, 1991.
\newblock Reprint of Hermann edition of 1886.

\bibitem{MR17:814b}
Euclid.
\newblock {\em The Thirteen Books of {E}uclid's \emph{{E}lements}}.
\newblock Dover Publications, New York, 1956.
\newblock Translated from the text of {H}eiberg with introduction and
  commentary by Thomas L. Heath. In three volumes. Republication of the second
  edition of 1925. First edition 1908.

\bibitem{Fermat-Oeuvres-2}
Pierre~de Fermat.
\newblock {\em Oeuvres de Fermat. {T}ome Deuxi{\`e}me. {C}orrespondance}.
\newblock Gautiers-Villars et Fils, Paris, 1894.
\newblock Edited by Paul Tannery and Charles Henry.
  \url{archive.org/details/oeuvresdefermat02ferm}, accessed November 23, 2017.

\bibitem{Fermat-theorem}
Pierre~de Fermat.
\newblock Letter to {B}ernard {F}r{\'e}nicle de {B}essy, {O}ctober 18, 1640.
\newblock In D.~J. Struik, editor, {\em A Source Book in Mathematics
  1200--1800}, Princeton Paperbacks, pages 27--29. Princeton University Press,
  Princeton, NJ, 1986.
\newblock Reprint of the 1969 edition.

\bibitem{Gauss-Latin}
Carl~Friedrich Gauss.
\newblock {\em Disquisitiones Arithmeticae}.
\newblock Carl Friedrich Gauss Werke. Gerh.\ Fleischer Jun., Leipzig, 1801.
\newblock Electronic version of the original Latin text from Goettingen State
  and University Library.

\bibitem{Gauss}
Carl~Friedrich Gauss.
\newblock {\em Disquisitiones Arithmeticae}.
\newblock Springer-Verlag, New York, 1986.
\newblock Translated into English by Arthur A. Clarke, revised by William C.
  Waterhouse.

\bibitem{MR0092794}
Edmund Landau.
\newblock {\em Elementary Number Theory}.
\newblock Chelsea Publishing, New York, 1958.
\newblock Originally part of \emph{Vorlesungen {\"u}ber Zahlentheorie}
  (Leipzig, 1927). Translated by J. E. Goodman.

\bibitem{MR12:397m}
Edmund Landau.
\newblock {\em Foundations of Analysis. {T}he Arithmetic of Whole, Rational,
  Irrational and Complex Numbers}.
\newblock Chelsea Publishing, New York, third edition, 1966.
\newblock Translated by F. Steinhardt; first edition 1951; first German
  publication, 1929.

\bibitem{Pierce-Thales-9}
David Pierce.
\newblock Thales and the nine-point conic.
\newblock {\em The De Morgan Gazette}, 8(4):27--78, 2016.
\newblock
  \url{http://education.lms.ac.uk/2016/12/thales-and-the-nine-point-conic/},
  accessed June 1, 2017.

\end{thebibliography}

\end{document}

