\documentclass[%
version=last,%
a5paper,
12pt,%
%headings=small,%
bibliography=totoc,%
index=totoc,%
titlepage=no,%
twoside,%
reqno,%
cleardoublepage=empty,%
%open=any,%
titlepage=false,%
draft=true,%
DIV=12,%
headinclude=false,%
pagesize]%
%{scrbook}
%{scrreprt}
{scrartcl}

%\usepackage{layout}
%\usepackage[notref,notcite]{showkeys}

\renewcommand{\sectionmark}[1]{\markleft{#1}}
\usepackage{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\refoot{Finite fields 2017}
\lofoot{\leftmark} % needs \sectionmark redefined as above
\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{verbatim}

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


%\begin{comment}

\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}}

%\end{comment}

%\usepackage{verse}

%\usepackage{multicol}
\usepackage{pstricks,pst-node,pst-plot,pst-math}

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

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

\swapnumbers
\newtheorem{theorem}{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{ET}[theorem]{Euler's Theorem}
%\newtheorem{Cfag}[theorem]{Classification of finite abelian groups}
\newcommand{\Theorem}[1]{Theorem \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][\Zmod,+]{\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{\me}{\mathrm e}
%\newcommand{\T}{\mathbb T}
%\newcommand{\pru}[1][n]{\upomega_{#1}{}}
\newcommand{\Zmod}[1][n]{\Z_{#1}}
%\DeclareMathOperator{\Li}{Li}
%\newcommand{\conj}[1]{\overline{#1}}
%\newcommand{\doubtful}{\textsuperscript?}
%\newcounter{xnum}
%\newcommand{\xnum}{\refstepcounter{xnum}[\arabic{xnum}]}

\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\Forall}[1]{\forall#1\;}
%\newcommand{\The}[1]{\text{\rotatebox[origin=c]{180}{$\iota$}}#1\;}


%\newcommand{\Ham}{\mathbb H}
%\DeclareMathOperator{\cont}{C}
%\newcommand{\lto}{\Rightarrow}
%\newcommand{\liff}{\Leftrightarrow}
\renewcommand{\geq}{\geqslant}
\renewcommand{\leq}{\leqslant}
\renewcommand{\emptyset}{\varnothing}
%\renewcommand{\epsilon}{\varepsilon}
%\newcommand{\gid}{\mathrm e}

\usepackage[all]{xy}
%\renewcommand{\theequation}{\fnsymbol{equation}}

%\usepackage[utf8]{inputenc}
%\usepackage[turkish,english]{babel}

%\usepackage{gfsneohellenic}
%\newcommand{\gr}[1]{\foreignlanguage{polutonikogreek}{%
%\relscale{0.9}\textneohellenic{#1}}}

\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}}}

\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 2017}
\author{David Pierce}
\date{January 16--22, 2017\\
%Edited February 6, 2017\\
Edited January 5, 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}
}

\maketitle
\thispagestyle{empty}
%\tableofcontents
%\setcounter{chapter}{-1}
\section*{Preface}

The present typeset document is based on
a course of lectures at the Nesin Mathematics Village in \c Sirince,
Sel\c cuk, \.Izmir, January 16--22 (Monday--Sunday), 2017.

My course was one of three on the general theme of linear algebra.
The students were university undergraduates,
though not necessarily from mathematics departments,
along with a few high-school students.
The other teachers were Ali Nesin and Salih Durhan.
I usually taught 9:00--11:00
(strictly, 9:00--50 and 10:00--50)
in the Ni\c sanyan K\"ut\"uphanesi,
and the other courses were 11:00--13:00 and 17:00--19:00,
with meals following each of these lecture.%%%%%
\footnote{On Monday I taught at 9:00,
and Salih taught at 11:00 about modules in general.
I was told Monday evening that
Ali would teach at 9:00 the next day; I, 11:00.
An SMS sent to Ali around 8:40 on Tuesday going unanswered,
I went to the library anyway.
Ali not being there at 9, I taught.
He had been planning to come, but came late.
Meanwhile, it transpired that the library was needed for another event at 11:00,
involving children;
lunch for our group was rescheduled for 12:00,
but I did not get the message.
(I did get lunch though,
just before the children invaded the Bol Kep\c ce at 13:00.)}

I started typesetting this document
on Thursday morning,
after three lectures had been completed.
The sources are 
\begin{inparaenum}[(1)]
\item
my handwritten notes, prepared before the lectures,
\item
the typeset notes from a similar course last year,
\item
my memory of what happened in the lectures,
and sometimes
\item
my wishes for enlargements or improvements.
\end{inparaenum}
Thus
the notes are not a precise record of what actually happened,
though they should be close.

I lectured mostly in Turkish,
though writing on the board in English.
Students' questions were mostly in Turkish,
though sometimes, face to face during the break or after the second hour,
in English.

\section{Monday, January 16}

We shall study \emph{vector spaces over finite fields.}
A \textbf{field} is a commutative ring in which $1\neq0$
and every nonzero element has a multiplicative inverse.
Examples of fields include $\C$, $\R$, and $\Q$.
A \textbf{vector space} is a module over a field.
Every field is a vector space over every field that it 
\emph{includes} as a subfield:
thus $\C$ is a vector space over $\R$ and $\Q$,
and $\R$ is a vector space over $\Q$.  
We shall prove the following theorems.
\begin{compactenum}
\item
The size of every finite field is the power of a prime number
(Theorem \ref{thm:p^n}, page \pageref{thm:p^n}).
\item
For every prime power $q$,
there is a field $\F[q]$ of size $q$,
and all such fields are isomorphic
(Theorem \ref{thm:F_p^n}, page \pageref{thm:F_p^n}).
\item
If $p$ is prime,
and $k$ and $m$ are positive integers,
\begin{equation*}
\F[p^k]\included\F[p^m]\iff k\divides m
\end{equation*}
(Theorem \ref{thm:m|t}, page \pageref{thm:m|t}).
\item
The multiplicative group $\units{\F[q]}$ of \emph{units} of $\F[q]$ is isomorphic to $\Zmod[q-1]$
(Theorem \ref{thm:F_q^x}, page \pageref{thm:F_q^x}).
\end{compactenum}
In order to be able to prove these theorems,
we shall prove the following results from number theory.

\begin{Euclem}\label{thm:Euc}
For all primes $p$,
\begin{equation*}
p\divides ab\And p\ndivides a\implies p\divides b.
\end{equation*}
\end{Euclem}

\begin{Bezout}
For all integers $a$ and $b$, not both $0$,
if $d$ is the greatest common divisor of $a$ and $b$,
then the equation
\begin{equation*}
ax+by=d
\end{equation*}
is soluble.
\end{Bezout}

Properly formulated,
\begin{compactitem}
  \item
Euclid's Lemma will be true for every commutative ring 
for which B\'ezout's Lemma is true;
\item
B\'ezout's Lemma will be true for every commutative ring 
in which greatest common divisors can be found by the 
\textbf{Euclidean Algorithm.}
\end{compactitem}
However, the converses fail;
there are commutative rings in which Euclid's Lemma is true,
but not B\'ezout's Lemma;
and in which B\'ezout's Lemma is true,
but the Euclidean Algorithm is not available.

The ring $\Zmod[5]$ is $\{0,1,2,3,4\}$;
one can check that this is a field, since, \emph{modulo} $5$,
\begin{align*}
	2\cdot3&\equiv1,&
4\cdot4&\equiv1,
\end{align*}
and so all nonzero elements of $\Zmod[5]$ have inverses.
However, the ring $\Zmod[6]$, namely $\{0,1,2,3,4,5\}$,
is not a field,
since $2\cdot3\equiv0\pmod6$,
so $2$ can have no inverse.

We let $\N$ be the set $\{1,2,3,\dots\}$
or $\{x\in\Z\colon x>0\}$ of positive integers,
that is, counting numbers.
If $n\in\N$, then
\begin{equation}\label{eqn:Zmod}
\Zmod=\{x\in\Z\colon 0\leq x<n\}.
\end{equation} 
This is a ring with addition $\oplus$
and multiplication $\otimes$, where
\begin{gather*}
	a\oplus b=c\iff a+b\equiv c\pmod n,\\
	a\otimes b=c\iff ab\equiv c\pmod n.	
\end{gather*}
(We shall work this out precisely tomorrow.)%%%%%
\footnote{I did not use the notation $\oplus$ and $\otimes$
in class.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{theorem}
For all $n$ in $\N$,
if the ring $\Zmod$ is a field, then $n$ must be prime.
\end{theorem}

\begin{proof}
We show the contrapositive.
If $n$ is not prime, 
then it is either $1$ or a composite $ab$,
where $1<a<n$.
Since $\Zmod[1]=\{0\}$, this is not a field,
since $1\neq0$ in a field.
In the other case, $a\not\equiv1$,
but $ab\equiv0\pmod n$,
so $a$ has no inverse.
\end{proof}

We shall show the converse,
that for all primes $p$, $\Zmod[p]$ is a field.%%%%%
\footnote{I say that we shall use the Euclidean Algorithm for this;
but here I shall turn out not to be correct.
A student says he can prove the theorem without the Algorithm;
but what he turns out to mean is that he can prove that every finite integral domain is a field.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We have this already when $p$ is $5$.
It is obviously true when $p$ is $2$.

On the four-element set $\{0,1,\alpha,\beta\}$,
we define addition and multiplication
as in the following tables.
%Figure \ref{fig:F4}.
%\begin{figure}[ht]
\begin{align*}
	&\begin{array}{c|*4c}
     +&     0&     1&\alpha& \beta\\\hline
     0&     0&     1&\alpha& \beta\\
     1&     1&     0& \beta&\alpha\\
\alpha&\alpha& \beta&     0&     1\\
 \beta& \beta&\alpha&     1&     0
\end{array}&
	&\begin{array}{c|*4c}
\times&     0&     1&\alpha& \beta\\\hline
     0&     0&     0&     0&     0\\
     1&     0&     1&\alpha& \beta\\
\alpha&     0&\alpha& \beta&     1\\
 \beta&     0& \beta&     1&\alpha
\end{array}
\end{align*}
%\caption{The operations on $\F[4]$}\label{fig:F4}
%\end{figure}
These are derived from the rules
\begin{align}\label{eqn:1+1=0}
	1+1&=0,&\alpha^2&=\alpha+1=\beta,
\end{align}
assuming also that the resulting structure will be a field,
so that, in particular, 
\begin{equation*}
x+x=1x+1x=(1+1)x=0.
\end{equation*}
One can check that the structure \emph{is} a field,
which we may call $\F[4]$;
but this checking may be tedious,
unless we develop some general principles.%%%%%
\footnote{With students who ask questions after class, 
I observe that our $\F[4]$ is $\F[2][\alpha]$,
and this is $\F[2]{}^2$ with multiplication of vectors by scalars
extended to allow multiplication by all vectors.
In the same way, $\C$ is $\R[\mi]$, where $\mi^2+1=0$;
so $\C$ is $\R^2$ with multiplication similarly extended.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Tuesday, January 17}

We want to show that, whenever $p$ is prime,
then $\Zmod[p]$ is a field.
What \emph{is} $\Zmod[p]$ anyway?
More generally, when $n\in\N$,
why is $\Zmod$ a ring?
The relation $R$ given by
\begin{equation*}
x\mathrel Ry\iff x\equiv y\pmod n
\end{equation*}
is an equivalence relation on $\Z$, meaning
\begin{gather*}
    x\mathrel Rx,\\
    x\mathrel Ry\implies y\mathrel Rx,\\
    x\mathrel Ry\And y\mathrel Rz\implies x\mathrel Rz.  
\end{gather*}
If $a\in\Z$, we define
\begin{equation*}
[a]=\{x\in\Z\colon a\mathrel Rx\},
\end{equation*}
the equivalence class of $a$ with respect to $R$.
Now we can define
\begin{equation*}
\Zmod=\{[x]\colon x\in\Z\}.
\end{equation*}
The next two theorems allow us to use the definition in \eqref{eqn:Zmod}.
We shall use the notation
\begin{equation*}
\upomega=\{0,1,2,\dots\}=\{0\}\cup\N=\{x\in\Z\colon x\geq0\}.
\end{equation*}

\begin{Division}\label{thm:div}
For all $n$ in $\N$ and $a$ in $\Z$,
the system
\begin{equation*}
a=nx+y\And 0\leq y<n
\end{equation*}
has a unique solution.
\end{Division}

\begin{proof}
We shall use that $\upomega$ is \emph{well-ordered}:
every nonempty subset has a least element.
The set
\begin{equation*}
\{a-nx\colon x\in\Z\}\cap\upomega
\end{equation*}
is nonempty (why?);
so it has a least element, $r$,
and then for some $q$,
\begin{equation*}
a=nq+r.
\end{equation*}
If $r\geq n$,
then $a=n(q+1)+(r-n)$,
so $r-n\in\{a-nx\colon x\in\Z\}\cap\upomega$,
but is less than the least element,
which is absurd.
So $0\leq r<n$.
Uniqueness is an exercise.
\end{proof}

\begin{theorem}
For all $n$ in $\N$,
\begin{compactenum}[1)]
\item
$\Zmod=\{[x]\colon0\leq x<n\}$;
\item
$\size{\Zmod}=n$.
%if $0\leq a<b<n$, then $[a]\neq[b]$.
\end{compactenum}
\end{theorem}

\begin{proof}
The first part follows from the previous theorem.
For the second part,
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}

We now establish that $\Zmod$ is a ring.

\begin{theorem}
For all $n$ in $\N$,
for all $a$, $b$, $c$, and $d$ in $\Z$,
if
\begin{equation*}
a\equiv c\And b\equiv d\pmod n,
\end{equation*}
then
\begin{equation*}
a+b\equiv c+d\And ab\equiv cd\pmod n.
\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 $\Zmod$ must satisfy all identities,
like $x\cdot(y+z)=xy+xz$, that involve addition and multiplication%%%%%
\footnote{In class I wrote only the example $xy=yx$.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
and are true in $\Z$.
Since commutative rings are defined as satisfying some such identities,
$\Zmod$ must be a commutative ring, like $\Z$.

However, not all properties of $\Z$
are inherited by $\Zmod$.
For example, $\Z$ is infinite,
but $\Zmod$ is not.
Moreover, $\Z$ satisfies
\begin{equation*}
0\neq1\And\Forall x\Forall y(xy=0\And x\neq0\implies y=0);
\end{equation*}
this means it is an \textbf{integral domain.}
All fields are integral domains,
but $\Z$ is an integral domain that is not a field.
The example $\Zmod[6]$ 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,
the function must be surjective.
This means the equation $ax=1$ has a solution.
\end{proof}

Euclid's Lemma is that, for all primes $p$,
\begin{equation*}
ab\equiv0\And a\not\equiv0\implies b\equiv0\pmod p,
\end{equation*}
that is, in $\Zmod[p]$,
\begin{equation*}
ab=0\And a\neq0\implies b=0.
\end{equation*}
Since $p>1$ in $\Zmod[p]$,
we have $0\neq1$ there.
Thus we can restate Euclid's Lemma
(\Theorem{thm:Euc}) as follows.

\begin{Euclem}[second form]\label{thm:Euc-2} 
For all primes $p$, $\Zmod[p]$ is an integral domain.
\end{Euclem}

Again, we shall prove this by means of B\'ezout's Lemma,
which we shall prove as we proved the Division Theorem
(\Theorem{thm:div}).

\begin{proof}[Proof of B\'ezout's Lemma.]%\label{Bezout-proof}
Let $d$ be the least element of the set
\begin{equation*}
\{ax+by\colon(x,y)\in\Z\times\Z\}\cap\N.
\end{equation*}
By the Division Theorem,
for some $q$ and $r$ in $\Z$, we have
\begin{equation*}
a=dq+r\And0\leq r<d.
\end{equation*}
Then for some $x$ and $y$ we have
\begin{equation*}
r=a-dq=a-(ax+by)q=a(1-qx)+b(-qy),
\end{equation*}
so $r$ belongs to $\{ax+by\colon(x,y)\in\Z\times\Z\}$.
By the minimality of $d$ as a positive element of this set,
$r$ must be $0$.  Thus $d\divides a$.
Likewise $d\divides b$.
Since $d$ is of the form $ax+by$,
every common divisor of $a$ and $b$ must divide $d$.
\end{proof}

We denote the greatest common divisor of $a$ and $b$ by
\begin{equation*}
\gcd(a,b).
\end{equation*}

\section{Wednesday, January 18}

\begin{proof}[Proof of Euclid's Lemma.]\label{proof:Euclem}
Suppose $p\divides ab$, but $p\ndivides a$.
Then
\begin{equation*}
\gcd(a,p)=1,
\end{equation*}
so for some $x$ and $y$,
\begin{gather*}
	ax+py=1,\\
	abx+pby=b.
\end{gather*}
Since $p\divides abx+pby$ for all $x$ and $y$,
we conclude $p\divides b$.
\end{proof}

\begin{theorem}
For all primes $p$, $\Zmod[p]$ is a field.
\end{theorem}

\begin{proof}
By Euclid's Lemma,
%(\Theorem{thm:Euc-2}),
$\Zmod[p]$ is an integral domain;
then by \Theorem{thm:fin-id-field}, it is a field.
\end{proof}

To emphasize that it is a field,
we shall write $\Zmod[p]$ as
\fbox{$\F[p]$.}
What other finite fields can there be?
On Monday we saw the example $\{0,1,\alpha,\beta\}$,
with the conditions \eqref{eqn:1+1=0}.
We can write the field as $\F[2][\alpha]$,
where $\alpha^2+\alpha+1=0$.
In general, if $R$ is a commutative ring,
and $\alpha$ belongs to some larger commutative ring,
then
\begin{multline*}
R[\alpha]
=\{0\}\cup\bigcup_{n\in\upomega}\{x_0\alpha^n+x_1\alpha^{n-1}+\dots+x_{n-1}\alpha+x_n\colon\\
(x_0,\dots,x_{n-1})\in R^n\And x_0\neq0\},
\end{multline*}
which is the smallest ring that includes $R$ and contains $\alpha$.
Note that, for this definition to make sense,
$\alpha$ should already belong to some commutative ring that includes $R$.
If $X$ is a ``variable'' or \emph{indeterminate,}
we define $R[X]$ formally,
just as we do $R[\alpha]$;
but the elements of $R[X]$ are the \textbf{polynomials}
in $X$ with coefficients from $R$.
Then we have
\begin{equation*}
R[\alpha]=\{f(\alpha)\colon f\in R[X]\}.
\end{equation*}
We are going to show how $R[\alpha]$ may be determined by some desired property,
falling short of membership in a known ring.
For example, $\C=\R[\mi]$, where $\mi^2+1=0$.
We shall be able to define $\F[8]$ as $\F[2][\alpha]$,
where now $\alpha^3=\alpha+1$, so that,
as a set,
\begin{equation*}
\F[8]=\{0,1,\alpha,\alpha+1,\alpha^2,\alpha^2+1,\alpha^2+\alpha,\alpha^2+\alpha+1\}.
\end{equation*}
For example, $\alpha\cdot(\alpha^2+\alpha)=\alpha^3+\alpha^2=\alpha^2+\alpha+1$.
But if we separately require $\beta^3=\beta^2+\beta+1$,
then
\begin{equation*}
\F[2][\beta]=\{0,1,\beta,\beta+1,\beta^2,\beta^2+1,\beta^2+\beta,\beta^2+\beta+1\}.
\end{equation*}
This is a commutative ring, but not an integral domain,
since
\begin{equation*}
0=\beta^3+\beta^2+\beta+1=(\beta^2+1)(\beta+1),
\end{equation*}
but neither factor is $0$.

In any commutative ring $R$,
the invertible elements are called \textbf{units,}
and they compose the multiplicative group denoted by
\begin{equation*}
\units R.
\end{equation*}
For example, $\units{\Z}=\{\pm1\}$,
while $\units K=K\setminus\{0\}$ for any field $K$.
An element $\pi$ of $R$ is called \textbf{irreducible}
if it has the properties of prime numbers:
$\pi\neq0$ and $\pi\notin\units R$, but
\begin{equation*}
\pi=ab\And a\notin\units R\implies b\in\units R.
\end{equation*}
We shall use irreducibles in $K[X]$ to obtain fields,
just as we used primes in $\N$ to obtain the fields $\F[p]$.

For any element $a$ of $R$,
we define
\begin{equation*}
(a)=\{ax\colon x\in R\}.
\end{equation*}
This determines an equivalence relation $R$
given by
\begin{equation*}
x\mathrel Sy\iff x-y\in(a).
\end{equation*}
Now for any $b$ in $R$ we define
\begin{equation*}
[b]=\{x\in R\colon x\mathrel Sa\}
=\{x\in R\colon a\divides x-y\}.
\end{equation*}
Finally,
\begin{equation*}
R/(a)=\{[x]\colon x\in R\}.
\end{equation*}
Thus, in particular,
\begin{equation*}
\Zmod[n]=\Z/(n).
\end{equation*}
Just as we showed, for all $p$ in $\N$,
\begin{equation*}
\Z/(p)\text{ is a field}\iff p\text{ is prime,}
\end{equation*}
so we shall show, for all $f$ in $K[X]$,
\begin{equation*}
K[X]/(f)\text{ is a field}\iff f\text{ is irreducible.}
\end{equation*}

\section{Thursday, January 19}

As an example, $X^3+X+1$ is irreducible in $\F[2][X]$,
because if it is not, then we have
\begin{equation*}
X^3+X+1=(X+a)(X^2+bX+c)
\end{equation*}
for some $a$, $b$, and $c$ in $\F[2]$;
but in this case
\begin{equation*}
X^3+X+1=X^3+(a+b)X^2+(ab+c)X+ac,
\end{equation*}
so $a=c=1$ (since $1=ac$),
and then $b=a=1$ (since $0=a+b$),
so $1=ab+c=0$, which is absurd.

The polynomial $X^2+1$ is irreducible over $\R$,
but not over $\C$, since
\begin{gather*}
	X^2+1=(X+\mi)(X-\mi).
\end{gather*}

An element $\pi$ of an integral domain $R$ is called \textbf{prime}
if $\pi\neq0$ and $\pi\notin\units R$, but
\begin{equation*}
\pi\divides ab\And p\ndivides a\implies p\divides b.
\end{equation*}
Thus we have:

\begin{Euclem}[third form]
All irreducibles in $\Z$ are prime.
\end{Euclem}

We proved this using B\'ezout's Lemma.
We can do the same for $K[X]$,
using an analogue of \Theorem{thm:div}.
Every nonzero element $f$ of $K[X]$ is,
for some $d$ in $\upomega$,
\begin{equation*}
a_0+a_1X+\dots+a_dX^d,
\end{equation*}
where the $a_i$ are in $K$, and $a_d\neq0$;
and then
\begin{equation*}
d=\deg(f),
\end{equation*}
the \textbf{degree} of $f$.
For completeness, we may define
\begin{equation*}
\deg(0)=-\infty.
\end{equation*}

\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}
Exercise.  (Let $r$ be an element of
$\{f-g\cdot\xi\colon\xi\in K[X]\}$
having minimal degree.)
\end{proof}

\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]\}
\end{equation*}
having minimal degree,
\begin{compactenum}[(i)]
\item
$h\divides f$ and $h\divides g$;
\item
if $k\in K[X]$ and $k\divides f$ and $k\divides g$,
then $k\divides h$.
\end{compactenum}
\end{Bezout}

\begin{proof}
Exercise.
\end{proof}

The polynomial $h$ in the theorem is a 
greatest common divisor of $f$ and $g$.
It is unique up to multiplication by a nonzero scalar.
Now we can show:

\begin{Euclem}[for polynomials]
For every field $K$,
every irreducible $f$ of $K[X]$ is prime,
and consequently $K[X]/(f)$ is an integral domain.
\end{Euclem}

\begin{proof}
Exercise.
\end{proof}

If $f$ in $\F{}[X]$ is irreducible of degree $n$,
then $\F{}[X]$ is an integral domain of size $p^n$
and is therefore a field.
We shall show that such $f$ exist for all positive degrees.

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 $\size K=p^n$.
\end{proof}

We shall give more details on Saturday.

\section{Friday, January 20}

\begin{FT}
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 $\Zmod[p]$,
\begin{equation*}
a\neq0\implies a^{p-1}=1,
\end{equation*}
or equivalently, for all $a$ in $\Zmod[p]$,
\begin{equation}\label{eqn:a^p=a}
a^p=a.
\end{equation}
We can prove this by induction in $\Zmod[p]$.
Immediately \eqref{eqn:a^p=a} when $a=1$.
Suppose \eqref{eqn:a^p=a} is true when $a=b$, so $b^p=b$.
Then
\begin{equation*}
(b+1)^p=b^p+\sum_{i=1}^{p-1}\binom pib^{p-i}+1=b^p+1=b+1
\end{equation*}
in $\Zmod[p]$
(see below),
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 $\Zmod[p]$.
\end{proof}

We have used:

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

\begin{proof}
We have
\begin{equation*}
\binom pk=\frac{p!}{k!\cdot(p-k)!};
\end{equation*}
also, this is indeed a whole number,
since it is a coefficient appearing in a polynomial over $\Z$,
and also since it is the number of $k$-element subsets of a set of size $p$.
We want to show
\begin{equation}\label{eqn:k!}
	k!\cdot(p-k)!\divides(p-1)!.
\end{equation}
By Euclid's Lemma, since $0<k<p$ and $p$ is prime,
\begin{equation*}
p\ndivides k!\cdot(p-k)!,
\end{equation*}
and then
$\gcd\bigl(p,k!\cdot(p-k)!\bigr)=1$.
Consequently, by the \emph{proof} of Euclid's Lemma
(page \pageref{proof:Euclem}),
we have \eqref{eqn:k!}.
\end{proof}

We can also derive Fermat's Theorem as a special case Euler's Theorem below,
which uses the definition
\begin{equation*}
\euphi(n)=\size{\units{\Zmod}}.
\end{equation*}
It follows again from the proof of Euclid's Lemma that
\begin{equation*}
\units{\Zmod}=\{[x]\in\Zmod\colon\gcd(n,x)=1\}.
\end{equation*}

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

\begin{proof}
If $\gcd(a,n)=1$, then $[a]\in\units{\Zmod}$, so all powers of $[a]$ are in this group.
But then for some $k$ and $m$ such that $0\leq k<m\leq\euphi(n)$,
we have
\begin{align*}
a^k&\equiv a^m\pmod n,&	
a^{m-k}&\equiv1\pmod n.
\end{align*}
If now $j$ is minimal such that $0<j\leq\euphi(n)$ and $a^j\equiv1\pmod n$,
then $j\divides\euphi(n)$ [why?%%%%%
\footnote{I may not have raised this question in class.
On can appeal to the Lagrange Theorem
or prove it for the present case:
There will be some elements $b$ of $\units{\Zmod}$
such that the group is the disjoint union of the subsets
$\{a^kb\colon 0\leq k<j\}$,
each having size $j$.}].
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
This yields the claim.
\end{proof}

The same proof gives us:

\begin{theorem}
If $K$ is a finite field of size $q$, then
\begin{align*}
\units K&=\{x\in K\colon x^{q-1}=1\},&
K&=\{x\in K\colon x^q=x\}.
\end{align*}
\end{theorem}

Now we shall be able to give a precise characterization of a finite field,
thanks to the following.

\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*}
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}

An \textbf{algebraically closed field}
is a field over which every irreducible polynomial has degree $1$.
This means \emph{every} polynomial has a zero in the field.%%%%%
\footnote{Except polynomials of degree $0$.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
An \textbf{algebraic closure} of a field $K$
is an algebraically closed field that includes $K$
and that embeds over $K$ in any other algebraically closed field
that includes $K$.

\begin{theorem}
Every field has an algebraic closure.
\end{theorem}

\begin{proof}
We prove this only for finite or countable fields $K$;
the general case is similar, but requires \emph{transfinite} recursion.
Even in the special case, we are not yet going to give a complete proof.

Let $(f_i\colon i\in\upomega)$ 
be a list of all of the irreducible polynomials over $K$
having degree greater than $1$.
Let $K_0=K$, and if $K_m$ has been defined so as to include $K$,
let
\begin{equation*}
K_{m+1}=K_m[X]/(g_m),
\end{equation*}
where $g_m\in K_m[X]$ and is an irreducible factor of $f_m$.
By recursion, we now have a chain
\begin{equation*}
K=K_0\included K_1\included K_2\included\cdots
\end{equation*}
We define
\begin{equation*}
\alg K=\bigcup_{i\in\upomega}K_i;
\end{equation*}
this is the \textbf{algebraic closure} of $K$.
For, it contains a zero of every irreducible polynomial over $K$.
Moreover, it contains a zero of every polynomial over \emph{itself}
(though this has to be proved).
Finally, $\alg K$ embeds in every algebraically closed field in which $K$ itself embeds
(this too must be shown).
\end{proof}

\begin{theorem}\label{thm:F_p^n}
For each prime power $p^n$,
the set
\begin{equation*}
\{x\in\alg{\F}\colon x^{p^n}=x\}
\end{equation*}
is a field of size $p^n$.
Every field of size $p^n$ is isomorphic to this one.
\end{theorem}

\begin{proof}
Let $f$ be the function $x\mapsto x^p$
from $\alg{\F}$ to itself.
The indicated set is
\begin{equation*}
\{x\in\alg{\F}\colon f^n(x)=x\},
\end{equation*}
where by definition $f^1=f$ and $f^{k+1}=f\circ f^k$.
We have $f(1)=1$,
and by the commutativity of multiplication,
$f(xy)=f(x)\cdot f(y)$.
Hence the indicated set is closed under multiplication and inversion.
By Lemma \ref{lem}, $f(x+y)=f(x)+f(y)$;
so the indicated set is now a field.
By the last three theorems,
this field is unique (up to isomorphism)
as a field of its size.%%%%%
\footnote{I did not write out this proof in class.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{proof}

The field in the theorem can be called
\begin{equation*}
\F[p^n].
\end{equation*}

We finally want to show that $\units K$ is cyclic for all finite fields $K$.
We consider first some examples.

In $\F[17]$, the computations
\begin{equation*}
\begin{array}{*{11}r}
     x & 0& 1& 2& 3& 4& 5& 6& 7& 8&              \\\hline
   2^x & 1& 2& 4& 8&-1&-2&-4&-8& 1&\text{mod}\ 17\\
   3^x & 1& 3&-8&-7&-4& 5&-2&-6&-1&\text{mod}\ 17\\
3^{8+x}&-1&-3& 8& 7& 4&-5& 2& 6& 1&\text{mod}\ 17
\end{array}
\end{equation*}
show that $\units{\Zmod[17]}$ is not $\gpgen2$, but is $\gpgen3$.

In $\F[2][X]$, let $f=X^3+X+1$, and let $\alpha=[X]=X+(f)$
in $\F[2][X]/(f)$, which field is therefore $\F[2][\alpha]$.
Then $\alpha^3=\alpha+1$, so we can compute as follows.%%%%%
\footnote{I did not give this example in class.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{equation*}
\begin{array}{*{9}c}
          x & 0& 1    & 2      & 3      & 4             & 5               & 6        &7\\\hline
   \alpha^x & 1&\alpha&\alpha^2&\alpha+1&\alpha^2+\alpha&\alpha^2+\alpha+1&\alpha^2+1&1
\end{array}
\end{equation*}
Thus $\units{\F[2][\alpha]}=\gpgen{\alpha}$.
But this is no surprise: since the group has prime order,
every nontrivial element generates it.

However, $X^2+1$ is irreducible over $\F[3]$,
since it has no zero in $\F[3]$.
Let $\beta=X+(X^2+1)$ in $\F[3][X]/(X^2+1)$.
Then $\beta^2=-1$ so $\beta^4=1$.
Thus $\beta$ cannot generate $\units{\F[\beta]}$,
which has order $8$.
However, $\beta+1$ does generate the group:
\begin{equation*}
\begin{array}{r*5c}
             x & 0& 1     & 2    & 3     & 4\\\hline
   (\beta+1)^x & 1&\beta+1&-\beta&1-\beta&-1\\
(\beta+1)^{4+x}&-1&-(\beta+1)&\beta&\beta-1&1
\end{array}
\end{equation*}
Writing $\beta+1$ as $\alpha$, we have
$\beta=\alpha-1$, so $0=(\alpha-1)^2+1=\alpha^2+\alpha-1$, so
\begin{equation*}
\F[3][\beta]=\F[3][\alpha]=\F[3][X]/(X^2+X-1).
\end{equation*}
In fact
\begin{equation*}
X^8-1=(X-1)(X+1)(X^2+1)(X^4+1),
\end{equation*}
and over $\F[3]$ we have
\begin{gather*}
	X^4+1=(X^2+X-1)(X^2-X-1).
\end{gather*}
Any of the three irreducible polynomials $X^2+1$
and $X^2\pm X-1$ will give us $\F[9]$.

It will be true generally that $X^{p^n-1}-1$
has at least one irreducible factor over $\F$
of degree $n$, and none of higher degree.

\section{Saturday, January 21}

\begin{proof}[Detailed proof of \Theorem{thm:p^n}.]
Let $K$ be a finite field,
and suppose $\Char K=p$.
Then $\F\included K$.
For some $n$ in $\N$,
\begin{equation*}
p^{n-1}<\size K\leq p^n.
\end{equation*}
By recursion, $K$ has a subset $\{a_i\colon 0\leq i<n\}$
such that, whenever $0\leq m<n$,
\begin{equation*}
a_m\notin\left\{\sum_{i=0}^{m-1}a_ix_i\colon x_i\in\F\right\}.
\end{equation*}
This is so because, defining
\begin{equation*}
V_m=\left\{\sum_{i=0}^{m-1}a_ix_i\colon x_i\in\F\right\},
\end{equation*}
we have $\size{V_m}\leq p^m$.  Now we show by induction
\begin{equation}\label{eqn:V}
\size{V_m}=p^m,
\end{equation}
whenever $m\leq n$.  By definition, $\sum_{i=0}^{m-1}a_ix_i$
is $0$, which is neutral with respect to addition, just as $0!=1$,
which is neutral for multiplication.  Also
\begin{equation*}
\sum_{i=0}^{m-1}1=m\cdot1=m;
\end{equation*}
it makes sense that this should be true even when $m=0$.
Suppose now $k<n$ and \eqref{eqn:V} holds when $m=k$.
We have
\begin{equation*}
V_k\cap\{a_kx\colon x\in\F\}=\{0\},
\end{equation*}
since if $a_kb\in V_k$, but $b\neq0$,
then $a_kbb\inv\in V_k$ (since this is a vector space over $\F$),
but this means $a_k\in V_k$, contrary to the definition.
So now the surjective function $(v,x)\mapsto v+a_kx$
from $V_m\times\F$ onto $V_{k+1}$
is also injective, since if
\begin{equation*}
v+a_kb=w+a_kc
\end{equation*}
for some $v$ and $w$ in $V_k$ and $b$ and $c$ in $\F$,
then
\begin{equation*}
v-w=a_k(c-b),
\end{equation*}
so both sides are in $V_k\cap\{a_kx\colon x\in\F\}$,
which means they are $0$, so $v=w$ and $b=c$.
Now we have
\begin{equation*}
\size{V_{k+1}}=\size V\times\size{\F}=p^k\cdot p=p^{k+1},
\end{equation*}
so \eqref{eqn:V} is true when $m=k+1$.
By induction it is true whenever $m\leq n$.
In particular,
\begin{equation*}
p^n=\size{V_n}\leq\size K\leq p^n,
\end{equation*}
so $\size K=p^n$.
\end{proof}

\begin{theorem}\label{thm:m|t}
For all primes $p$, 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{gather*}
	p^t-1=(p^m)^k-1
	=(p^m-1)\bigl((p^m)^{k-1}+\dots+1\bigr),\\
	p^t-1=(p^m-1),\\
	\begin{aligned}[b]
          \F[p^m]
          =\{0\}\cup\units{\F[p^m]}
&=\{0\}\cup\{x\in\F[p^t]\colon x^{p^m-1}=1\}\\
&\included\{0\}\cup\{x\in\F[p^t]\colon x^{p^t-1}=1\}\\
&=\{0\}\cup\units{\F[p^t]}
=\F[p^t].
	\end{aligned}\qedhere
\end{gather*}
\end{proof}

It remains to show $\units{\F[q]}\cong\Zmod[q-1]$.

\begin{theorem}
For all $a$ and $b$ in $\N$,
if $d=\gcd(a,b)$, then
\begin{compactenum}[1)]
\item
$ab/d$ is a common multiple of $a$ and $b$, and
\item
if $c$ is a common multiple of $a$ and $b$,
then $ab/d\divides c$.
\end{compactenum}
\end{theorem}

\begin{proof}
$a\divides a\cdot(b/d)$ and $b\divides(a/d)\cdot b$.
Suppose $a\divides c$ and $b\divides c$.
Then $c/a\in\Z$, and
\begin{align*}
	&\frac bd\bigdivides c,&
	&\frac bd\bigdivides\frac ca\cdot a,&	
  &\frac bd\bigdivides\frac ca
\end{align*}
since $\gcd(b/d,a)=1$, and therefore $ab/d\divides c$.
%\begin{equation*}
%  \frac{ab}d\bigdivides c.\qedhere	
%\end{equation*}
\end{proof}

Thus
\begin{equation*}
\frac{ab}{\gcd(a,b)}
=\lcm(a,b),
\end{equation*}
the least common multiple of $a$ and $b$.

\begin{theorem}
If an abelian group has elements $g$ and $h$
of orders $a$ and $b$ respectively,
the the element
\begin{equation*}
\gcd(a,b)\cdot g+h
\end{equation*}
has order $\lcm(a,b)$.
\end{theorem}

\begin{proof}
Let $\gcd(a,b)=d$.
Then $\ord{dg}=a/d$ and $\ord h=b$,
and $\gcd(a/d,b)=1$.
By the proof of Euler's Theorem (\Theorem{thm:ET}),
since every element of $\gpgen{dg}$ or $\gpgen h$
has order dividing that of the respective group,
\begin{equation*}
\gpgen{dg}\cap\gpgen h=\{0\}.
\end{equation*}
As in the proof of \Theorem{thm:p^n} above,
if $c(dg+h)=0$, then $cdg=-ch$,
so each side belongs to $\gpgen{dg}\cap\gpgen h$
and is therefore $0$.
Then $a\divides cd$, so $a/d\divides c$;
but also $b\divides c$,
and therefore $ab/d\divides c$,
since $\gcd(a/d,b)=1$.
Conversely
\begin{equation*}
\frac{ab}d(dg+h)=bag+abh=0.
\end{equation*}
Thus $\ord{dg+h}=\lcm(a,b)$.
\end{proof}

\begin{theorem}\label{thm:F_q^x}
For all prime powers $q$,
\begin{equation*}
\units{\F[q]}\cong\Zmod[q-1].
\end{equation*}
\end{theorem}

\begin{proof}
Let $a$ be an element of $\units{\F[q]}$ of maximal order.
If $b\in\units{\F[q]}$,
then the group has an element of order $\lcm(\ord a,\ord b)$,
and therefore $\ord b$ must divide $\ord a$.
If this order is $n$, then
\begin{equation*}
\units{\F[q]}=\{x\in\F[q]\colon x^n=1\}.
\end{equation*}
By \Theorem{thm:deg},
\begin{equation*}
q-1=\size{\units{\F[q]}}\leq n,
\end{equation*}
so $n=q-1$,
and therefore $\units{\F[q]}=\gpgen a$.
\end{proof}

\section{Sunday, January 22}

$\F[q]$ as splitting field; EDs, PIDs, and UFDs;
induction and recursion.

\tableofcontents
%\listoffigures


\end{document}

