\documentclass{article}
\voffset=-0.05\textheight
\textheight=1.1\textheight
\hoffset=-0.05\textwidth
\textwidth=1.1\textwidth
\title{Math 480 (Spring 2007): Homework 3}
\author{\bf Due: Monday, April 16}
\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.\\

\begin{enumerate}


\item Let $\vphi$ be the Euler phi function.  The first few values
of $\vphi$ are as follows (you do not have to prove this):
    	\begin{verbatim}
	1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8 20 12 18 12 28 
	\end{verbatim}
Notice that most of these numbers are even.  
{\em Prove for all $n>2$ that $\vphi(n)$ is an even integer.}
(You may using anything that is proved
about $\vphi$ in the course textbook.)

\item Compute each of the following {\em entirely by hand -- no calculator}.
In each case, given the problem $\xgcd(a,b)$,
your final answer will be integers $x,y,g$ such that
$ax+by=g$.  It is probably best to use the algorithm
I described in class, which is also in the newest version
of the course notes.
\begin{enumerate}
\item $\xgcd(15,35)$
\item $\xgcd(59,-101)$
\item $\xgcd(-931,343)$
\item $\xgcd(-123,-45)$
\item $\xgcd(144,233)$
\item Find integers $x$ and $y$ such that $17x-19y = 5$.
\end{enumerate}

\item Do each of the following using any means (including a computer).
As in the previous problem, your answer is integers $x,y,g$ such
that $ax+by=g$. 
\begin{enumerate}
\item $\xgcd(2007,2003)$
\item $\xgcd(12345,678910)$
\item $\xgcd(2^{101}-1, 2^{101}+1)$
\end{enumerate}

\item Prove that there are infinitely many composite numbers $n$
such that for all $a$ with $\gcd(a,n)=1$, we have
$a^{n-1}\con a\pmod{n}$.  (Hint: consider $n=2p$ with $p$ an odd prime.)

\item Solve each of the following equations for $x$ (you may use a computer
if necessary):
\begin{enumerate}
\item $59x \con 5 \pmod{101}$
\item $144x + 1 \con 2 \pmod{233}$
\item $17x \con 18 \pmod{19}$
\end{enumerate}

\item Prime numbers $p$ and $q$ are called {\em twin primes} if $q = p+2$. 
For example, the first few twin prime pairs are
$$(3,5), (5,7), (11,13), (17,19), (29,31), (41,43), (59,61), (71,73), (101,103),$$
and it is an open problem to prove that there are infinitely many.
Notice in the above list of pairs $(p,q)$ that, {\em except for the first pair},
we have that $p+q$ is divisible by $12$. 
Prove that if $p$ and $q$ are twin primes with $p\geq 5$,
then $p+q \con 0 \pmod{12}$, as follows:
\begin{enumerate}
\item Prove that if $p\geq 5$ is prime, then $p \con 1, 5, 7, 11\pmod{12}$,
i.e., there are only four possibilities for $p$ modulo $12$.
\item Show that if $p$ and $p+2$ are both prime with $p\geq 5$, then $p \con 5 \pmod{12}$
or $p\con 11\pmod{12}$.
\item Conclude  that $p+q\con 0\pmod{12}$. 
\end{enumerate}

\item 
Let $n=323$. Do the following by hand:
\begin{enumerate}
\item Write $n$ in binary, i.e., base $2$.
\item Compute $2^{n-1} \pmod{n}$ by hand. 
\item Is $n$ prime.  Why or why not?
\end{enumerate}

\item 
Let $n=167659$.
\begin{enumerate}
\item Use a computer to write $n$ in binary.
E.g., in \sage, use {\tt 167659.str(2)}.
\item Use a computer to compute $2^{n-1}\pmod{n}$, e.g.,
in \sage do \verb+n=167659; Mod(2,n)^(n-1)+.
\item Is $n$ prime?
\end{enumerate}


\end{enumerate}
\end{document}




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