\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{enumitem}
%\pagestyle{headings}

\usepackage{mathtools}

\newcommand{\0}{\mathbf 0}
\newcommand{\C}{{\mathbb C}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\diag}{\textrm{diag}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\newcommand{\normal}{\trianglelefteq}
\newcommand{\bmid}{\,\Big|\,}
\newcommand{\ds}{\displaystyle}

\DeclareMathOperator{\GCD}{GCD}

\begin{document}

\thispagestyle{empty}

\begin{flushright}
  Your Name Goes Here
\end{flushright}


\begin{center}
  \textbf{Math 25}\\ Homework 4
\end{center}

\begin{enumerate}
\item Let $p$ be an odd prime, and $a$ an integer not divisible by
  $p$.  Show that $x^2 \equiv a\pmod p$ is solvable if and only if
  $x^2 \equiv a \pmod{p^2}$ is solvable.

  % \item Determine how many solutions there are to the congruence
  %   $x^2 \equiv 124\pmod{225}$, and find one of them using methods
  %   from the course (not exhaustive search).

\item Let $n\ge2$ and $a$ be integers, with $\gcd(a,n) =1$. Let
  \[S = \{ h \in \Z_+ \mid a^h \equiv 1 \pmod n\}.\] By Euler's
  theorem, we know that $S \not= \emptyset$.  Denote by $e_n(a)$ the
  smallest element of $S$, that is the smallest positive integer $h$
  so that $a^h \equiv 1 \pmod n$.  Show that $e_n(a) \mid \phi(n)$,
  where $\phi$ is Euler's function.


\item Show that for all integers $a$ with $\gcd(a,10) = 1$, we have
  that $a^{20} \equiv 1\pmod {100}$.


\item Show that 25 is a strong pseudoprime to the base 7.

\item Show that 1387 is a pseudoprime to the base 2, but not a strong
  pseudoprime to the base 2.

\end{enumerate}

\end{document}


%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
