\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 3}
\date{Due date: Sept 17, 2010}
\author{your name}


\begin{document} 
\maketitle

Solve the following problems. Please remember to use complete sentences
and good grammar. Each problem is 4 points.



\begin{enumerate}
\item Find the prime factorization of $32!$.  How many zeros are at the end of $32!$?

\item  Find the last two digits of $9^{9^9}$. 


\item Find the inverse of $3$ module $7$, and find all integers $n$ so that $3n\equiv 5 \pmod{7}$. 

\item Show that $x^2-2y^2=77$ has no integer solution.  

\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_1, m_2, \ldots, m_k$ be pairwise relatively prime  positive integers. Let $M=m_1m_2\ldots m_k$ and $M_j=M/m_j$ for $j=1, 2, \ldots, k$.  Show that $M_1a_1+M_2a_2+\ldots+M_ka_k$ runs through a complete system of residues modulo $M$ when $a_1, a_2, \ldots, a_k$ run through complete system of residues modulo $m_1, m_2, \ldots, m_k$, respectively.  (hint:  for each $i$, there are $m_i$ choices of $a_i$'s.  So there are exactly $m_1m_2m_3\ldots m_k$ integers of the form $M_1a_1+M_2a_2+\ldots+M_ka_k$.  We need to show that all of those integers are different modulo $M$.)


\item (Extra credit problem) show that $\frac{(2n)!}{(n!)^2}$ is even.  

\end{enumerate}

\end{document}
