\documentstyle[12pt]{report}
\newcommand{\sk}{\vskip 0.2in}
\begin{document}
\begin{center}
{\Huge 189-346B/377B: Number Theory} \\ \sk
{\Huge Midterm Exam} \\ \sk
{\Large Friday, February 11}
\end{center}
\def\Z{{\bf Z}}
\def\C{{\bf C}}
\def\R{{\bf R}}
\def\Q{{\bf Q}}
\sk\sk
\noindent
1. Show that the $\gcd$ of two integers $a$ and $b$ is a linear combination
of $a$ and $b$, i.e., that
if $d = \gcd(a,b)$ then there exist integers $m$ and $n$ for which
$$ d = ma + nb.$$
\sk
\noindent
2. State two number-theoretic problems that are believed to be computationally
intractable, and for each problem, name a cryptosystem that exploits
this presumed intractability.
(This question is just to test your knowledge of the salient
points in the material covered
in class. You do not need to provide descriptions of the cryptosystems in question,
only their names. If you can't remember the names, then a brief description
will do...)
\sk\sk
\noindent
3. Compute
$$ 7^{403275023750023740523040602} \pmod{101}.$$
You should express your answer as an integer between $0$ and $100$.
\sk\sk
\noindent
4. A {\em Sophie Germain prime} is a prime $p$ of the form
$1+2q$ where $q$ is also a prime.
Assume that $p$ is such a prime.
Show that
$a\in(\Z/p\Z)^\times$
is a primitive root modulo $p$ if and only if
$$ a \ne \pm 1, \quad a\ne b^2 \pmod{p}, \mbox{ for any } b\in
(\Z/p\Z)^\times. $$
Find the smallest primitive root modulo $23$.
\sk\sk \noindent
5. Solve the equation
$$x^2+1=0 \pmod{ 101^2 }.$$
\end{document}