\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{\del}{\delta}
\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 V63.0349 \\ Assignment $\omega$ Solutions}
\end{center}
\ben
\item Assume that {\em both} $p$ and $2^p-1$ are primes. ({\tt Comment:}
When this occurs $2^p-1$ is called a {\em Mersenne prime}.) Let
$f(x)$ be an irreducible polynomial over $Z_2$ of degree $p$.
\ben
\item Show $f(x)|(x^{2^p-1}-1)$.
\So To say that $f(x)|(x^j-1)$ is the same as saying $x^j=1$ in
$F=Z_2[x]/(f(x))$. As $F$ is a field with $2^p$ elements,
$|F^*|=2^p-1$ and so any element of $F^*$ to the power $2^p-1$ is
one, in particular $x$ to that power is $1$.
\item Show for all $1\leq i < 2^p-1$ that $f(x)$ does not divide $x^i-1$.
\So This is saying (given the first part) that $x$ has order $2^p-1$
in $F$. From the first part the order of $x$, $o(x)$, divides $2^p-1$.
The order can't be one so, as $2^p-1$ is assummed prime, it must be
$2^p-1$.
\item Show that $x$ is a generator of $Z_2[x]/(f(x))$.
\So This field has $2^p$ elements so its multiplicative group has
$2^p-1$ elements. And, above, we just said $x$ has order that
number, so it is a generator. (Easier: In a group with a prime
number of elements (here $2^p-1$) every element except the
identity is a generator.
\een
\item Consider the linear recursion
\[ u_n = 4u_{n-1}-5u_{n-2} \]
with initial conditions $u_0=0,u_1=1$.
\ben
\item Give the solution using complex numbers.
\So The equation $x^2-4x+5$ has solutions $\ah_1=2+i$ and
$\ah_2=2-i$
the initial conditions give equations $0=c_1+c_2$ and
$1=c_1(2+i)+c_2(2-i) = c_1(2i)$ so that $c_1 = -i/2, c_2=i/2$
and
\[ u_n = \frac{-i}{2}[(2+i)^n-(2-i)^n] \]
\item Rewrite the solution in terms of real exponential
and trigonometric functions.
\So Write $2+i=\sqrt{5}e^{i\theta}$ with $\theta=\arctan(1/2)$.
Then \[ (2+i)^n=5^{n/2}[\cos(n\theta)+i\sin(n\theta) \]
and
Then \[ (2+i)^n-(2-i)^n=5^{n/2}[2i\sin(n\theta) \]
so that
\[ u_n= 5^{n/2}\sin(n\theta) \]
\item Discuss the asymptotic nature of $u_n$ as $n\ra\infty$.
(It might help to work out the first ten or so terms!)
\So The exponential is getting bigger (fast!) but the $\sin$ is
oscillating between $-1$ and $+1$ so the product has bigger and
bigger oscillations. (Sometimes this behavior is called driving/driven or
positive feedback. When the exponential is decaying -- like
$2^{-n}\sin(n\theta)$ -- it is called damping but the case of
the increasing exponential doesn't seem to have a standard name.)
You can actually see it in the first few
terms:
\[ 0,1,4,11,24,41,44,-29, -336, -1489, -7636 -37989, \]
\[ -113776, -265159,
-491756, -641229, -106136, +2781601 \]
As $\theta$ is about $26$ degrees and the $\sin$ keeps its sign
for $180$ degrees, the sequence keeps its sign for roughly (since
it has to be an integer) $180/26$ or about seven terms.
\een
\item
Let $F$ be a finite field and let $\ah,\beta$ be
distinct nonzero elements of $F$. Let $\ah$ have
order $r$ and let $\beta$ have order $s$.
(The order of an element $\gam$ is the least
positive $m$ with $\gam^m=1$.) Let $M=lcm(r,s)$.
Let $a,b$ be nonzero elements of $F$ and define
a sequence $u_n=a\ah^n+b\beta^n$
\ben
\item Show $u_{n+M}=u_n$ for all $n$.
\So $u_{n+M}= a\ah^n\ah^M + b\beta^n\beta^M$ but as $a,b$ divide $M$,
$\ah^M=\beta^m=1$ so $u_{n+M}=u_n$.
\item (*) Show that $M$ is the period of the sequence $u_n$. That is,
show there is no $L$, $1\leq L < M$, with $u_{n+L}=u_n$ for all $n$.
\So
$u_{n+L}= a\ah^n\ah^L + b\beta^n\beta^L$ so if this is
$u_n=a\ah^n+b\beta^n$, subtracting would give (for all $n$)
$0 = a(\ah^L-1)\ah^n + b(\beta^L-1)\beta^n$. But (as shown
in class) the sequences $\ah^n$ and $\beta^n$ are independent
so then $a(\ah^L-1)=0$ and $b(\beta^L-1)=0$. As $a,b\neq 0$,
$\ah^L=1$ so $a|L$ and $\beta^L=1$ so $b|L$ so $M|L$.
\een
\item Let $f(x)\in Z[x]$, a polynomial of degree $n$. Suppose $f(x)$
has $n$ {\em distinct} roots $\ah_1,\ldots,\ah_n\in C$. Call a prime
$p$ bad (given $f$) if $f(x)$ has a multiple factor when considered
in $Z_p[x]$. (For example, $x^2+x-8$ is $(x+2)^2$ in $Z_3[x]$ and
$(x+6)^2$ in $Z_{11}[x]$.) Prove that there can be only a {\em finite}
(maybe zero) number of bad primes $p$.
\So From our theorem on multiple roots $\gcd(f(x),f'(x))=1$ in $Q[x]$.
Thus there exist $a(x),b(x)\in Q[x]$ with $a(x)f(x)+b(x)f'(x)=1$.
Multiplying out the denominators we get $c(x),d(x)\in Z[x]$ with
$c(x)f(x)+d(x)f'(x)= F$ for some integer $F$. Now suppose $p$ does
not divide $F$. We consider this as an equation in $Z_p[x]$ and
multiply by $F^{-1}$ so that $c_1(x)f(x)+d_1(x)f'(x)=1$ where
$c_1(x)=c(x)/F$ and $d_1(x)=d(x)/F$. That is, $\gcd(f(x),f'(x))=1$
in $Z_p[x]$ and thus $f(x)$ cannot have multiple factors in $Z_p[x]$.
When $p$ does divide $F$ we don't know if there are multiple factors
or not, but there are only finitely many such $p$.
\een
\end{document}