\documentclass{article}
\usepackage{amsmath, amssymb,verbatim, amsthm, graphicx}

%exercise environment
\newcounter{exercise}
\setcounter{exercise}{0}
\newenvironment{exercise}{\addtocounter{exercise}{1} \noindent{\bf{Exercise \theexercise.}}}{\vspace{.5cm}}

\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\C}{\mathbb{C}}

\textwidth 6.5in
\textheight 9in
\oddsidemargin 0in
\evensidemargin 0in
\headsep -0.5in

\setlength{\parskip}{0.25cm}

\pagenumbering{gobble}

\begin{document}

\begin{center}
\includegraphics[width=0.5in]{../ltr-logo.jpg}
\end{center}

\noindent{\Large{\textsc{Number Theory \hfill Assignment 11.1  \\ Fall 2023 \hfill Due November 15}}}

\large

\vspace{1cm}

\begin{exercise}
Let $d,n \in \N$ with $d|n$.  In class we showed that the rule $a+n\Z \mapsto a+d \Z$ yields a well-defined function
\[
R:(\Z/n\Z)^{\times} \to (\Z/d\Z)^{\times}.
\]
Show that $R$ is surjective as follows.

\begin{itemize}

\item[\bf a.]  Let $a , k \in \Z$ with $(a,d)=1$.  Show that if a prime $p$ divides $(a+kd, n)$, then $p|n$ and $p \nmid d$.

\item[\bf b.]  Let $p_1, p_2, \ldots, p_r$ be the primes dividing $n$ that don't divide $d$.  Use the CRT to show that there is a $k \in \Z$ so that $dk \equiv 1-a \pmod{p_i}$ for all $i$.

\item[\bf c.]  With $k \in \Z$ chosen as above, show that $(a+kd,n) = 1$.  [{\em Suggestion:}  Use parts {\bf a} and {\bf b} to show that $(a+kd,n)$ has no prime divisors.]

\item[\bf d.]  Parts {\bf a} - {\bf c} show that for any $a \in \Z$ with $(a,d)=1$, there exists $k \in \Z$ so that $(a+kd,n) = 1$.  Use this to conclude that $R$ is surjective.

\end{itemize}

\end{exercise}

\begin{exercise}
Textbook exercise 7.2.1.
\end{exercise}

\begin{exercise}
Textbook exercise 7.2.14.
\end{exercise}

\begin{exercise}
Textbook exercise 7.3.1c.
\end{exercise}

\begin{exercise}
Textbook exercise 7.3.4.
\end{exercise}

\begin{exercise}
Textbook exercise 7.3.5.
\end{exercise}

\begin{exercise}
Textbook exercise 7.3.9.
\end{exercise}


\vspace{1cm}










\end{document}
 