\documentclass[12pt,a4paper]{amsart}
%%%%%%%%%%% Here is where you tell LaTeX to use packages. Each
%%%%%%%%%%% package gives you access to different commands and
%%%%%%%%%%% functionality. Most of them are unnecessary for the
%%%%%%%%%%% mathematics in this document.

%%%%%%%%%%% If you hadn't figured out, the % symbol automatically
%%%%%%%%%%% nulls out all subsequent characters on that line. So
%%%%%%%%%%% it's used for commenting code.
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{multicol}
\usepackage[OT2,T1]{fontenc}
\usepackage{graphicx}
\usepackage[all]{xy}
\usepackage{color}
\usepackage{mathrsfs}
\usepackage{mathtools}

%%%%%%%%%%% Determining margins and spacing.
\setlength\topmargin{-0.3in}
\addtolength{\oddsidemargin}{-.625in}
	\addtolength{\evensidemargin}{-.625in}
	\addtolength{\textwidth}{1.25in}
\setlength\footskip{1in}

%%%%%%%%%%% I think this command enables `sections'
\numberwithin{equation}{section}

%%%%%%%%%%% This command allows you to label things as `theorem',
%%%%%%%%%%% `conjecture', etc.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}{Question}[theorem]
\newtheorem{example}{Example}[theorem]


\usepackage[utf8]{inputenc}
\title{Math 220.201 Class 5 Solutions}
\begin{document}
\maketitle

\begin{enumerate}
\item [1.] Let $n\in \mathbb{Z}$. Prove that if $n$ is odd, then $n^2-5n+2$ is even.
\begin{proof}
If $n$ is an odd integer, then there is some integer $k$ such that $n=2k+1$. Then
$$
\begin{aligned}
n^2-5n+2 &= (2k+1)^2-5(2k+1)+2\\
 &= 4k^2+4k+1-10k-5+2\\
 &= 4k^2-6k-2\\
 &= 2(2k^2-3k-1)
\end{aligned}
$$
Since $k$ is an integer, $2k^2-3k-1$ is an integer. Therefore, $n^2-5n+2$ is an integer.
\end{proof}
\vskip 0.5in
\item [2.] Let $n\in\mathbb{Z}$. Prove that $n$ is odd if and only if $n^2$ is odd.
\begin{proof}
Let $n$ be an integer. We first prove that if $n$ is odd, then $n^2$ is odd. If $n$ is odd, then $n=2k+1$ for some integer $k$. Then
$$n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$$
Since $k$ is an integer, $2k^2+2k$ is an integer. Therefore, $n^2$ is odd.

Now, we prove that if $n^2$ is odd, then $n$ is odd. We do so by proving the contrapositive: namely showing that if $n$ is even, then $n^2$ is even.\footnote{Remember, we assumed $n$ is an integer.} If $n$ is even, then $n=2\ell$ for some integer $\ell$. Then
$$n^2=(2\ell)^2=4\ell^2=2(2\ell^2)$$
Since $\ell$ is an integer, $2\ell^2$ is an integer. Therefore, $n^2$ is even.
\end{proof}
\vskip 0.5in
\item [3.] Let $n\in\mathbb{Z}$. Prove that if $7n+4$ is even, then $3n-11$ is odd.
\begin{proof} We will show that\footnote{A logical maneuver we are using here is \emph{transitivity}, namely that for any statements (or open sentences) $P, Q, R$,
$$((P \implies Q) \wedge (Q\implies R))\implies (P\implies R)$$
If you want a fun exercise, you can either express the above statement entirely in terms of $\wedge, \vee, \sim$ and show it's a tautology, or write a truth table for it.}
\vskip 0.1in
\begin{center}
($7n+4$ is even $\implies$ $n$ is even) and ($n$ is even $\implies$ $3n-11$ is odd)
\end{center}
and deduce the conclusion.

Let's first prove the one on the left.\footnote{Note, we could prove these two in either order.} We show it by proving the contrapositive. Namely, we show that if $n$ is an odd integer, then $7n+4$ is odd. If $n$ is odd, then $n=2k+1$ for some integer $k$. Then
$$7n+4=7(2k+1)+4=14k+11=2(7k+5)+1$$
Since $k$ is an integer, $7k+5$ is an integer. Therefore, $7n+4$ is odd, as desired.

Now we show that if $n$ is even, $3n-11$ is odd. If $n$ is even, then $n=2\ell$ for some integer $\ell$. Then
$$3n-11=3(2\ell)-11=6\ell-11=2(3\ell-6)+1$$
Since $\ell$ is an integer, $3\ell-6$ is an integer. Therefore, $3n-11$ is odd, as desired.

\end{proof}
\vskip 0.2in
\begin{proof}
Here is an alternate proof. Suppose that $7n-4$ is even. Then $7n-4=2k$ for some integer $k$. Therefore
$$
\begin{aligned}
3n-11&=7n-4n-4-7&=(7n-4)-4n-7\\
&=2k+2(-2n-4)+1&= 2(k-2n-4)+1
\end{aligned}
$$
Since $k$ and $n$ are integers, $k-2n-4$ is an integer. Therefore, $3n-11$ is odd.\footnote{This is a proof where the way you'd figure it out is the reverse of the finished product. The idea of this proof is that you prove that the difference between $7n-4$ and $3n-11$ is \emph{always odd}.}
\end{proof}
\vskip 0.5in
\item [4.] Suppose that the following fact is known to be true\footnote{If you are curious how to prove this particular lemma, here is a rigorous proof.
\begin{proof}If $k$ is an integer, then it is either an even integer, or it is an odd integer.

If $k$ is even, then $k=2a$ for some integer $a$. Then $k(k+1)=2a(2a+1)=2(2a^2+a)$. Since $a$ is an integer, $2a^2+a$ is an integer, and so $k(k+1)$ is even.

If $k$ is odd, then $k=2b+1$ for some integer $b$. Then $k(k+1)=(2b+1)(2b+2)=2(2b^2+3b+1)$. Since $b$ is an integer, $2b^2+3b+1$ is an integer, and so $k(k+1)$ is even.\end{proof}}
\label{lemma:consecutive}\begin{lemma}
For every $k\in\mathbb{Z}$, $k(k+1)$ is an even integer.
\end{lemma}
Prove that if $n$ is any odd integer, then $n^2-1$ is a multiple of $8$.
\begin{proof}
Suppose that $n$ is an odd integer. Then $n=2k+1$ for some integer $k$. Then
$$n^2-1=(2k+1)^2-1=4k^2+4k+1-1=4k(k+1)$$
$k$ is an integer, so by the lemma, $k(k+1)$ is an even integer. Therefore, $k(k+1)=2\ell$ for some integer $\ell$. Then $n^2-1=4(2\ell)=8\ell$. Therefore, $n^2-1$ is a multiple of $8$.
\end{proof}
\vskip 0.5in
\item [5.] Let $n\in\mathbb{Z}$. Prove that $n^2-3n+9$ is odd.
\begin{proof}
If $n$ is an integer, then $n$ is even or $n$ is odd. We consider these two cases separately.
\vskip 0.1in
\underline{Case 1, $n$ is even:} If $n$ is even, then $n=2k$ for some integer $k$. Then
$$n^2-3n+9=(2k)^2-3(2k)+9=4k^2-6k+9=2(2k^2-3k+4)+1$$
Since $k$ is an integer, $2k^2-3k+4$ is an integer. Therefore, $n^2-3n+9$ is odd.

\underline{Case 2, $n$ is odd:} If $n$ is odd, then $n=2k+1$ for some integer $k$. Then
$$\begin{aligned}
n^2-3n+9 &= (2k+1)^2-3(2k+1)+9\\
&= 4k^2+4k+1-6k-3+9
&= 2(2k^2-k+3)+1\end{aligned}$$
Since $k$ is an integer, $2k^2-k+3$ is an integer. Therefore, $n^2-3n+9$ is odd.
\end{proof}
\vskip 0.2in
\begin{proof}
Here is an alternate proof. Notice that
$$n^2-3n+9=(n^2-3n+2)+7=(n-1)(n-2)+7$$
$$=(n-2)(n-2+1)+7$$
By Lemma \ref{lemma:consecutive}, $(n-2)(n-2+1)$ is even. Therefore, it can be written in the form $2\ell$ for some integer $\ell$. Thus, $n^2-3n+9=2\ell+7=2(\ell+3)+1$. Since $\ell$ is an integer, $\ell+3$ is an integer, and therefore $n^2-3n+9$ is odd.
\end{proof}
\vskip 0.5in
\item [6.] Let $a, b\in\mathbb{Z}$. Prove that
\vskip 0.1in
\begin{center}
$ab$ is even $\iff$ ($a$ is even) $\vee$ ($b$ is even)
\end{center}
\begin{proof}
\underline{$\Rightarrow$:} We first prove the forwards direction by proving its contrapositive\footnote{I have used De Morgan's law here.}

\begin{center}
($a$ is odd) $\wedge$ ($b$ is odd) $\implies$ $ab$ is odd
\end{center}
If $a$ and $b$ are odd, then $a=2k+1$ and $b=2\ell+1$ for some integers $k$ and $\ell$. Then
$$ab=(2k+1)(2\ell+1)=4k\ell+2k+2\ell+1=2(2k\ell+k+\ell)+1$$
Since $k$ and $\ell$ are integers, $2k\ell+k+\ell$ is an integer. Therefore, $ab$ is odd.
\vskip 0.1in
\underline{$\Leftarrow$:} We prove the backwards direction by considering two possible cases.

If $a$ is even, then $a=2k$ for some integer $k$. Then $ab=(2k)b=2(kb)$. Since $k$ and $b$ are integers, $kb$ is an integer. Therefore, $ab$ is even.

If $b$ is even, then $b=2\ell$ for some integer $\ell$. Then $ab=a(2\ell)=2(a\ell)$. Since $a$ and $\ell$ are integers, $a\ell$ is an integer. Therefore, $ab$ is even.
\end{proof}
\vskip 0.5in
\item [7.] The following is a faulty proof. Explain what is wrong with it.
\begin{proposition}
If $m$ is an even integer and $n$ an odd integer, then $3m+n+mn-1$ is a multiple of $4$.
\end{proposition}
\begin{proof}
Let $m$ be an even integer and $n$ an odd integer. Then $m=2k$ and $n=2k+1$ for some $k\in\mathbb{Z}$. Therefore
\begin{equation}
\begin{aligned}
3m+n+mn-1 &= 3(2k)+(2k+1)+2k(2k+1)-1\\
&= 6k+2k+1+4k^2+2k-1\\
 &= 4k^2+8k\\
 &= 4(k^2+2k)
\end{aligned}
\end{equation}
Since $k^2+2k$ is an integer, $3m+n+mn-1$ is a multiple of $4$.
\end{proof}
\vskip 0.1in
{\bf Solution:} The issue is that if $m$ is an arbitrary even integer and $n$ is an arbitrary odd integer, then $m=2k$ and $n=2\ell+1$ where $k$ and $\ell$ are not necessarily equal. In the faulty proof above, the same letter was used for both. The proposition is actually false: try $m=2$ and $n=3$.
\vskip 0.1in
\vskip 0.5in
\item [8.] Let $a, b, c, d, n \in \mathbb{Z}$. Prove that if $a\equiv b\pmod{n}$ and $c\equiv d\pmod{n}$, then $ac\equiv bd\pmod{n}$, where the notation `$\equiv \pmod{n}$' is defined below.
\begin{definition}
For integers $a, b,$ $n$, if $a-b$ is a multiple of $n$, let us write this as
\vskip 0.1in
\begin{center}
$n|(a-b)$ ; `$n$ \emph{divides} $a-b$', or
\vskip 0.1in
$a\equiv b\pmod{n}$ ; `$a$ \emph{is congruent to} $b$ \emph{modulo} $n$'.
\end{center}
\end{definition}
\begin{proof}
If $a \equiv b\pmod{n}$, then $a-b=kn$ for some integer $k$. Similarly $c-d=\ell n$ for some integer $\ell$. Then $a=b+kn$ and $c=d+\ell n$, so
$$
\begin{aligned}
ac-bd &=(b+kn)(d+\ell n)-bd\\
&=bd+kdn+b\ell n+k\ell n^2-bd\\
&= (kd+b\ell+k\ell n)n
\end{aligned}
$$
Since $k, \ell, n$ are integers, $kd+b\ell+k\ell n$ is an integer. Therefore, $ac \equiv bd\pmod{n}$.
\end{proof}
\end{enumerate}



\end{document}