\documentclass[12pt]{article}

\begin{document}

\centerline{\bf Homework 3 MORALLY Due Feb 21 at 9:00AM}
\newcommand{\implies}{\Rightarrow}
\newcommand{\NSQ}{{\rm NSQ}}
\newcommand{\into}{{\rightarrow}}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\Ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\ceil}[1]{\left\lceil {#1}\right\rceil}
\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\Z}{{\sf Z}}
\newcommand{\N}{{\sf N}}
\newcommand{\Q}{{\sf Q}}
\newcommand{\R}{{\sf R}}
\newcommand{\Rpos}{{\sf R}^+}

\centerline{\bf WARNING: THIS HW IS SIX PAGES LONG!!!!!!!!!!!!!!!!!}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}

\item
(25 points)
Give a sentence in the first order language of $<$ that is TRUE in $\Q+\Z$
but FALSE in $\Z+\Q$. 

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(25 points)
Let $p$ be a prime and $g\in \{1,\ldots,p-1\}$.
$g$ is a {\it generator for mod $p$} if 

$$\{g^1,\ldots,g^{p-1}\} = \{1,\ldots,p-1\}.$$

(Note that we are NOT saying $g_1=1$, $g^2=2$, $\ldots$ $g^{p-1}=p-1$.) 


A \textit{safe prime} is a prime number $p$ of the form:
$$p=2q+1$$
where $q$ is also a prime number.

\begin{enumerate}
\item
(0 points but you will need this for part 3.) 
Write a program that will, given $p$, a safe prime, and $g\in\{1,\ldots,p-1\}$, determines 
if $g$ is a generator for mod $p$. 

\item
(0 points but you will need this for part 3.) 
Write a program that will, given safe prime $p$, determine how many generators for mod $p$ there are. 
\item
(25 points) 
Run the program on all primes $\le 1000$ and submit your program by emailing it to Emily (ekaplitz@umd.edu).
\item
(0 points but I REALLY WANT YOU TO DO THIS. This is the WHOLE POINT OF THE PROBLEM,
but since it is speculative its hard to grade. Do it for ENLIGHTENMENT!) 
Graph $f(p)=$ the number of generators mod $p$. 
See if you can determine what function its close to (e.g., is it close to $\sqrt{p}$?)
\end{enumerate} 

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage


\item
(25 points)
\begin{enumerate}
\item 
(25 points)
Show that $7^{1/3}$ is irrational.
(First proof a lemma about mods.)
\item
(0 points, BUT DO IT!!!!)
Try to use your proof to show that $8^{1/3}$ is irrational.
What goes wrong? 
\end{enumerate} 

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage



\newpage

\item
(25 points)
Show that 23 CANNOT be written as the sum of $\le 8$ cubes. 

\vfill

\centerline{\bf GOTO NEXT PAGE}

\newpage

\item
(Extra Credit) 
Show that $2^{1/3}$ does not satisfy any 
quadratic equation of the form $ax^2+bx+c=0$ with $a,b,c\in \Z$. 


\vfill

\newpage

\centerline{\bf GOTO NEXT PAGE}

\item
(Extra Credit) 

{\it Known} for all $k$, DUP wins the $k$-round DUP-SPOILER game with
$\Z$ and $\Z+\Z$.

Hence there is no {\bf First Order} sentence that is TRUE for $\Z+\Z$ but FALSE for $\Z$. 

Give a {\bf Second Order } sentence that is TRUE in $\Z+\Z$ but false in $\Z$. 

\end{enumerate}
\end{document}