\documentclass[10pt]{article} % 
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{psfrag}
\usepackage{amsmath,amssymb}
\usepackage{enumerate}

\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\newcommand{\cP}{\mathcal{P}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}

\title{Math 412  Homework 8}
\date{Due date: Oct 30, 2014}
\author{your name}


\begin{document} 
\maketitle

Solve the following problems. Please remember to use complete sentences and good grammar. Four points each. 



\begin{enumerate}
\item Show that there are the same number of primitive roots modulo $2p^t$ as there are modulo $p^t$, where $p$ is an odd prime and $t$ is a positive integer. 

\item Show that the integer $m$ has a primitive root if and only if the only solutions of the congruence $x^2\equiv 1\pmod{m}$ are $x\equiv \pm 1\pmod{m}$. 

\item Let $p$ be an odd prime.  
\begin{enumerate}
\item Show that if $p$ is an odd prime an $r$ is a primitive roots of $p$, then $ind_r(p-1)=(p-1)/2$. 
\item Show that the congruence $x^4\equiv -1\pmod{p}$ has a solution if and only if $p$ is of the form $8k+1$.  
\end{enumerate}

\item Find all solutions of the following congruence:  $13^x\equiv 5\pmod{23}$. 

\item Let $p$ be an odd prime and $p\not| a$.  Show that there exist integers $u, v$ with $(u, v)=1$ so that $u^2+av^2\equiv 0\pmod{p}$ if and only if $-a$ is a quadratic residue modulo $p$. 

\item Show that if $p$ is a prime and $p=8n+1$, and $r$ is a primitive root modulo $p$, then the solutions of $x^2\equiv \pm2\pmod{p}$ are given by $x\equiv \pm(r^{7n}\pm r^n)\pmod{p}$, where $\pm$ sign in the first congruence corresponds to the $\pm$ sign inside the parentheses in the second congruence. 


\item (Bonus) A {\em cyclic number} is an $(n-1)$-digit integer that, when multiplied by $1,2,3,\ldots, n-1$, produces the same digits in a different order. For example, $142857$ is a cyclic number with $6$ digits.  Prove that if $10$ is a primitive root modulo $p$, where $p$ is a prime, then $(10^{p-1}-1)/p$ is a cyclic number. 


\end{enumerate}

\end{document}
