\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}