\documentclass{article}
\voffset=-0.05\textheight
\textheight=1.1\textheight
\hoffset=-0.05\textwidth
\textwidth=1.1\textwidth
\title{Math 480 (Spring 2007): Homework 2}
\author{\bf Due: Monday, April 9}
\date{}
\include{macros}

\begin{document}
\maketitle 

\noindent{\bf There are 8 problems.} Each problem is worth 6 points
and parts of multipart problems are worth equal amounts.  (Note: 6 points
each, instead of 5 this time.)\\
{\bf Office Hours.}
My official office hours are on Thursdays 4--6pm in Padelford C423.


\begin{enumerate}

\item
\begin{enumerate}
\item Prove that for any positive
integer $n$, the set $(\Z/n\Z)^*$ under multiplication
modulo~$n$ is a group.  
\item Prove that for any positive
integer $n$, the set $\Z/n\Z$ under addition
and multiplication modulo~$n$ is a ring.
\end{enumerate}

%\item
%Find two distinct pairs of integers $x,\, y\in\Z$
%such that $221x + 510y = 17$.  (You may use
%  any method (even a computer) 
%  to answer this question, as long as you
%  explain what you do.)

% Burton, page 88
\item Prove that for every positive integer $n$ the integer $5^{2n} +
  3\cdot 2^{5n-2}$ is divisible by $7$.

\item\label{ex:polrepconj} Let $f(x)=x^3+a \in\Z[x]$ be a cubic
  polynomial with integer coefficients, e.g., $f(x)=x^3+1$. 
\begin{enumerate}
\item Formulate
  a conjecture about when the set $\{ f(n) : n\in \Z \text{ and $f(n)$
    is prime}\}$ is infinite.
\item  Give numerical evidence that supports
  your conjecture.
\end{enumerate}

%Burton, page 88
\item Prove the following statements:
\begin{enumerate}
\item If $a$ is an odd integer, then $a^2\con 1\pmod{8}$.
\item For any integer $a$, we have $a^3 \con 0,1,\text{ or }6\pmod{7}$.
\item For any integer $a$, we have $a^4 \con 0\text{ or }1\pmod{5}$. 
\end{enumerate}

\item\label{ex:divrules} 
  Find rules for divisibility of an integer
  by~$5$,~$9$, and~$11$, and prove each of these rules using
  arithmetic modulo a suitable~$n$.

\item\label{ex:ordmod} What is the multiplicative order of~$3$ modulo
  $17$?  (You may use any method (even a computer) to answer this
  question, as long as you explain what you do.)

\item A basket has $n$ eggs in it.  One egg remains when the eggs
are removed from the basket 2, 3, 4, 5, or 6 at a time.  No egg
remains if they are removed 7 at a time.  Find the smallest number $n$
of eggs that could be in the basket. 

%\item\label{ex:invmod} Find an integer~$x$ such that $38x \con
%  1\pmod{101}$ and explain the algorithm that you used.  (You may use
%  any method (even a computer) to answer this question, as long as you
%  explain what you do.)

\item 
\begin{enumerate}
\item Verify by hand the equation $\sum_{d\mid n} \varphi(d) = n$ in the case $n=12$.
  Here we are summing over the positive divisors of $n$.
\item Verify by computer that $\sum_{d\mid n} \varphi(d) = n$ for $n=1000$.  In your
solution make sure to explain exactly what you type into the computer, and what program
you use. 
\end{enumerate}

\end{enumerate}
\end{document}




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