\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 4}
\date{Due date: Sept 25, 2015}
\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 Find the least nonnegative remainder of $30!\pmod{899}$. 

\item let $r_1, r_2, \ldots, r_{\phi(m)}$ be a reduced system of residues modulo $m=2^l$, where $l\ge 3$, then $$\prod_{i} r_i\equiv 1\pmod{2^l}.$$

\item let $r_1, r_2, \ldots, r_{\phi(m)}$ be a reduced system of residues modulo $m=2p^l$, where $l\ge 1$ and $p$ is an odd prime, then $\prod_{i} r_i\equiv -1\pmod{2p^l}$.


\item Show that if $n$ is an odd positive integer or if $n$ is a positive divisible by $4$, then $$1^3+2^3+\ldots+(n-1)^3\equiv 0 \pmod{n}.$$ 



\item Let $(m,n)=1$.  Show that $m^{\phi(n)}+n^{\phi(m)}\equiv 1\pmod{mn}$. 

\item Find the last two digits of $a_{1001}$ if $a_1=7, a_n=7^{a_{n-1}}$. 

\item (Extra credit problem) Let $m\ge 3$, $r_1, r_2, \ldots, r_m$ and $r_1', r_2', \ldots, r_m'$ are two complete system of residues modulo $m$.  Show that $r_1r_1', r_2r_2', \ldots, r_mr_m'$ is a not a complete system of residues modulo $m$.  





\end{enumerate}

\end{document}
