\documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{ulem} % for strikethrough \sout{...} command
\usepackage{color}
\usepackage{hyperref}

% for the smiley face
\usepackage{wasysym}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.25in}
\setlength{\evensidemargin}{-0.25in}
\setlength{\topmargin}{-0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.75in}
\setlength{\textwidth}{7in}

\newcommand{\bdot}{\, {\scriptstyle{\bullet}} \,}
\newcommand{\B}[1]{{\bf {#1}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}

\newcommand{\myspace}{\parbox[c][0.25in]{0.25in}{\hfill}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}
\newcommand{\force}{{\noindent $\mbox{\;}$}}

\newcommand{\diagquotient}[2]{\displaystyle{{#1 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} {\; \atop #2}}}

\newcommand{\bproof}{\noindent {\bf Proof:} \quad}
\newcommand{\eproof}{$\blacksquare$}

\begin{document}

\pagestyle{empty}

\noindent
\parbox{2.25in}{\bf Math 2110}
\hfill {\Large \bf Homework \#11} \hfill
\parbox{2.25in}{\bf \hfill Due: Fri., Nov. $20^\mathrm{th}$, 2020}

\vspace{0.1in}

%\noindent {\large\bf Name:} \underline{\Large\quad My Name Goes Here \quad} \hfill 

\force \hfill Handwritten solutions are fine. \smiley  % uses wasysym package. :)
\hfill \force

\vspace{0.2in}

\begin{description}
\item[\#1 Extended Euclidean Exhaustion:] For each of the following pairs of numbers, $a,b \in \mathbb{Z}$, compute their greatest common divisor, $d=\mathrm{gcd}(a,b)$, using the Euclidean algorithm. Then use your work to write the gcd as an integral linear combination of your pair of numbers (i.e., find $x,y \in\mathbb{Z}$ such that $ax+by=d$).

{\it Note:} Obviously my Sage Interact found at\dots

\vspace{-0.125in}

\begin{center}
\url{https://billcookmath.com/sage/algebra}
\end{center}

\vspace{-0.05in}

will compute the end result. But I want you to do this by hand and {\it show your work}! [Then go use the interact to check your answers.]

\begin{enumerate}[(a)]
   \item $a=555$ and $b=95$.
   \item $a=9999$ and $b=122$.
\end{enumerate}

\item[\#2 What does this get me?] Suppose that $a,b,x,y \in \mathbb{Z}$ and we have $ax+by=10$. What can we say about $\mathrm{gcd}(a,b)$? What must be true if $ax+by=1$?

\item[\#3 Modulo Inverses] Fix some positive integer $n$.

It turns out that the set of equivalence classes mod $n$, $\mathbb{Z}_n = \{ [0], [1],\dots, [n-1]\}$, has the structure of something called a ``commutative ring with $1$''. This means that we can add and multiply elements of $\mathbb{Z}_n$ much like we add and multiply integers. However, some things are weird.
In particular, multiplicative inverses and cancellation properties don't quite work as one might initially expect.

\begin{enumerate}[(a)]
\item We say $[a]$ is a {\it unit} of $\mathbb{Z}_n$ if there is some $[b] \in \mathbb{Z}_n$ such that $[a][b]=[1]$. 

Explain why $[a]$ is a unit if and only if $\mathrm{gcd}(a,n)=1$.

\item Let $\mathbb{Z}_n^\times = \{ [k] \in \mathbb{Z}_n \;|\; \mathrm{gcd}(k,n)=1\}$ (this is the set of units). 

Find the elements of $\mathbb{Z}_7^\times$ along with their inverses. Do the same for $\mathbb{Z}_8^\times$. 

For example, $\mathbb{Z}_6 = \{[0],[1],\dots,[5]\}$ but $\mathbb{Z}_6^\times = \{[1],[5] \}$. Notice that $[1][1]=[1\cdot 1]=[1]$ and $[5][5]=[5\cdot 5]=[25]=[1]$
 (working mod 6). Thus $[1]^{-1}=[1]$ and $[5]^{-1}=[5]$.
 
 \item Show that cancellation does not work in $\mathbb{Z}_6$. Specifically, find some $[a],[b],[c] \in \mathbb{Z}_6$ such that $[a] \not= [0]$ and $[a][b]=[a][c]$ but $[b] \not= [c]$. 
 
 {\it Note:} This doesn't happen in $\mathbb{Z}$. If $a,b,c \in \mathbb{Z}$ and $a\not=0$. Then $ab=ac$ implies $b=c$. It is also interesting to note that this failure of cancellation can only happen because $6$ is composite. Cancellation laws do hold in $\mathbb{Z}_p$ for any prime $p$. 
 
\end{enumerate}

\item[\#4 Calculatin' Modulo] Compute $5^{-2}\cdot(4-10)\cdot 13^{9999}+11$  (mod 14).  Give a ``good manners'' answer (i.e., simplify so your answer is between 0 and 13).

Please keep in mind that $5^{-2}$ means $(5^{-1})^2$ where $5^{-1}$ is the multiplicative inverse of $5$ modulo 14. Let me emphasize that $5^{-1}$ is not the same thing as the fraction $1/5$. 


\end{description}


\end{document}