\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsfonts}
\newcommand{\F}{\mathbb{F}}
\newcommand{\K}{\mathbb{K}}
\newcommand{\np}{\mathop{\rm NP}}
\newcommand{\binom}[2]{{#1 \choose #2}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\vol}{\mathop{\rm Vol}}
\newcommand{\conp}{\mathop{\rm co-NP}}
\newcommand{\atisp}{\mathop{\rm ATISP}}
\renewcommand{\vec}[1]{{\mathbf #1}}
%\input{dansmacs}
\begin{document}
\noindent {\large Algebra and Computation (MIT 6.s897)
\hfill Lecturer: Madhu Sudan\\
Problem Set 1 \hfill
Due: Friday, March 6, 2015
\\
\section*{Instructions}
\begin{description}
\item[Goal:] The goal of this problem set is to induce some ``finite field''
thinking. So while it would be great if you can solve the problem without
consulting texts, if that makes things better feel free to do so.
\item[Collaboration:]
Collaboration is allowed, but try to think of the solutions you eventually
came up with (possibly collaboratively) in isolation and make sure you
understand it (and internalize it).
\item[Writeup:]
The due date is a recommendation rather than a deadline. It is best if you
think of the questions and answers sooner rather than later. The goal of
this pset is only to get you to think about potentially weak points in your
background. So submission of answers is optional - but I would like to get
an email acknowledging that you have thought about the questions and know
how to answer them. If you have any questions, email me. If you think you
would like to run your solutions by me to verify them or to check if there
are alternate solutions, do write them up and send to me by email.
\end{description}
\section*{Exercises}
\begin{enumerate}
\item
Prove $\F_q[x]/(g(x))$ is a field of cardinality $q^d$ if and only if
$g$ is an irreducible polynomial of degree $d$.
\item
Prove that the multiplicative group of the finite field $\F_q$, denoted
$\F_q^*$ is cyclic. Conclude that every field has a primitive element.
\item If $\omega$ is a primitive element in $\F_{q^d}$ then prove that
$\omega$ is a generator of $\F_{q^d}$ over $\F_q$.
\item Let $\alpha \in \F_{q^d}$ have $g \in \F_q[x]$ as it minimal polynomial.
Prove that $\K = \F_q[x]/(g)$ is a subfield of $\F_{q^d}$ and so the degree
of $g$ divides $d$.
\item
Prove the identity $x^q - x = \prod_{a \in \F_q} (x-a)$.
\item
Prove $x^{q^d} - x = \prod_{g \in {\cal P}_{q,d}} g(x)$ where
$${\cal P}_{q,d} = \{g \in \F_q[x] | g \mbox{ irreducible, monic, with }
\deg(g) | d \}.$$
\item
Prove that if $g \in \F_q[x]$ is irreducible of degree $d$,
then it splits completely in $\F_{q^d}$.
(In class we claimed that $g$ has a root in $\F_q[x]/(g)$,
and if one combines this with the assertion that fields of cardinality
$q^d$ are
unique then it follows that $\F_{q^d}$ has a root of $g(x)$.
But the way to prove
the uniqueness is by proving that $g$ has a root in $\F_{q^d}$.)
\item
Prove that there is a unique field of any given cardinality: In particular
suppose $g \in \F_p[x]$ is irreducible of degree $a\cdot b$ and $h \in
\F_{p^a}[x]$ is irreducible of degree $b$. Then prove that
$\F_p[x]/(g(x)) \cong \F_{p^a}[x]/(h(x))$.
\item Write down the full details of the reduction alluded to in the beginning of Lecture 7 reducing
factorization of a polynomial $f \in \F_q[x]$ with all irreducible factors
having degree $d$, to root finding in $\F_{q^d}$.
\end{enumerate}
\end{document}