\documentclass[12pt]{article}

\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amscd}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}

\theoremstyle{definition}
\newtheorem{defn}{Definition}
\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{cor}{Corollary}

\renewcommand{\H}{\mathbf{H}}
\newcommand{\R}{\mathbf{R}}
\newcommand{\C}{\mathbf{C}}
\newcommand{\Z}{\mathbf{Z}}
\newcommand{\Q}{\mathbf{Q}}
\newcommand{\F}{\mathbf{F}}
\DeclareMathOperator{\ind}{Index}
\DeclareMathOperator{\irr}{Irred}


\title{Math 129, Test 1}
\author{Bryden Cais}

\begin{document}
\maketitle

\section{The Prime Divisors of $\ind(K)$}
\begin{enumerate}
	\item Let $q=p^r$ and let $\alpha$ be a root of a degree $r$ monic irreducible polynomial in $\F_p[X]$.
	Then $\F_p[\alpha]$ is a degree $r$ extension of $\F_p$ and is therefore isomorphic to $\F_q$.
	We therefore have a surjective map $\Z[\alpha]\longrightarrow \F_q$, which shows that $F_q$ is
	primitive.

	\item In one direction, suppose $A=\Z[\alpha]$ is primitive and that 
	$A=k_1\times k_2\times\cdots\times k_m$ is a product of finite fields.  Write
	$\alpha=(\alpha_1,\ldots,\alpha_m)$ with $\alpha_j\,\in\,k_j$ for each $j$.  Certainly,
	$\Z[\alpha_j]=k_j$ for each $j$.  Notice that for any
	polynomial $f$ we have $f(\alpha)=(f(\alpha_1),\ldots,f(\alpha_m))$.  Therefore, since 
	$(1,\ldots,1,0,1,\ldots,1)\,\in\,A=\Z[\alpha]$, where the $0$ is in the $i$ th position, we have
	some polynomial $f\,\in\,\F_p[X]$ such that $f(\alpha_j)=\delta_{ij}$.  Thus, 
	$\irr(\alpha_i)|f$ and $\irr(\alpha_j)\not|f$ for $i\not=j$.  Hence, we have distinct monic irreducible
	polynomials $P_i,\ldots,P_m\,\in\,\F_p[X]$ with $\deg(P_i)=f_i=[k_i:\F_p]$ since $k_i=\Z[\alpha_i]$.

	In the other direction, suppose that $P_i,\ldots,P_m\,\in\,\F_p[X]$ with $\deg(P_i)=f_i=[k_i:\F_p]$
	are such polynomials.  Then let $\alpha_i$ be a root of $P_i$ in some splitting field and set
	\begin{eqnarray*}
	    \alpha\ =\ (\alpha_1,\ldots,\alpha_m).
	\end{eqnarray*}
	Let $R_i$ be the polynomial in $\F_p[X]$ given by $P_1\cdots\hat{P_i}\cdots P_m$, where the hat
	indicates omission.  Define $\beta_i=R_i(\alpha_i)$, and set $B_i=\irr(\beta_i)$.  Clearly,
	$\beta_i\not=0$, so that $B_i(0)\not=0$ since $B_i$ is irreducible and $\deg(B_i)\geq 1$.  Now let
	\begin{eqnarray*}
	    Q_i(X)=\frac{-X}{B_i(0)}(B_i(R_i(X))-B_i(0)). 
	\end{eqnarray*}
	It is not difficult to see that $Q_i(X)\,\in\,\F_p[X]$ and 
	$Q_i(\alpha)=(0,\ldots,0,\alpha_i,0,\ldots,0)$.
	Since $\Z[\alpha_i]=k_i$, we have shown that $A=\Z[\alpha]$ is primitive.

	\item One direction is trivial: Since $I^e\subset I$, we have $R/I^e\supset R/I$, so that
	if $R/I^e$ is primitive, $R/I$ is also.  Now suppose that $R/I$ is primitive and that
	\begin{eqnarray*}
	    I\ =\ P_1^{r_1}P_2^{r_2}\cdots P_m^{r_m}
	\end{eqnarray*}
	for distinct prime ideals $P_j$ and integers $r_j>0$.  By the chinese remainder theorem, we then have
	\begin{eqnarray*}
	    R/I^e\ =\ R/P_1^{er_1}\times R/P_2^{er_2}\times\cdots\times R/P_m^{er_m},
	\end{eqnarray*}

	\item Let $I=I_1\cdots I_m$ with $N(I_j)=p_j^{f_j}$ for distinct $p_j$.  Then
	the ideals $I_i,I_j$ are relatively prime for $i\not=j$.  In other words, the chinese remainder
	theorem applies and gives
	\begin{eqnarray*}
	    R/I\simeq R/I_i\times \cdots\times R/I_m.
	\end{eqnarray*}
	Clearly, if $R/I$ is primitive, then $R/I_i$ is primitive for every $i$.  We already proved this in 
	item $1$.  (Notice the proof in this direction works even without the hypothesis that all of the factors
	be finite fields.)  Assume now that $R/I_i$ is primitive for each $i$, say $R/I_i\simeq\Z[\alpha_i]$.  
	Let $g_i\,\in\,\Z[X]$ be the irreducible polynomial of $\alpha_i$.  Then we have
	$R/I_i\simeq\Z[X]/g_i(X)$.  We then apply the chinese remainder theorem again to give
	\begin{eqnarray*}
	    R/I\simeq \Z[X]/g_1\cdots g_m.
	\end{eqnarray*}
	Now let $\alpha$ be the image of $X$ in $R/I$ under the above isomorphism.  Clearly, then, $\alpha$
	generates $R/I$ and hence $R/I$ is primitive.

	\item Using the unique decomposition of $I$ into prime ideals, we write
	$I=I_1\cdots I_m$ where $N(I_i)$ is a power of $p_i$ and the $p_i$ are distinct primes.
	By item $4$, $R/I$ is primitive if and only if $R/I_i$ is primitive for all $i$.  We factor $I_i$
	into a product of prime ideals as $I_i=P_1^{e_1}\cdots P_m^{e_m}$, for distinct prime ideals $P_j$.
	Notice that every prime ideal $P\supset I$ of norm a power of $p_i$ is one of the $P_j$.  

	Notice that our proof for item $4$ only uses the fact that $I_i,I_j$ are relatively
	prime for $i\not=j$.  Therefore, since the $P_j$ are distinct, they are all relatively
	prime so that $R/I_i$ is primitive if and only if $R/P_j^{e_j}$ is primitive for each
	$j$.  By item $3$, this is the case if and only if $R/P_j$ is primitive for each $j$, that is,
	again by $4$, if and only if
	\begin{eqnarray*}
	    R/P_1P_2\cdots P_m
	\end{eqnarray*}
	is primitive.  Now we are in the situation of item $2$, and we see that this quotient is primitive
	if and only if there exist distinct monic irreducible polynomials $g_j\,\in\,\F_{p_i}[X]$ with $\deg(g_j)=f_j$ 
	where $f_j=R/P_j=N(P_j)$. (since all the $P_j$ have norm a power of $p_i$, and therefore the quotient 
	is a product of finite fields of characteristic $p_i$).  

	If the number of prime ideals containing $I$ of norm $p_i^f$ is greater than the number
	of irreducible monic polynomials of degree $f$ in $\F_p[X],$ we see that there cannot possibly
	be the distinct polynomials as in item $2$, so that $R/I_i$ is not primitive.  Conversely,
	if there are at least as many distinct irreducible polynomials of degree $f$ as there are prime
	ideals containing $I_i$ of norm $p_i^f$, then $R/P_1\times\cdots\times R/P_m$ is primitive, and hence
	$R/I_i$ is primitive.  Following the chain of reasoning backwards, we see that this completes the proof.

	\item In one direction, suppose that the $P_1,\ldots,P_m$ are prime ideals each with norm $p^f$ and
	that $m$ is strictly greater than the number of irreducible monic polynomials of degree $f$ in $\F_p[X]$.
	Let $I=P_1\cdots P_m$.  Then item $5$ tells us that $R/I$ is not primitive.  Since $N(I)$ is a power
	of $p$, $\# R/I$ and hence $\# (R/I)/\Z[\alpha]$ is a power of $p$ also.  Since $R/I$ is not primitive,
	$\# (R/I)/\Z[\alpha]$ is a nontrivial power of $p$ for any $\alpha$.  This implies that $p|\#R/\Z[\alpha]$
	for any $\alpha$, and hence $p|\ind(K)$.  

\end{enumerate}

\section{A Nice Ring}
\begin{enumerate}
	\item To show commutativity, notice that as $d$ ranges over all divisors of $n$, so does $n/d$, so that
	we may reindex the sum defining $f*g$ to obtain
	\begin{eqnarray*}
	    (f*g)(n)&=&\sum_{d|n}f(d)g(n/d)\\
	    &=&\sum_{d|n}f(n/d)g(d)\\
	    &=&(g*f)(n).
	\end{eqnarray*}
	Associativity of $*$ is proved similarly.  We have
	\begin{eqnarray*}
	    (f*(g*h))(n)&=&\sum_{d|n}\sum_{d^{\prime}|(n/d)}f(d)g(d^{\prime}h(n/dd^{\prime}))\\
	    &=&\sum_{\delta|n}\sum_{d|\delta}f(d)g(\delta/d)h(n/d)\\
	    &=&((f*g)*h)(n)
	\end{eqnarray*}
	upon replacing $dd^{\prime}$ by $\delta$ and reindexing the sum.  Let
	\begin{eqnarray*}
	e(n)\ =\ 
	\begin{cases}
	    1 & \ \text{if}\quad n=1\\
	    0 & \ \text{otherwise}
	\end{cases}.
	\end{eqnarray*}
	Then we obviously have $(f*e)(n)=f(n)$ for all $n$ and any $f\,\in\,\mathcal{L}$,
	so that $e$ is the identity element.  We finally have to check some trivial properties, for example
	that 
	\begin{eqnarray*}
	    (f+g)*h&=&f*h+g*h\quad\text{and}\\
	    f*\lambda\cdot g&=&\lambda\cdot f*g,
	\end{eqnarray*}
	which follow from 
	\begin{eqnarray*}
	    \sum_{d|n}(f(d)+g(d))h(n/d)&=&\sum_{d|n} f(d)h(n/d)+\sum_{d|n} g(d)h(n/d),\\
	    \sum_{d|n} f(d)\lambda g(n/d)&=&\lambda\sum_{d|n} f(d)g(n/d).
	\end{eqnarray*}
	Now if $f\,\in\,\mathcal{L}$ and $f(1)=0$ then $(f*g)(1)=f(1)g(1)=0$ no matter what $g$ is, so 
	that $f$ is not invertable.  Conversely, if $f(1)\not=0$, then we may define $f^{-1}(1)=1/f(1)$,
	and we can define $f^{-1}(n)$ for $n>1$ inductively as 
	\begin{eqnarray}
	\label{inv}
	    f^{-1}(n)\ =\ -\frac{1}{f(1)}\sum_{\substack{d|n\\d<n}} f^{-1}(d)f(n/d).
	\end{eqnarray}
	It is then not difficult to see that $f*f^{-1}=e$.
	Finally, suppose that $f*g\equiv 0$.  Suppose that $g\not\equiv0$.  Let $m$ be the least integer
	for which $g(m)\not=0$.  Then since $(f*g)(m)=0$, we have 
	\begin{eqnarray*}
	    0\ =\ \sum_{d|m}f(d)g(m/d)\ =\ f(1)g(m), 
	\end{eqnarray*}
	so that $f(1)=0$.  Now we show by induction that $f\equiv 0$.  Suppose that $f(d)=0$ for all
	$d<k$.  Since $(f*g)(mk)=0$, we have
	\begin{eqnarray*}
	    0&=&\sum_{d|mk}f(d)g(n/d)\\
	    &=&\sum_{\substack{d|mk\\d<k}}f(d)g(mk/d)+\sum_{\substack{d|mk\\d>k}}f(d)g(mk/d)+g(m)f(k)\\
	    &=&g(m)f(k), 
	\end{eqnarray*}
	since $f(d)=0$ for $d<k$ and $g(mk/d)=0$ for $d>k$ because we chose $m$ to be the least integer
	for which $g(m)$ was nonzero.  Thus, we have $f(k)=0$ and by induction, $f\equiv 0$ as claimed.
	
	\item We show that $f*g$ is multiplicitive if $f,\ g$ are.  Let $(m,n)=1$.  Then any $d$ with 
	$d|mn$ may be written \textit{uniquely} as $d=d_1d_2$ where $d_1|m$ and $d_2|n$.  We need only
	take $d_1=(m,d)$ and $d_2=(n,d)$.  Thus there is a bijection between divisors $d$ of $mn$ and
	pairs $(d_1,d_2)$ with $d_1|m$, $d_2|n$ and $d_1d_2=d$.  (Since the other direction is clear).
	Therefore, we have
	\begin{eqnarray}
	\label{mult1}
	    \sum_{d|mn}f(d)g(mn/d)\ =\ \sum_{d_1|m}\sum_{d_2|n}f(d_1d_2)g(mn/d_1d_2).
	\end{eqnarray}
	Again, since $(m,n)=1$, we have $(d_1,d_2)=(m/d_1,m/d_2)=1$ for any $d_1|m$ and $d_2|n$.
	Thus, since $f,g$ are multiplicative, we find
	\begin{eqnarray}
	\label{mult2}
	    \sum_{d|mn}f(d)g(mn/d)&=&\sum_{d_1|m}\sum_{d_2|n}f(d_1)f(d_2)g(m/d_1)g(n/d_2)\\
	    &=&\sum_{d_1|m}f(d_1)g(m/d_1)\sum_{d_2|n}f(d_2)g(n/d_2)\\
	    &=&(f*g)(m)(f*g)(n).
	\end{eqnarray}
	Since $(f*g)(1)=f(1)g(1)=1$, $f*g$ is multiplicative.
	Obviously, $e$ is multiplicitive.  We may use our definition \ref{inv} to show by induction
	that $f^{-1}$ is also multiplicitive.  Since $f(1)=1$, we have $f^{-1}(1)=1$.  Now suppose that
	for all $m,n\,<N$, we have $f^{-1}(mn)=f^{-1}(m)f^{-1}(n)$ whenever $(m,n)=1$.  Then
	\begin{eqnarray*}
	    f^{-1}(mN)&=&-\frac{1}{f(1)}\sum_{\substack{d|m\\d<m}}\sum_{d^{\prime}|N}f^{-1}(dd^{\prime})
	    f(mN/dd^{\prime})\\
	    &&-\frac{f^{-1}(m)}{f(1)}\sum_{\substack{d^{\prime}|N\\d^{\prime}<N}}f^{-1}(d^{\prime})
	    f(N/d^{\prime})\\
	    &=&f^{-1}(m)f^{-1}(N),
	\end{eqnarray*}
	where we have used the same summation reindexing techniques as in \ref{mult1}, and \ref{mult2} and
	the assumption that $(m,N)=1$.  This shows, in fact, that $f^{-1}$ is multiplicitive for all
	$(m,n)\leq N$ with $(m,n)=1$, so by induction, $f^{-1}$ is multiplicitive.  Obviously, if $f,g$
	are multiplicitive, then $f\times g$ is also multiplicitive since we have $f(1)g(1)=1$ and
	\begin{eqnarray*}
	    (f\times g)(mn)&=&f(mn)g(mn)=f(m)f(n)g(m)g(n)\\&=&(f(n)g(n))(f(m)g(m))=(f\times g)(n)(f\times g)(m).
	\end{eqnarray*}
	This shows that the set of multiplicitive functions is a subgroup of $\mathcal{L}^*$ which is
	stable under $\times$.

	\item Define $z$ by $z(n)=1$ for all $n$, and let $\mu$ be the inverse of $z$ under $*$.
	First, we clearly have $\mu(1)\cdot 1=1$ so that $\mu(1)=1$.  Now for any prime $p$,
	we must have $\mu(p)+\mu(1)=0$ so that $\mu(p)=-1$ for all primes.  We also have
	\begin{eqnarray*}
	    \mu(1)+\mu(p)+\mu(p^2)+\cdots+\mu(p^r)=0
	\end{eqnarray*}
	for any $r\geq 2$ so that 
	\begin{eqnarray*}
	    \mu(p^2)+\cdots+\mu(p^r)=0
	\end{eqnarray*}
	for any $r\geq 2$ whence by induction, $\mu(p^r)=0$ for all $r\geq 2$.  Since $z$ is multiplicitive
	and $\mu$ is its inverse, $\mu$ is also multiplicitive.  Thus we have completely determined the 
	behavior of $
	\mu$ and have
	\begin{eqnarray*}
	\mu(n)\ =\ 
	\begin{cases}
	    1 & \ \text{if}\quad n=1\\
	    0 & \ \text{if}\quad\text{$n$ has a square factor}\\
	    (-1)^k & \ \text{if}\quad n=p_1p_2\cdots p_k
	\end{cases}
	\end{eqnarray*}
	where all the $p_j$ are distinct.  We note an interesting consequence:  Let 
	\begin{eqnarray*}
	f(n)=(z*g)(n)=\sum_{d|n}g(d).
	\end{eqnarray*}
	Then
	\begin{eqnarray*}
	\label{mobius}
	    (\mu*f)(n)=(\mu*z*g)(n)=(e*g)(n)=g(n).
	\end{eqnarray*}
	The converse is also clear.

	\item Let $\varphi(n)$ be Euler's phi function and let $i(n)=n$ for all $n$.  We know
	that $\varphi$ is multiplicitive, so that $\varphi*z$ is also multiplicitive.  Moreover,
	\begin{eqnarray*}
	    \sum_{d|p^r}\varphi(d)&=&\sum_{i=1}^r\varphi(p^i)\\&=&\sum_{i=1}^r \left(p^{i}-p^{i-1}\right)\\
	    &=&p^r.
	\end{eqnarray*}
	Therefore, decomposing any integer as a product of primes and applying the above, we have, by the
	multiplicitivity of $\varphi*z$ that $(\varphi*z)(n)=n$ for any $n$.

	\item We have
	\begin{eqnarray*}
	    z*z&=&\sum_{d|n}1,
	\end{eqnarray*}
	which obviously counts the number of divisors of $n$.  Similarly,
	\begin{eqnarray*}
	    i*z&=&\sum_{d|n}d,
	\end{eqnarray*}
	which clearly gives the sum of the divisors of $n$.

	\item Now suppose that $f$ is completely multiplicitive.  The fact that $\times f$ is
	a $\C$-algebra homomorphism of $(\mathcal{L},+,*,\cdot)$ will follow if we can show that
	it preserves the multiplicitive $*$ structure of $\mathcal{L}$, as the other requirements
	are trivial to check.  We have
	\begin{eqnarray*}
	    (f\times g)*(f\times h)(n)&=&\sum_{d|n} f(d)g(d)f(n/d)h(n/d)\\
	    &=&f(n)\sum_{d|n} g(d)h(n/d)\\
	    &=&f\times(g*h)(n)
	\end{eqnarray*}
	for all $n$.  We also have
	\begin{eqnarray*}
	    f*(\mu\times f)&=&\sum_{d|n} f(d)\mu(n/d)f(n/d)\\
	    &=&f(n)\sum_{d|n}\mu(n/d)\\
	    &=&f(n)\mu*z\\
	    &=&f(n)e(n)\\
	    &=&e(n)
	\end{eqnarray*}
	since $f(1)=1$.  Here we have used the fact that $\mu$ is the inverse under $*$ for $z$.  This
	shows that $\mu\times f$ is the inverse under $*$ of $f$.
\end{enumerate}

\section{Irreducible Polynomials Over $\F_q$}
\begin{enumerate}
	\item This is not difficult.  For irreducible polynomials of degree $1,2,3$ it is enough
	to check for polynomials that do not have a root in $\F_p$.  For degree $4$ polynomials, we
	need only exclude polynomials that have a root in $\F_p$ and polynomials that are the product of
	two irreducible quadratics.  Thus, we find
	\begin{eqnarray*}
	    I_2(1)&=&\{x,x+1\}\\
	    I_2(2)&=&\{x^2+x+1\}\\
	    I_2(3)&=&\{x^3+x^2+1,x^3+x+1\}\\
	    I_2(4)&=&\{x^4+x+1,x^4+x^3+1,x^4+x^3+x^2+x+1\}\\\\
	    I_3(1)&=&\{x,x+1,x+2\}\\
	    I_3(2)&=&\{x^2+1,x^2+x+2,x^2+2x+2\}\\
	    I_3(3)&=&\begin{Bmatrix}x^3+2x+1,x^3+2x+2,x^3+x^2+2,x^3+x^2+x+2,\\x^3+x^2+2x+1,x^3+2x^2+1,x^3+2x^2+x+1,
	    x^3+2x^2+2x+2\end{Bmatrix}\\\\
	    I_5(1)&=&\{x,x+1,x+2,x+3,x+4\}\\
	    I_5(2)&=&\begin{Bmatrix}x^2+x+1,x^2+x+2,x^2+2x+3,x^2+2x+4,\\x^2+3x+3,x^2+3x+4,x^2+4x+1,x^2+4x+2
	    \end{Bmatrix}.
	\end{eqnarray*}

	\item We first prove that 
	\begin{eqnarray*}
	    x^{q^m}-x \quad\text{divides}\quad x^{q^n}-x
	\end{eqnarray*}
	if and only if $m|n$.  First suppose that $m|n$, say $n=ms$.  We employ the identity
	\begin{eqnarray}
	\label{iden1}
	    y^d-1\ =\ (y-1)(y^{d-1}+y^{d-2}+\cdots+1)
	\end{eqnarray}
	with $y=q^m$ and $d=s$ to find that $q^m-1|q^n-1$.  Now set $y=x^{q^m-1}$ and $d=(q^n-1)/(q^m-1)$
	in \ref{iden1} to see that $x^{q^m}-x$ divides $x^{q^n}-x$, as claimed.  Conversely, if 
	$m\not|n$ then $a=q^n$ is not a power of $b=q^m$, so $\F_a$ is not an extension
	of $\F_b$.  But since the elements of $\F_a$ are precisely the roots of $x^a-x$,
	we see that $x^{b}-x$ cannot divide $x^a-x$.

	Now let $P\,\in\,I_q(d)$.  Let $\alpha$ be a root of $P$ in some extension of $\F_q$.  Then
	the field $K=\F_q(\alpha)$ has degree $d$ over $\F_q$ and its elements are the roots
	of $x^{q^d}-x$.  Since $\alpha$ is thus a root of $x^{q^d}-x$ and $P$ is irreducible,
	$P|x^{q^d}-x$, and hence by the above, $P|x^{q^r}-x$ for all $r$ divisible by $d$.  Conversely,
	if $P|x^{q^n}-x$ for some $n$, then the field generated by a root of $P$ must be a subfield of
	$\F_{q^n}$.  As above, this implies that $q^n$ is some power of $q^{d}$, that is,
	$d|n$.

	\item By the previous item, we see that the irreducible polynomials of degree $d$ in
	$\F_q[x]$ are precisely the degree $d$ irreducible factors of $X^{q^n}-x$ when $d|n$,
	and hence we may write
	\begin{eqnarray*}
	    x^{q^n}-x\ =\ \prod_{d|n}\prod_{P\in I_q(d)}P.
	\end{eqnarray*}
	Counting degrees now gives
	\begin{eqnarray}
	\label{rq}
	    \sum_{d|n}dr_q(d)\ =\ q^n.
	\end{eqnarray}

	\item Notice that we may rewrite \ref{rq} in the form 
	\begin{eqnarray*}
	    (i\times r_q)*z\ =\ q^n.
	\end{eqnarray*}
	We may apply \ref{mobius} to the above identity to obtain
	\begin{eqnarray*}
	    (i\times r_q)*z*\mu&=&\mu*q^n\\
	    &=&(i\times r_q)*e\\
	    &=&(i\times r_q),
	\end{eqnarray*}
	or what is the same thing,
	\begin{eqnarray*}
	    r_q(n)\ =\ \frac{1}{n}\sum_{d|n}\mu(n/d)q^d.
	\end{eqnarray*}

	\item From our formula for the m{\"o}bius function, we have
	\begin{eqnarray*}
	    nr_q(n)\ \geq\ q^n-(q+q^2+\cdots+q^{n-1})\ =\ q^n-\frac{q^n-q}{q-1}.
	\end{eqnarray*}
	Now using the fact that, for $n\geq 1$ we always have
	\begin{eqnarray*}
	    q^n\geq q,
	\end{eqnarray*}
	we see that 
	\begin{eqnarray*}
	    q^n(q-2)\geq q(q-2),
	\end{eqnarray*}
	with equality only if $q=2$ or $n=1$.  We expand this inequality and rearrange terms to obtain
	\begin{eqnarray*}
	    \frac{q^{n+1}-2q^n+q}{q-1}\geq q,
	\end{eqnarray*}
	that is,
	\begin{eqnarray*}
	    q^n-\frac{q^n-q}{q-1}\geq q,
	\end{eqnarray*}
	so that
	\begin{eqnarray*}
	    nr_q(n)\ \geq\ q,
	\end{eqnarray*}
	with equality only possible when $q=2$ or $n=1$.  It is clear that equality always holds when $n=1$
	since the ploynomial $x+r$ is irreducible for every $r\,\in\,\F_q$.  The possibility of equality 
	when $q=2$ may be ruled out as we are only summing over the divisors of a particular integer $m$ and
	not over all $k\leq m$.  (Moreover, the m{\"o}bius function is not always negative one).  In any case,
	it is easy to see that for $n\not=1$ and $q=2$, we have grossly underestimated things and equality
	above holds if and only if $n=1$.
\end{enumerate}

\section{A Bound for $p|\ind(K)$}

\begin{enumerate}
	\item Suppose that $p|\ind(K).$  Then item $6$ of section $1$ tells us that for some $f$, the number
	of monic irreducible polynomials of degree $f$ in $\F_p[X]$ is strictly less than the number of prime ideals
	$P_1,\ldots,P_m$ of norm $p^f$.  Then $m>r_p(f)$.  By item $5$ of
	section $3$, we have 
	\begin{eqnarray*}
	    m>r_p(f)\geq\frac{p}{f},
	\end{eqnarray*}
	or $mf>p$.  Since $[K:\Q]=n$, we have $[R:\Z]=n$ and therefore $[R:\Z[\alpha]]\leq n$ for any $\alpha$.
	Notice that $R/P_1\cdots P_m$ is an $\F_p$ vector space of dimension $mf$.  Since $\F_p$ is primitive,
	we write $\F_p=\Z[\alpha]$ for some alpha.  Then we see that $R$ may be considered (with the same sense
	of equality as above) as an $\F_p$ vector space of dimension at most $n$.  Since $R$ contains
	$R/P_1\cdots P_m$, comparing dimensions gives $n\geq mf$, and therefore $n>p$.

	\item Let $K=\Q(\sqrt{7},\sqrt{10})$.  Supose that $\mathcal{O}_K=\Z(\alpha)$ for some $\alpha$ and let $f$ 
	be the monic irreducible polynomial for $\alpha$ over $\Z$.  We will denote by $\bar{g}$ the reduction 
	modulo $3$ of the polynomial $g\,\in\,\Z[X]$.
	\begin{enumerate}
	    \item We know that $g(\alpha)$ is divisible by $3$ in $\Z[\alpha]$ if and only if $g$ is zero
	    in $\Z[\alpha]/3=\Z[X]/(f,3)=\Z_3[X]/\bar{f}$, that is, if and only if $\bar{f}$ divides
	    $\bar{g}$ in $\Z_3[X]$.

	    \item Let $\alpha_i=(1+(-1)^{\lfloor{\frac{i-1}{2}}\rfloor}\sqrt{7})(1+(-1)^{i-1}\sqrt{10})$, for
	    $1\leq i\leq 4$.  Clearly, the products $\alpha_i\alpha_j$ for $i\not=j$ are each divisile
	    by one of $N(1+\sqrt{7})=-6$, $N(1+\sqrt{10})-9$ in $\Z[\alpha]$.  Thus, in any case, $\alpha_i\alpha_j$
	    is divisible by $3$ in $\Z[\alpha]$ for $i\not=j$.  Obviously, the four embeddings of $K$ into $\C$
	    send each $\alpha_i$ to the four $\alpha_j$.  Thus, 
	    \begin{eqnarray*}
	        Tr(\alpha_i^n)\ =\ \alpha_1^n+\alpha_2^n+\alpha_3^n+\alpha_4^n.
	    \end{eqnarray*}
	    Since all of the cross terms $\alpha_i^k\alpha_j^m$ with $i\not=j$, $m,k>0$ are divisible
	    by $3$ in $\Z[\alpha]$, we have
	    \begin{eqnarray*}
		Tr(\alpha_i^n)\equiv (\alpha_1+\alpha_2+\alpha_3+\alpha_4)^n=4^n\mod 3
	    \end{eqnarray*}
	    in $\Z[\alpha]$.  However, since the trace is an integer, this congruence holds in $\Z$.  Therefore,
	    $Tr(\alpha_i^n)\equiv 1\mod 3$ in $\Z$, so it is not divisible by $3$.  Hence, $\alpha_i^n$ is
	    not divisible by $3$ in $\Z[\alpha]$ for any $n$.

	    \item Since we are supposing that $\Z[\alpha]=\mathcal{O}_K$, let $\alpha_i=f_i(\alpha)$ for each $i$.
	    Then by part a, we see that $\bar{f}|\bar{f_i}\bar{f_j}$ in $\Z_3[X]$ for $i\not=j$ but
	    $\bar{f}\not|\bar{f_i}^n$ for any $n$.  Therefore, since $\Z_3[X]$ is a UFD, $f$ has an irreducible
	    factor which does not divide $\bar{f_i}$ but does divide all ${f_j}$ for $i\not=j$.

	    \item This shows that $f$ has at least $4$ distinct irreducible factors over $\F_3[X]$.  Since
	    $f$ has degree at most $4$, we conclude that $f$ splits completely into $4$ distinct linear 
	    factors over $\F_3$.  But there are only $3$ distinct linear irreducible factors (up to units, of course)
	    in $\F_3[X]$ and this is a contradiction.  Thus, $\mathcal{O}_K\not=\Z[\alpha]$ for any $\alpha$.  That is,
	    $R=\mathcal{O}_K$ is not primitive.  This shows that $\ind(\alpha)>1$ for any $\alpha$.  Now we showed
	    on an earlier homework (Marcus, ex. $42$) that an integral basis for $R$ is 
	    \begin{eqnarray*}
		\left\{1,\sqrt{7},\sqrt{10},\frac{\sqrt{10}+\sqrt{70}}{2}\right\}
	    \end{eqnarray*}
	    and that $\mathrm{disc}(K)$ is $2^8\cdot 5^2\cdot 7^2$.  Using the previous item, we see that if
	    $p|\ind(K)$ then $p<4,$ so that $p=2$ or $3$.  We can rule out $p=2$ because $\Q((\sqrt{10}+\sqrt{70})/2)=K$
	    since the former is of degree $4$ and contained in $K$, but 
	    $\mathrm{disc}((\sqrt{10}+\sqrt{70})/2)=2^8\cdot 3^2\cdot 5^6\cdot 7^2$, and therefore 
	    $\ind((\sqrt{10}+\sqrt{70})/2)=75$.  Thus, $\ind(K)=3$.  Incidentally, one may compute a polynomial as in
	    section $5$ item $5$:
	    \begin{eqnarray*}
		P(X,Y,Z)\ =\ (2X^2-5Z^2)(2Y^2+2YZ-3Z^2)(14X^2-5(2Y+Z)^2).
	    \end{eqnarray*}
	
	
	\end{enumerate}

\end{enumerate}

\section{The Second Question}

\begin{enumerate}

	\item From class, (or Marcus pg. 36) we have the following result:
	Suppose that $K$ is a number field and $R$ its ring of integers.
	Let $\alpha\,\in\,R$ and suppose that $\alpha$ has degree $n$ over $\Q$.  Then there is an integral basis
	\begin{eqnarray*}
	    1,\frac{f_i(\alpha)}{r_1},\ldots,\frac{f_{n-1}(\alpha)}{d_{n-1}}
	\end{eqnarray*}
	where $f_i$ has degree $i$ and $d_1|d_1|\ldots|d_{n-1}$, the $d_i$ are uniquely determined, and
	\begin{eqnarray*}
	\mathrm{disc}(\alpha)=(d_1d_2\cdots d_{n-1})^2\mathrm{disc}(R).
	\end{eqnarray*}
	Therefore, $R$ has an integral basis of the form $1=\omega_1,\omega_2,\ldots,\omega_n$.

	\item Let $\alpha=\sqrt[3]{175}$.  The irreducible polynomial of $\alpha$ is $X^3-175$, form which we
	easily compute $\mathrm{disc}(\alpha)=-3^3\cdot 5^4\cdot 7^2$.  Now it can be shown (Marcus pg. 49)
	that in the above notation, $d_1^6|\mathrm{disc}(\alpha)$.  Therefore we conclude that $d_1=1$.  Notice
	that $\alpha^2/5=5^{1/3}\cdot 7^{2/3}$ is integral.  Therefore, $5|d_2$.  Again, from our discriminant
	computation, we see that $d_2|3\cdot 5^2\cdot 7.$  Set $f_2(\alpha)=\alpha^2+a\alpha+b$.  If $7|d_2$ then 
	$f_2(\alpha)/7$ is integral (from the theorem).  We see then by considering the trace of this element
	that $7|b$ since $Tr(\alpha)=(1+\omega+\omega^2)\alpha=0$.  Therefore, $(\alpha^2+a\alpha)/7$ is integral.
	We then cube this element and consider its trace, using the fact that the trace of $\alpha$ is $0$.
	We obtain $Tr((\alpha^2+a \alpha)^3/7^3)=525(175+a^3)/7^3$.  Therefore, $7|a^3$, from which we see that
	$7|a$ and that $\alpha^2/7$ is integral.  But this is false, so that $7\not|d_2$.  Now suppose that $25|d_2$.
	Again, $(\alpha^2+a\alpha+b)/25$ is integral so that by considering the trace, we see that $25|b$ and that
	$5^6|525(175+a^3)$, and hence $5|a$ so that $5|7$, a contradiction.  Thus, $25\not|d_2$.  We finally show
	that $3\not|d_2$.  Squaring $f_2(\alpha)/d_2$ shows that
	\begin{eqnarray*}
	    \frac{(a^2+2b)\alpha^2+(2ab+175)\alpha+(b^2+350a)}{d_2^2}
	\end{eqnarray*}
	is integral.  Therefore, since we can write this in terms of $\alpha$ and $f_2(\alpha)/d_2$, we must have
	that $d_2$ divides each of $(a^2+2b),(2ab+175),(b^2+350a)$.  If $3|d_2$ then these equations imply
	that $a\equiv b\equiv 1\mod 3$.  Therefore, $(\alpha-1)^2/3=(\alpha^2-2\alpha+1)/3\,\in\,R$.  Raising
	this element to the fourth power and considering its trace implies that $3^4|3^3\cdot 131\cdot 719$,
	which is a contradiction.  Therefore, $3\not|d_2$ and $d_2=5$.  Thus, we have an integral basis
	for $R$:
	\begin{eqnarray*}
	    \left\{1,175^{1/3},\frac{175^{2/3}}{5}\right\}.
	\end{eqnarray*}
	
	\item This is trivial: Since $x_1\,\in\,\Z$ and $\omega_1=1,$ we see that $\Z[\alpha]=\Z[\alpha-x_1]$ and therefore
	$\ind(\alpha)=\# R/\Z[\alpha]=\# R/\Z[\alpha-x_1]=\ind(\alpha-x_1)$.

	\item We will use the equation $\mathrm{disc}(\alpha)=\ind(\alpha)^2\mathrm{disc}(K)$ and the fact that
	$\mathrm{disc}(\alpha)=|\sigma_i(\alpha_j)|^2$ where $\sigma_i$ are the distinct imbedings of $K$ into $\C$
	and $\alpha_j=\alpha^j$.  Set
	\begin{eqnarray*}
	    \alpha=x_1\omega_1+\cdots+x_n\omega_n.
	\end{eqnarray*}
	Then $\ind(\alpha)=\ind(\alpha-x_1)$ by the previous item.  Clearly,
	\begin{eqnarray*}
	\begin{vmatrix}
	1 & \sigma_1(\alpha) & \cdots & \sigma_1(\alpha^{n-1})\\
	\vdots & & & \vdots\\
	1 & \sigma_n(\alpha) &\cdots & \sigma_n(\alpha^{n-1})
	\end{vmatrix}
	\end{eqnarray*}
	is a polynomial in $x_1,x_2,\ldots x_n$ with integral coefficients in a quadratic extension of $\Q$ (since any 
	automorphism at worst flips the sign of this determinant).  Moreover, this polynomial, call it 
	$Q(x_2,\ldots,x_n)$ satisfies $Q/\sqrt{\mathrm{disc}(K)}=\ind(\alpha)$.  Since $\mathrm{disc}(K)$ is
	an integer, and since $\ind(\alpha)$ is an integer for every $\alpha$, we conclude that 
	$P=Q/\sqrt{\mathrm{disc}(K)}$ is a polynomial in $x_2,\ldots,x_n$ with coefficients in some degree $2$ or $4$ extension
	of $\Q$ that takes only integer values.  Therefore, $P\,\in\,\Z[x_1,\ldots,x_n]$.

	\item We now compute such a polynomial for $K=\Q(175^{1/3})$.  We write 
	\begin{eqnarray*}
	    \beta\ =\ \alpha-x_1\ =\ Xa+Ya^2/5,
	\end{eqnarray*}
	for any $\alpha\,\in\,R$ with $a=175^{1/3}$.  We readily compute
	\begin{eqnarray*}
	    \beta^2\ =\ X^2a^2+7 y^2 a+70XY.
	\end{eqnarray*}
	The two nontrivial imbeddings of $K$ into $\C$ are given by $\sigma_2(a)=\omega a$ and $\sigma_3(a)=\omega^2 a$,
	where $\omega$ is a cube root of unity.  Therefore, we must calculate the determinant
	\begin{eqnarray*}
	\begin{vmatrix}
	1 & Xa+Ya^2/5 & X^2a^2+7 y^2 a+70XY\\
	1 & X\omega a+Y\omega^2a^2/5 & X^2\omega^2a^2+7 y^2\omega a+70XY\\
	1 & X\omega^2 a+Y\omega a^2/5 & X^2\omega a^2+7 y^2\omega^2 a+70XY\\
	\end{vmatrix}
	\end{eqnarray*}
	This is somewhat tedious, but we find that the determinant is equal to
	\begin{eqnarray*}
	    -105\sqrt{-3}(5X^3-7Y^3).
	\end{eqnarray*}
	It remains to divide this polynomial by $\sqrt{\mathrm{disc}(K)}.$  Using the integral basis found above,
	we readily compute
	\begin{eqnarray*}
	\sqrt{\mathrm{disc}(K)}&=&
	\begin{vmatrix}
	1 & a &  a^2/5\\
	1 & \omega a &  \omega^2 a^2/5\\
	1 & \omega^2 a &  \omega a^2/5
	\end{vmatrix}\\
	&=&-105\sqrt{-3}.
	\end{eqnarray*}
	Therefore, we have
	\begin{eqnarray*}
	    P(X,Y)\ =\ 5 X^3-7 Y^3.
	\end{eqnarray*}
	From this it follows that $\ind(K)=1$ since $(5,7)=1$.  If $R$ were primitive, we could find
	some $X,Y\,\in\,\Z$ such that $5X^3-7Y^3=1$.  We view this equation modulo $7$ so see that we have
	a solution to $X^3\equiv 3 \mod 7.$  The cubes modulo $7$ are $1,-1,$, so that this is impossible
	and $R$ is not primitive.
	
	  

\end{enumerate}

\end{document}