\DocumentMetadata{
  pdfstandard=ua-2, 
  lang=en-US,
  tagging=on,
  tagging-setup = {
    math/setup=mathml-SE,
    math/alt/use,
    table/header-rows = 1
  }
}

\documentclass[11pt]{article}
\usepackage{multicol,tikz,kgm2}
\usepackage{hyperref}
\usetikzlibrary{arrows,automata}
%\usepackage{fullpage}


\tikzstyle{vertex}=[circle,draw]

\newcommand{\kgmtitle}{Homework 7}

\hypersetup{
  pdftitle={\kgmtitle},  % Registers the PDF Title metadata
  pdfauthor={K.G. Milans},          % Registers the Author metadata
  pdfdisplaydoctitle=true           % Tells PDF viewers to display the title, not filename
}

\newcommand{\kgmcomment}[1]{}

\begin{document}
\headers{Math303}{\kgmtitle}{Due: Mon. Oct 12, 2026}
	

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

\newtheorem{theorem}{Theorem}{}

\section*{\vspace{-2em}\smash{\phantom{Solutions}}}

\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 Prove that if $n\in\ZZ$, then $5n^2 + 3n + 7$ is odd.  Hint: try cases.

\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 Recall that an integer $p$ is \emph{prime} if $p\ge 2$ and the only positive divisors of $p$ are $1$ and $p$.  Prove that if $n$ is a positive integer, $n\ge 2$, and $n$ is not prime, then $2^n - 1$ is not prime.  Hint: recall the geometric series formula: $\sum_{k=0}^n a^k = \frac{a^{n+1} - 1}{a-1}$ for $a\ne 1$.

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

\item We want to cover the 100 vertices in a $10\times 10$ square grid with lines that are not parallel to the sides.  What is the fewest number of lines such that this is possible?  A full answer (1) explains how to do it with a certain number of lines and (2) argues that it is not possible to do it with fewer lines.

For example, a $3\times 3$ square grid can be covered by $4$ lines not parallel to the square (see figure below).  Can you argue that $3$ lines is not enough?  Hint: think about the boundary of the grid.
\begin{center}
\begin{tikzpicture}
	\foreach \x in {1,2,3}
	{{
		\foreach \y in {1,2,3}
		{{
			\node[coordinate] at (\x,\y) (U\x\y) {} ;
		}}
	}}
	
	\draw (U11) -- (U33) ;
	\draw (U12) -- (U21) ;
	\draw (U13) -- (U31) ;
	\draw (U23) -- (U32) ;

	\foreach \x in {1,2,3}
	{{
		\foreach \y in {1,2,3}
		{{
			\node[medium vertex,inner sep=0pt,fill=black!30] at (\x,\y) (V\x\y) {} ;
		}}
	}}
\end{tikzpicture}
\end{center}

\end{enumerate}
\end{document}