\documentclass[11pt]{article}
\usepackage{amsmath}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\ah}{\alpha}
\newcommand{\lam}{\lambda}
\newcommand{\gam}{\gamma}
\newcommand{\ol}{\overline}
\newcommand{\noi}{\noindent}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\beq}{\begin{quote}}
\newcommand{\enq}{\end{quote}}
\newcommand{\hsone}{\hspace*{1cm}}
\newcommand{\hstwo}{\hspace*{2cm}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Algebra Assignment 6 Solutions}
\end{center}
\ben
\item Let $p$ be a prime of the form $p=3k+1$. Let $g$ be a generator, so
that the elements of $Z_p^*$ can be written $1,g,g^2,\ldots,g^{3k-1}$ with
$g^{3k}=1$.
\ben
\item Show that there is an element $\omega\in Z_p^*$ with $\omega\neq 1$ and
$\omega^3=1$.
\So Easy! Take $\omega = g^k$. Then $\omega^3=g^{3k}=1$. Another one that works is
$g^{2k}$.
\item (*) Show that there exists $\eta\in Z_p^*$ with $\eta^2=-3$. [Hint: The formula
for $\omega$ in the complex numbers will be helpful!]
\So The formula in $C$ is that $\omega=\frac{1}{2}(-1+\sqrt{-3})$ so that $2\omega+1=\sqrt{-3}$.
So lets try $\eta=2\omega+1$. So $\eta^2=4\omega^2+4\omega+1$. As $\omega$ satisfies $x^3-1=0$
and $\omega\neq 1$, it satisfies $\omega^2+\omega+1=0$. Thus $\eta^2=4(\omega^2+\omega+1)-3 = -3$.
[Caution: We don't know {\em a priori} that this will work. After all, $C$ is not $Z_p$. But we
see an anology and try something. Then -- hooray! -- it leads to a solution.]
\een
\item Now suppose $p$ be a prime of the form $p=3k+2$.
\ben
\item Again using a
generator $g$ show that there is no
element $\omega\in Z_p^*$ with $\omega\neq 1$ and $\omega^3=1$.
\So Write $\omega=g^i$. Then $g^{3i}=1$. As $g$ has order $p-1=3k+1$ we must have $(3k+1)|3i$
so that $(3k+1)|i$ which would give $\omega=1$. Alternatively, $Z_p^*$ has $p-1=3k+1$ elements
so that it can't have an element of order $3$.
\item (*) Show that there does not exist $\eta\in Z_p^*$ with $\eta^2=-3$.
\So Reverse the above argument, setting $\omega=\frac{1}{2}(-1+\eta)$. Then
\[ \omega^2= \frac{\eta^2-2\eta + 1}{4} = \frac{-2\eta-2}{4} = \frac{-\eta-1}{2} = -\omega-1 \]
so $\omega^3=1$ and $\omega\neq 1$ which doesn't exist.
\\ {\tt Note: Together we get a necessary and sufficient condition for when $-3$ is a square
in $Z_p$. There is a result in Number Theory called The Law of Quadratic Reciproicity, which
we do not cover in this course, which tells you when $a$ is a square in $Z_p$.}
\een
\item Let $F$ be a finite field with $q=p^n$ elements. Define
$\sig: F\ra F$ by $\sig(\ah)=\ah^p$.
\ben
\item Show that $\sig(\ah\beta)=\sig(\ah)\sig(\beta)$ for all $\ah,\beta\in F$.
\item Show that $\sig(\ah +\beta)=\sig(\ah)+ \sig(\beta)$ for all $\ah,\beta\in F$.
\item Show that $\sig(\ah^{-1})=\sig(\ah)^{-1}$ for all nonzero $\ah\in F$.
\item (*) Show that $\sig$ is injective. That is, show that if $\sig(\ah)=\sig(\beta)$ then $\ah=\beta$.
\item Deduce that $\sig$ is surjective. (Use that $|F^*|=p^n-1$.)
\een
{\tt Note:} Together this gives that $\sig$
is an automorphism, an isomorphism from $F$ to itself. $\sig$
is often called the Frobenius automorphism.]
\So The easy ones are
\[ \sig(\ah\beta)=\ah^p\beta^p = \sig(\ah)\sig(\beta) \]
and
\[ \sig(\ah^{-1})=\ah^{-p}= (\ah^p)^{-1}=\sig(\ah)^{-1} \]
and the amazing one is
\[ \sig(\ah+\beta)= (\ah+\beta)^p = \ah^p + \beta^p = \sig(\ah)+ \sig(\beta) \]
The critical middle equality is because by the Binomial theorem
\[ (\ah+\beta)^p = \ah^p + \sum_{i=1}^{p-1}{p\choose i}\ah^{p-i}\beta^i + \beta^p \]
The binomial coefficients have a $p$ in the numerator and not in the denominator and
so are divisible by $p$ and hence are zero (!!) in a field of characteristic $p$.
Clearly $\sig(\ah)=\ah^p=0$ has only the solution $\ah=0$.
If $\ah^p=\sig(\ah)=\sig(\beta)=\beta^p\neq 0$ then, setting $\gam=\ah/\beta$, $\gam^p=1$.
The order of $\gam$ must divide $p^n-1$ so it can't be $p$, but it must divide $p$ so it
must be $1$. That is, $\gam=1$ and $\ah=\beta$, proving injectivity. As $F$ is a {\em finite}
set an injective map from it to itself must be surjective by pigeonhole.
\item Let $F=Z_3[x]/(x^2+1)$.
\ben
\item List the elements of $F$.
\So $0,1,2,x,x+1,x+2,2x,2x+1,2x+2$.
\item Find a generator $g$ of $F^*$.
\So $x$ doesn't work as $x^2=2$ so $x^4=1$. But $g=x+1$ works. The powers are
$g^2=x^2+2x+1=2x$, $g^3=2x^2+2x=2x+1$, $g^4=(g^2)^2=4x^2=8=2=-1$ and
once we get half way we know we are done as the order must divide $8$ and is
now bigger than $4$.
\item For each $\ah\in F$ find the minimal polynomial $p_{\ah}(y)$
of $\ah$ in $Z_3[y]$.
\So For $\ah=0,1,2$ the minimal polynomial is simply $y-\ah$. The others have
been ordered to indicate the pairs with the same minimal polynomial.
\\ For $\ah=x$, $\ah^2=x^2=2$, $p_{\ah}(y)=1+y^2$.
\\ For $\ah=2x$, $\ah^2=4x^2=2$, $p_{\ah}(y)=1+y^2$.
\\ For $\ah=x+1$, $\ah^2=x^2+2x+1=2x$, $p_{\ah}(y)=y^2+y+2$.
\\ For $\ah=2x+2$, $\ah^2=x^2+2x+1=2x$, $p_{\ah}(y)=y^2+2y+2$.
\\ For $\ah=x+2$, $\ah^2=x^2+x+1=x$, $p_{\ah}(y)=y^2+2y+2$.
\\ For $\ah=2x+1$, $\ah^2=x^2+x+1=x$, $p_{\ah}(y)=y^2+y+2$.
\item Factor $y^9-y$ in $F[y]$.
\So As all $\ah\in F$ are roots this factors into nine linear terms
\[ y^9-y = y(y-1)(y-2)(y-x)(y-(x+1))(y-(x+2))(y-2x)(y-(2x+1))(y-(2x+2)) \]
\item Factor $y^9-y$ in $Z_3[y]$. Show how the factors in $F[y]$ join
to form factors in $Z_3[y]$.
\So We still get $y(y-1)(y-2)$ are before. For other $\ah\in F$ the minimal
polynomial of $\ah$ over $Z_3[y]$ gives the factor. So we get
\[ y^9-y = y(y-1)(y-2)(y^2+1)(y^2+y+2)(y^2+y+2) \]
Each of the three quadratics has two roots $\ah,\beta\in F$ from above and so
further factors into $(y-\ah)(y-\beta)$ in $F[y]$.
\een
\item Assume the following theorem: Let $q=p^n$ and set $f(x)=x^q-x$.
Then, in $Z_p[x]$, $f(x)$ factors into the product of all monic irreducible
(over $Z_p[x]$) polynomials of all degrees $d$, where $d$ is a divisor
(including $1$ and $q$) of $q$.
\ben
\item How many irreducible quadratic polynomials are there over $Z_5[x]$?
(Count degrees in the factorization of $x^{25}-x$.)
\So This degree $25$ polynomial factors into $5$ linear polynomials and $A$
quadratics, where $A$ is the number we are seeking. So $25=5+2A$ and $A=10$.
\item How many irreducible cubic polynomials are there over $Z_5[x]$?
(Count degrees in the factorization of $x^{125}-x$.)
\So This degree $125$ polynomial factors into $5$ linear polynomials and $B$
cubics, where $B$ is the number we are seeking. So $125=5+3B$ and $B=40$.
\item (*)
How many irreducible polynomials of degree six are there over $Z_5[x]$?
(Count degrees in the factorization of $x^{15625}-x$.)
\So This degree $15625$ polynomial factors into $5$ linear polynomials and $10$
quadratics, $40$ cubics, and $D$ degree six polynomials,
where $D$ is the number we are seeking. So $15625=5+10(2)+40(3)+6D$ and $D=2580$.
\een
\een
\end{document}