\documentclass[12pt]{article}
\title{Modular Exponentiation and Related Topics}
\author{Dr Holmes}
\begin{document}
\maketitle
This is due Friday after break.
\begin{enumerate}
\item Compute $13^{4096}\,{\tt mod}\,100$. Notice that 4096 is a power of two; this makes it very straightforward.
\item Compute $5^{1000}\,{\tt mod}\,41$. This is also to be done by repeated squaring, but with the appropriate modification when odd exponents appear. Do not use Fermat's Little Theorem (and of course show all work).
\item Use Fermat's Little Theorem ($a^{p-1}\equiv 1\,{\tt mod} p$ for $p$ prime, $p \not| a$) to compute $5^{1000}\,{\tt mod}\,41$. Why can't you use Fermat's Little Theorem to simplify the first problem?
\item There is a number $k$ such that $10^{m {\tt mod} k} = 10^m$ in mod 10 arithmetic, for any $m$. Find it by experiment (you don't have to do a lot of computations: compute the first few powers of each of the numbers 0 through 9 in mod 10 arithmetic and see how long it takes for the powers to repeat). There is another way you could find it as well.
\item Use the result that if $N=pq$, $p,q$ prime, that $a^m = a^{m {\tt mod} (p-1)(q-1)}$ for any $a$ and $m$ (which we proved in class) to simplify the computation of $3^500$ in mod 21 arithmetic. You will not need to do repeated squaring, or not very much. You do know how to factor 21; that is where to start.
\item Write out the proof that if $p|ab$ then $p|a$ or $p|b$, when $p$ is prime. Read it in the book or my notes, take a break for an hour, then write it out without looking at your source (study suggestion). Give a counterexample to show that the hypothesis that $p$ is prime is necessary.
\item How many different closed necklaces of 13 red, green, blue, and yellow beads can I make? (This recalls the counting argument I used to prove Fermat's Little Theorem). Hint: there are $4^{13}$ open chains. How many open chains correspond to each necklace (the answer is not the same in all cases, but because 13 is prime there are only two cases)?
\end{enumerate}
\end{document}