\documentclass[11pt]{article}
\usepackage{jeffe,handout,multicol,tikz,ulem}
\usetikzlibrary{arrows,automata}
\usepackage[latin1]{inputenc}

\tikzstyle{vertex}=[circle,draw]

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math 303}{Homework 10}{Due: Wed. Mar 27, 2024}

%\makeatletter
%\def\@oddfoot{\hfill \tikz \node[draw] {over} ; }
%\makeatother

\makeatletter
\def\@oddfoot{}
\makeatother

%\noindent
%\hfill Name: \underline{\hspace{3.5in}} 

%\begin{flushright}
%Name: \underline{\hspace{3.5in}} \\
%\end{flushright}
%\hrule

\def\columnseprule{0.4pt}

\newcommand{\PS}{\mathcal{P}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\st}{\colon \,}
\newcommand{\comp}[1]{\overline{#1}}
\renewcommand{\emptyset}{\varnothing}
\newtheorem{theorem}{Theorem}{}





%%
%% FUTURE/ HW11:
%%  $Let a,b,c,d\in\ZZ$ and suppose that $|bc-ad| = 1$.  Prove that $\gcd(an+b,cn+d)=1$ for each $n\in\ZZ$.
%% Suppose n bits are arranged.  In each interval of size m, we want an odd number of bits set to 1.  For which pairs $(n,m)$ is this possible?
%%
%%  Cake flipping problem.  Cut slices with angle $\theta$.  In terms of $\theta$, will cake ever be all facing up again?  Will it ever be all face down?
%%

\noindent
\textbf{Directions:} You may work to solve these problems in groups, but all written work must be your own.  Unless the problem indicates otherwise, all problems require some justification; a correct answer without supporting reasoning is not sufficient.  Submissions must be stapled.  See ``Guidelines and advice'' on the course webpage for more information.

\begin{enumerate}


\item Prove the following using the method of proof by contradiction.
\begin{enumerate}
	\item Show that $2^{\frac{1}{3}}$ is irrational.
	\item Suppose that $a,b,c\in\ZZ$.  Show that if $a^2+b^2=c^2$, then $a$ or $b$ is even. 
	\item Prove that there are no integers $a$ and $b$ such that $21a + 30b = 1$.
\end{enumerate}

\item Irrational powers of three.
\begin{enumerate}
	\item Let $a$ be an integer.  Prove that if $3\mid a^2$, then $3\mid a$.
	\item Prove that if $k$ is an odd positive integer, then $\sqrt{3^k}$ is irrational.  Hint: suppose for a contradiction that the implication is false for some values of $k$, and let $k$ be the \emph{least} odd positive integer for which the implication fails.
\end{enumerate}

\item Using only logic and trigonometry (not calculus), show that $\sin(x) + \sqrt{3}\cos(x) \le 2$ for each real number $x$.  (Hint: recall that $\tan(\pi / 3) = \sqrt{3}$.)

\item {} Critique the following argument.  (Be careful!)
\begin{center}
\begin{minipage}{0.90\textwidth}
\begin{theorem}
If $p_1, \ldots, p_k$ is a list of the first $k$ primes, then $p_1 p_2 \cdots p_k + 1$ is also a prime.
\end{theorem}
\begin{proof}
Let $n=p_1p_2\cdots p_k + 1$, and note that $1=n-p_1 p_2 \cdots  p_k$.  

Suppose for a contradiction that some prime $p_i$ less than $n$ divides $n$.  If this were true, then $p_i$ divides both terms on the right hand side of $1=n-p_1 p_2  \cdots  p_k$ and therefore $p_i$ must also divide the left hand side of this equation.  Since no prime divides $1$, we have a contradiction.  

The contradiction implies that no prime less than $n$ divides $n$, and therefore $n$ is prime.
\end{proof}
\end{minipage}
\end{center}

\item Counting Subsets and The Binomial Theorem.
\begin{enumerate}
\item Suppose that $A$ is a set and $|A| = 84$.  How many subsets of $A$ have $0$ elements?  How many have $10$ elements?  How many have $74$ elements?

\item Suppose that $A$ is a set and there are $330$ subsets of $A$ of size $7$.  What is $|A|$?

\item Use the binomial theorem to find the coefficient of $x^4y^8$ in $(3x-2y)^{12}$.
\end{enumerate}


\item Prove the following (using any method).
\begin{enumerate}
	\item Suppose that $x\in\ZZ$.  Prove that $x$ is even if and only if $3x+5$ is odd.
	\item An integer $a$ is odd if and only if $a^3$ is odd.
	\item Suppose $x,y\in\RR$.  Then $(x+y)^2 = x^2 + y^2$ if and only if $x=0$ or $y=0$.
\end{enumerate}

\item Prove that for each $d\in\NN$, there exist infinitely many primes $p$ such that $p+d$ is not prime. (Hint: try proof by contradiction.  What does it mean for this claim to be false?  In other words, what is the logical negation of this claim?  If you have trouble formulating the negation, then it may be helpful to translate the claim into a symbolic logic formula $\varphi$, negate $\varphi$ and simplify, and finally translate back into English.)

\end{enumerate}
\end{document}
