\documentclass[12pt]{article}
\usepackage{fullpage}
\usepackage{amsfonts}
\usepackage{amsmath, amsthm, amssymb}
\usepackage{enumitem, url}
%\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}
\newcommand{\lra}{\leftrightarrow}

\DeclareMathOperator{\GCD}{GCD}
\newcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}
\newcommand{\Legendre}[2]{\ds \genfrac{(}{)}{}{}{#1}{#2}}

\newcommand{\sol}{\textbf{Solution: }}



\begin{document}

\thispagestyle{empty}

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


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

\begin{enumerate}
\item The following question arose while students were working on
  homework 6.  Suppose that $a$ is a primitive root modulo the odd
  prime $p$, but not a primitive root modulo $p^2$.  Show that $a$ is
  not a primitive root modulo $p^e$ for all $e \ge 2$. Explain how the
  following hint is relevant and then prove it.  Hint: Show by
  induction that $a^{(p-1)p^{k-1}}\equiv 1\pmod {p^{k+1}}$ for all
  $k \ge 1$.

\item Suppose that the positive integer $n$ has a primitive root, and
  $\gcd(a,n) = 1$.  Show that the congruence
  \[x^m \equiv a \pmod n\] is solvable iff
  $a^{\phi(n)/d} \equiv 1 \pmod n$ where $d = \gcd(m,\phi(n))$.  If it
  is solvable, show that there are exactly $d$ solutions modulo $n$.

\item Analogous to problem 1 on Homework 4, it is straightforward to
  prove the following result (you may assume its validity): Let $a$ be
  an integer, and $p$ be an odd prime with $p \nmid a$.  Then
  $x^2 \equiv a \pmod p$ is solvable if and only if
  $x^2 \equiv a \pmod {p^e}$ for all $e \ge 1$.  Moreover, all these
  congruences have the same number of solutions.

  \begin{enumerate}
  \item Use Gauss's lemma to compute $\Legendre{5}{19}$.
  \item Determine whether the following congruence is solvable, and if
    so determine the number of solutions
    \[x^2 \equiv 5 \pmod {19^7\cdot 11^3}
    \]
  \end{enumerate}

    
\item The following exercise will help you find all square roots of
  $-3$ in $U_{7^3}$.  It is certainly possible to find a solution
  modulo 7 and then ``lift'' it to one modulo $7^3$, but this problem
  outlines an alternate approach.
  \begin{enumerate}
  \item Show that 3 is a primitive root modulo $7^3$.
  \item Find the index of $-3$ with respect to the primitive root 3.
  \item Use that information to determine all the solutions to
    $x^2 \equiv -3 \pmod{7^3}$.
  \end{enumerate}


\item What is the analog of Corollary 7.10 for $\Legendre{-2}{p}$?
  That is, determine congruence conditions to characterize when
  $-2 \in Q_p$ for an odd prime $p$.  Make sure you involve
  $\Legendre{2}{p}$ as part of your answer.
\end{enumerate}

\end{document}


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