\documentclass[12pt]{article}
\title{Math 187 Test IV, Spring 2012}
\author{Dr. Holmes}
\begin{document}
\maketitle
The exam will begin at 140 pm and end at 235 pm. You may use your writing instrument, your non-graphing scientific calculator,
and your test paper. If you require scratch paper I will have some.
\newpage
\begin{enumerate}
\item Find a solution to the system of equations
$$x \equiv 6 \,{\tt mod}\, 13$$
$$x \equiv 9 \,{\tt mod}\, 19$$
Find another solution (hint: what is the appropriate modulus?)
\newpage
\newpage
\item Necklace counting
\begin{enumerate}
\item A closed necklace with no clasp has 11 beads of 4 colors. How many such necklaces are possible?
\vspace{1 in}
\item (extra credit) A closed necklace has 15 beads of 3 colors. How many such necklaces are possible?
\end{enumerate}
\newpage
\item Modular exponentiation
\begin{enumerate}
\item Compute $7^{435627650}\, {\tt mod}\,13$ Hint: Fermat's little theorem makes this a snap.
\vspace{2 in}
\item Compute $11^{1024} \,{\tt mod} \, 100$ (a different set of tricks makes this straightforward)
\end{enumerate}
\newpage
\item Degree sequences
\begin{enumerate}
\item For each of the two following degree sequences, either draw a graph with that degree sequence or give a brief explanation as to why there cannot be one.
\begin{enumerate}
\item $4,4,3,2,2,1$
\vspace{1.5 in}
\item $4,3,3,2,2,1$
\vspace{1.5 in}
\end{enumerate}
\item Show me two nonisomorphic graphs with the degree sequence $2,2,2,2,2,2$
\end{enumerate}
\newpage
\item One of the two pictured graphs has an Eulerian trail. One doesn't. Explain why the one that doesn't, doesn't,
and give an Eulerian trail for the other in the form of a list of vertices visited in order.
\newpage
\item Prove using the Pigeonhole Principle that if I choose 10 points in a $3 \times 3$ square, two of them will be at distance $\leq \sqrt 2$ from each other. Be sure to state the counting facts you use.
\newpage
\item RSA problem
Your RSA key $N=pq$ is 55 and your encryption exponent $r$ is 3.
\begin{enumerate}
\item Find your decryption exponent (Hint: it is the reciprocal of 3 in a certain modulus). Show all work.
\vspace{2 in}
\item Decode the message 17. Show all work.
\end{enumerate}
\newpage
\item Factoring magic
\begin{enumerate}
\item Prove this theorem: if $p$ is a prime, and $p | ab$, then either $p|a$ or $p|b$.
Your proof should not mention prime factorizations: it is the basis for the proof of the uniqueness of prime factorizations! It should use the basic theorem about greatest common divisors and the definition of divisibility. (another part on the next page)
\newpage
\item Use the theorem proved in part a to prove this theorem: if $3|x$ and $7|x$ then $21|x$.
I want you to use the theorem of the first part -- nothing about prime factorizations. Further, you should explicitly use the definition of divisibility: this will help you see how to use the theorem of part a!
\end{enumerate}
\end{enumerate}
\end{document}