\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. 9, 2022}

%\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 {}[JJJ 1.28] Compute the following values of the order function.
\begin{enumerate}
	\item $\ord_2 (2816)$
	\item $\ord_7 (2222574487)$
	\item $\ord_p (46375)$ for each prime $p\in \{3,5,7,11\}$.
\end{enumerate}

\item {} [JJJ 1.29] Let $p$ be a prime number, and let $a$ and $b$ be positive integers.  Prove the following.
\begin{enumerate}
	\item $\ord_p(ab) = \ord_p(a) + \ord_p(b)$
	\item $\ord_p(a+b) \ge \min\{\ord_p(a), \ord_p(b)\}$
	\item If $\ord_p(a) \ne \ord_p(b)$, then $\ord_p(a+b) = \min\{\ord_p(a), \ord_p(b)\}$.
\end{enumerate}

\item Modular exponentiation in $\F_7$.
\begin{enumerate}
	\item Fill in the table so that row $a$ and column $k$ contains $a^k$, where $a^k \in \F_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 For each non-zero element $a$, find the order of $a$ in $\F_7^*$.

	\item Use the table to find all primitive roots in $\F_7$.  Verify that the number of primitive roots equals $\phi(6)$.
\end{enumerate}

\item Use Fermat's Little Theorem and the fast power algorithm to compute the multiplicative inverse of $68$ in $\F_{101}$.

\end{enumerate}
\end{document}
