\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,kgm}

\newcommand{\kgmcomment}[1]{}
\renewcommand{\gcd}{\mathrm{gcd}}

\begin{document}
\headers{Math373}{Homework 3}{Due Fri, Jan. 31, 2014}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

%\newcommand{\seq}[1]{\left\langle #1\right\rangle}

\makeatletter
\def\@oddfoot{}
\makeatother

\noindent
\textbf{Directions:} Solve the following problems.  All written work must be your own.  See the course syllabus for detailed rules.

\begin{enumerate}

\item {} Modular Arithmetic Tables
\begin{enumerate}
	\item Make addition and multiplication tables for $\Z_3$.
	\item Make addition and multiplication tables for $\Z_6$.
\end{enumerate}

\item Compute the following.  Your answer should be an integer in the set $\{0, 1, \ldots, m-1\}$, where $m$ is the modulus in the given problem.
\begin{enumerate}
	\item $73 - 6173 \pmod{22}$
	\item $342\cdot 825 \pmod{17}$
\end{enumerate}

\item Use the extended Euclidean algorithm to find a multiplicative inverse of $50$ modulo $2891$ in the range $\{0,1,\ldots, 2890\}$.


\item Make a multiplication table for the unit group $\Z_9^*$.

\item Use the fast power algorithm to compute $2^{300} \pmod{1000}$.  Show intermediate powers of $2$.

\item Using a computer/calculator only for basic arithmetic operations (addition, subtraction, multiplication, and division), solve for $x$ in $523x \equiv 211 \pmod{591}$.  \emph{Show your work}.

\item Let $a$, $b$, $g$, and $m$ be integers such that $g^a\equiv 1\pmod{m}$ and $g^b\equiv 1\pmod{m}$.  Prove that $g^{\gcd(a,b)}\equiv 1\pmod{m}$.

\item {} \textbf{[Challenge]} Let $a$ and $b$ be integers, not both zero.  The \emph{least common multiple} of $a$ and $b$, denoted $\lcm(a,b)$, is the smallest positive integer that is a multiple of both $a$ and $b$.  For example, $\lcm(10,4) = 20$.  Prove that $\lcm(a,b) = (ab)/\gcd(a,b)$.  \emph{Hint:} find (and prove) a relationship between the positive common divisors of $a$ and $b$ and the positive common multiples of $a$ and $b$.

\end{enumerate}
\end{document}
