\documentclass[12pt]{article} \usepackage{comment} \begin{document} \centerline{\bf Homework 4 MORALLY Due Feb 29 at 9:00AM} \newcommand{\implies}{\Rightarrow} \newcommand{\MOD}{{\rm MOD}} \newcommand{\PRIMES}{{\rm PRIMES}} \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!!!!!!!!!!!!!!!!!} \begin{enumerate} \item (0 points but please DO IT) What is your name? \bigskip \item (20 points) \begin{enumerate} \item (20 points) Show that, for all primes $p$, $p^{1/5}\notin\Q$. USE the Unique Factorization. \item (0 points) Try to do it using the MOD method. Discuss if this works or not. \end{enumerate} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (20 points) Let $\PRIMES$ be the set of primes. Let $\MOD_{i,j}$ be the set of numbers that are $\equiv i \pmod j$. Let $\PRIMES_{i,j}=\PRIMES \cap \MOD_{i,j}$. For example $\PRIMES_{1,4}$ is the set of primes that are $\equiv 1 \pmod 4$. \begin{enumerate} \item Show that $\PRIMES_{3,4}$ is infinite. (Hint: If $p_1,\ldots,p_L$ are all of the primes $\equiv 3 \pmod 4$ then look at $4p_1\cdots p_L - 1$.) \item Show that $\PRIMES_{5,6}$ is infinite. \item Give an infinite sequence $i_1 < j_1 < i_2 < j_2 < \cdots$ such that $\PRIMES_{i_1,j_1}$ is EMPTY. $\PRIMES_{i_2,j_2}$ is EMPTY. $\PRIMES_{i_3,j_3}$ is EMPTY. etc. \item Give an infinite sequence $i_1 < j_1 < i_2 < j_2 < \cdots$ such that $\PRIMES_{i_1,j_1}$ is FINITE but not EMPTY. $\PRIMES_{i_2,j_2}$ is FINITE but not EMPTY. $\PRIMES_{i_3,j_3}$ is FINITE but not EMPTY. etc. \end{enumerate} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (30 points- 10 points each) For each of the following sequences find a {\it simple} function $A(n)$ such that the sequence is $A(1)$, $A(2)$, $\ldots$. (I am not going to define simple rigorously, but just keep it simple.) \begin{enumerate} \item $10, -17, 24, -31, 38, -45, 52, \ldots$. \item $-1, 1, 5, 13, 29, 61, 125, \ldots$. \item $6, 9, 14, 21, 30, 41, 54, \ldots$. \end{enumerate} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (25 points) In Grand Fenwick they have two types of coins: one worth 100 cents, and one worth 101 cents. \begin{enumerate} \item (15 points) Show that for all $n\ge 9900$ one can form $n$ with these two types of coins. (In Math: $$(\forall n\ge 9900)(\exists x,y\in\N)[n=100x+101y].$$ ) \item (10 points) Prove or Disprove: There is NO way to form 9899 cents in Grand Fenwick. (In Math: $$(\forall x,y\in \N)[9899\ne 100x+101y].$$ ) \item (0 points but you should do it) If you DID NOT KNOW the bound of 9900 how would you find it. HINT: Use Wolfram Alpha. \end{enumerate} \vfill \centerline{\bf GO TO NEXT PAGE} \newpage \item (Extra Credit) Prove or Disprove: there is a second order sentence that is TRUE of $\Q + \Q$ but false of $\Q$. \end{enumerate} \end{document}