\documentclass{article}[11 pts] 

\begin{document}
\centerline{\bf THEORY OF NUMBERS, Math 115 A}
\centerline{\bf Homework 6 Due Wednesday November 15 2002}
\vskip 5pt

\begin{enumerate}

\item (6.1 6) What is the remainder when 
$7\cdot 8 \cdot 9 \cdot 15 \cdot 16 \cdot 17 \cdot 23 \cdot 24 \cdot 25 \cdot 43$ is divided by 11? 

\item (6.1 12) Using Fermat's little theorem, find the least positive residue
of $2^{1000000}$ modulo 17.

\item (6.1 34) Show that if $p$ is a prime and $0 <k< p$, then $(p-k)!(k-1)! \equiv (-1)^k$ modulo $p$.

\item (6.1 40,41) Using the fact that $p$ divides the binomial coefficient
${p \choose k}$ when $k$ is less than $p$ show that if $a,b$ are integers
then $(a+b)^p \equiv a^p+ b^p$. Use this to prove Fermat's little theorem.

\item  (6.2 2) Show that 45 is a pseudoprime to the bases 17 and 19.

\item (6.2 20) Show that if $n$ is a Carmichael number then $n$ is square free.

\item (6.2 1 computer exploration) Determine for which positive integers 
$n$, $ n \leq 100$, the integer $n 2^n-1$ is prime.

\item (6.3 6) Find the last digit of the decimal expansion of $7^{999,999}$.


\item (6.3 10) Show that $a^{\phi (b)} + b^{\phi (a)} \equiv 1 \ (mod \ ab)$
if a,b are relatively prime positive integers.


\item (6.3 2 computational exploration) Find $\phi(n)$ for all integers less
than 1000. What conjecture can you make about the values of $\phi(n)$. 

\end{enumerate}

\end{document}





