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

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

\begin{document}
\headers{Math373}{Homework 4}{Due Wed, Feb. 8, 2023}

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

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

\makeatletter
\def\@oddfoot{}
\makeatother


\newcommand{\ord}{\mathrm{ord}}
%\newcommand{\F}{\mathbb{F}}

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

\begin{enumerate}

\item Make a multiplication table for the unit group $\Z_9^*$.  What is $\phi(9)$?

\item Modular exponentiation in $\Z_7$.
\begin{enumerate}
	\item Fill in the table so that row $a$ and column $k$ contains $a^k$, where $a^k \in \Z_7$.
	\begin{center}
	{
	\def\arraystretch{1.5}
	\begin{tabular}{c|*{9}{|p{0.5cm}}}
		$a^k$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & $\cdots$\\
		\hline
		\hline
		0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
		\hline
		1 & & & & & & & &\\
		\hline
		2 & & & & & & & &\\
		\hline
		3 & & & & & & & &\\
		\hline
		4 & & & & & & & &\\
		\hline
		5 & & & & & & & &\\
		\hline
		6 & & & & & & & &\\
	\end{tabular}
	}
	\end{center}

	\item The \emph{order} of an element $a\in \Z_m^*$ is the smallest positive integer $k$ such that $a^k = 1$ in $\Z_m$.  Find the unit group $\Z_7^*$, and for each $a\in \Z_7^*$, find the order of $a$.

	\item An element $a\in \Z_7$ is a \emph{primitive root} if its order equals $|\Z_7^*|$; that is, if the sequence $a^0, a^1, a^2, \ldots$ contains each element in $\Z_7^*$.  Use the table to find all primitive roots in $\Z_7^*$.  Verify that the number of primitive roots equals $\phi(6)$.
\end{enumerate}

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

\item Common divisors divide the gcd.
\begin{enumerate}
	\item Let $a$ and $b$ be integers and let $d=\gcd(a,b)$.  Prove that if $\ell$ is a common divisor of $a$ and $b$, then $\ell \mid \gcd(a,b)$.
	\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}$.
\end{enumerate}

\end{enumerate}
\end{document}
