\documentclass[12pt]{article}

\usepackage{comment}
\usepackage{amsmath}
\usepackage{amssymb}  % for \nmid

\newcommand{\D}{{\mathbb D}}
\newcommand{\G}{{\mathbb G}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Q}{{\mathbb Q}}
\newcommand{\R}{{\mathbb R}}
\newcommand{\succc}{{\rm succ}}
\newcommand{\pred}{{\rm pred}}

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

\begin{document}


\centerline{Homework 06, MORALLY Due March 24} 


\begin{enumerate}

\item
(0 points)
What is your name.

\vfill 

\centerline{\bf GO TO THE NEXT PAGE}

\newpage

\item
(25 points) 
In this problem we will guide you through the proof that the following set
is infinite

$$X=\{ p \colon p\equiv 3 \pmod 4 \hbox{ and $p$ is prime } \}.$$

We begin the proof for you but you will need to finish it. 

{\it 
Assume $X$ is finite. So let $X=\{p_1,\ldots,p_k\}$. 

Let

$N= 4p_1p_2\cdots p_k - 1$

If $N$ is prime then you have found a prime NOT on the list. You are done!

If $N$ is not prime then let $N=q_1^{a_1}\cdots q_m^{a_m}$. 
where $q_1,\ldots,q_m$ are primes. } 

YOU NEED TO SHOW THAT at least one of the $q_i$ is $\equiv 3 \pmod 4$. 


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item
(25 points)
Let $a_n$ be defined as follows

$a_0=1$

$a_1=100$

$(\forall n\ge 2)[a_n = a_{n-1} + 3a_{n-2}]$

Find INTEGERS $A,B$ such that

$(\forall n\ge 0)[a_n \le AB^n].$

Try to make $B$ as small as possible .


\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage


\item 
(25 points) 
(This is the Honors Problem from HW04 BUT you will now do it 
rigorously with induction!)

By the {\it Four Color Theorem} every planar graph is 4 colorable.
You may use this. 

A graph has {\it crossing number $c$} if there is a way
to draw it so that if you REMOVE $c$ edges, the graph is planar.

Prove the following by induction. So give a Base Case, an Induction Hypothesis,
and an Induction step.

{\it Every graph of crossing number $c$ is $c+4$-colorable.} 

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage





\item
(25 points) In this problem we guide you through a proof that number of the
form $4^n(8k+7)$ cannot be written as the sum of 3 squares. 

\begin{enumerate}
\item
(0 points but you will need this for later)
Find the following set 

$$X = \{ x^2 \pmod 8 \colon x\in \{0,1,2,3,4,5,6,7\}\}.$$

\item
(0 points, this is more of a review of what you've already seen) 
Show that if $x\equiv 7 \pmod 8$ then $x$ is NOT the sum of three squares. 
Also, we need this later for the base case. 

\item
(10 points) 
Prove that if $x^2+y^2+z^2 \equiv 0 \pmod 4$ then $x,y,z$ are all even. 

{\it Hint:} Prove the contrapositive.


\item
(15 points) 
Prove the following by induction on $n$. 

{\bf Theorem} Let $n\ge 0$. Let $k\in\N$. Show that $4^n(8k+7)$ cannot be written
as the sum of 3 squares. 

(Hint: Use Part 3.) 

\end{enumerate}

\vfill

\centerline{\bf GO TO NEXT PAGE}

\newpage

\item 
(0 points Extra Credit)
\begin{enumerate}
\item
Give a complete prove of the following theorem: 

{\it $\{ n \colon \hbox{$n$ is prime and } n\equiv 1 \pmod 4 \}$ is infinite.}

The proof must be understandable to the students taking 250H. See next item. 

{\bf Permission} I doubt you can do this without looking it up, so feel
free to look it up. The important this is that you {\it understand} the
proof and can explain it.

\item
Make up slides in LaTeX to prove the theorem above. I may ask you to
present it to the class. (If you don't want to, then I might.) 

\end{enumerate} 

\end{enumerate}

\end{document}