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