\documentclass[12pt]{amsart}
\setlength{\textheight}{9.75truein}
\setlength{\textwidth}{6.5truein}
\setlength{\evensidemargin}{0truein}
\setlength{\oddsidemargin}{0truein}
\setlength{\topmargin}{-.75truein}
\parskip\baselineskip
\parindent0in
\usepackage{amssymb,latexsym,amscd}
\begin{document}
\begin{center}{\bf M445/845, Homework 4, due Monday, November 11, 2013}\end{center}
\noindent Instructions: Do any three problems.
\begin{itemize}
\item[(1)] Consider the nonzero rationals, ${\bf Q}^*$. This is a group under multiplication.
\vskip\baselineskip
\begin{itemize}
\item[(a)] If $r\in{\bf Q}^*$, show that there is a unique expression of $r$
as $\frac{m}{n}$, such that $m>0$ and $n\neq0$ are integers with $(m,|n|)=1$.
%as a product of powers of distinct primes with nonzero (possibly negative) exponents.
\vskip\baselineskip
\item[(b)] Show that ${\bf Q}^*$ is not a cyclic group.
(I.e., show that there is no nonzero rational $r$ such that
every nonzero rational $c$ is a power of $r$.)
\vskip\baselineskip
\end{itemize}
\item[(2)] Let $a,b,c,d$ be positive integers and let $s$ be any integer.
Prove that $x=s$ is a solution to $adx\equiv bd\mod cd$
if and only if $x=s$ is a solution to $ax\equiv b\mod c$.
\vskip\baselineskip
\item[(3)] Use techniques developed in class to
find all positive integer solutions $x\leq m$ for $m=519223=71^2*103$
to the equation $x^2\equiv 480777 \mod m$.
\vskip\baselineskip
\item[(4)] Show how to use quadratic reciprocity in conjunction with
techniques developed in class to determine whether
$x^2\equiv 85\mod23319936929$ has a solution.
(Note: $p=23319936929$ is known to be prime.)
\vskip\baselineskip
\item[(5)] Let $p_n$ denote the $n$th prime, so, for example, $p_1=2$ and $p_5=11$.
\vskip\baselineskip
\begin{itemize}
\item[(a)] Use induction to show that $p_n\leq 2^n$. (You may assume without proof
a theorem known as Bertrand's postulate, viz.,
that for any positive integer $n$, there is a prime $p$ with $n