\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{Math303}{Homework 8}{Due: Wed. Mar 6, 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}{}


\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.  See ``Guidelines and advice'' on the course webpage for more information.

\begin{enumerate}

\item \emph{Proof critiques.}  Give a critique of each claimed proof below.  A \emph{proof critique} addresses the following questions:  (1) Is the proof correct?  (2) If correct, can the proof be improved in some way?  (3) If incorrect, what is/are the error(s)?  Can they be fixed, and if so, how?

\begin{enumerate}
	\item 
		\begin{theorem} 
			If $x$ and $y$ are real numbers, then $\frac{x+y}{2} \ge \sqrt{xy}$.
		\end{theorem}
		\begin{proof}
			\begin{align*}
				\frac{x+y}{2} &\ge \sqrt{xy} \\
				x+y &\ge 2\sqrt{xy} \\
				(x+y)^2 &\ge 4xy \\
				x^2+2xy+y^2 &\ge 4xy\\
				x^2 -2xy + y^2 &\ge 0\\
				(x-y)^2 \ge 0
			\end{align*}
		\end{proof}
		
	\item 
		\begin{theorem}
			All real numbers are equal.
		\end{theorem}
		\begin{proof}
			Let $x$ and $y$ be real numbers.  Observe that 
				\[ x^2-y^2 = (x-y)(x+y) = x(x+y) - y(x+y).\]
			After rearranging terms, this becomes $x^2 - x(x+y) = y^2 - y(x+y)$.  Adding $\frac{(x+y)^2}{4}$ to both sides gives $x^2 - x(x+y) + \frac{(x+y)^2}{4} = y^2 - y(x+y) + \frac{(x+y)^2}{4}$.  Factoring both sides, we see that $(x-\frac{x+y}{2})^2 = (y - \frac{x+y}{2})^2$ and taking the square root gives $x-\frac{x+y}{2} = y-\frac{x+y}{2}$.  Adding $\frac{x+y}{2}$ to both sides gives $x=y$.  Since $x$ and $y$ were arbitrarily chosen real numbers, it follows that all real numbers are equal.
		\end{proof}
		
	\item
		\begin{theorem}
			If $n\in\ZZ$, then $n^2=3k$ or $n^2=3k+1$ for some $k\in\ZZ$.
		\end{theorem}
		\begin{proof}
			Suppose that $n\in\ZZ$.  By the division algorithm, it follows that $n=3q+r$ for some integers $q$ and $r$ with $0\le r < 3$.  Since $r$ is an integer and $0\le r < 3$, it follows that $r\in\{0,1,2\}$.  We consider three cases, depending on the value of $r$.
			
			\hspace{1cm} Case 1: If $r=0$, then $n^2 = (3q+0)^2 = 9q^2 = 3(3q^2)$, and so $n^2=3k$ when we set $k$ equal to the integer $3q^2$.
			
			\hspace{1cm} Case 2: If $r=1$, then $n^2 = (3q+1)^2 = 9q^2 + 6q + 1 = 3(3q^2 + 2q) + 1$, and so $n^2=3k+1$ when we set $k$ equal to the integer $3q^2 + 2q$.
			
			\hspace{1cm} Case 3: If $r=2$, then $n^2 = (3q+2)^2 = 9q^2 + 12q + 4 = 3(3q^2 + 4q + 1) + 1$, and so $n^2 = 3k+1$ when we set $k$ equal to the integer $3q^2 + 4q + 1$.
			
			In all cases, we have that $n^2=3k$ or $n^2=3k+1$ for some integer $k$. 
		\end{proof}
			
	\item 
		\begin{theorem}
			Let $a,b,c\in\ZZ$.  If $a\mid b$ and $b\mid c$, then $a\mid c$.
	      	\end{theorem}
	      	\begin{proof}
	      	Since $a\mid b$, we have that $b=ka$ for some integer $k$.  Similarly, since $b\mid c$, it follows that $c=kb$ for some integer $k$.  Therefore $c=kb=k(ka)=k^2a$.  Since $k^2$ is an integer, it follows that $a\mid c$.
	      	\end{proof}
\end{enumerate}


\item Use the method of direct proof to prove the following.
\begin{enumerate}
	\item Suppose $a$ is an integer.  If $7\mid 4a$, then $7\mid a$.  Hint: consider the equation $a=8a-7a$.
	\item Suppose $a$, $b$, and $c$ are integers.  If $a^2\mid b$ and $b^3\mid c$, then $a^6 \mid c$.
	\item If $x\in\RR$ and $0<x<4$, then $\frac{4}{x(4-x)} \ge 1$.
	\item Every odd integer is a difference of two squares.  (Example: $7=4^2 - 3^2$).
\end{enumerate} 


\end{enumerate}
\end{document}
