\documentclass[12pt,oneside]{amsart}
\usepackage{geometry}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
%\usepackage{pdfpages}
\usepackage{enumerate}
\usepackage[all]{xy}
\usepackage{graphicx}
\graphicspath{ {./images/} }
\usepackage{appendix}
%\usepackage{caption}
\usepackage{subcaption}
\usepackage{color}
\usepackage{verbatim}
\usepackage{mathtools}
\usepackage{tikz-cd}
\usepackage[section]{placeins}
\usepackage{showkeys}
\usepackage{hyperref}
\usepackage{enumitem}
\usepackage{multicol}
\hypersetup{
  colorlinks=true,
  allcolors=blue,
}

%ENVIRONMENTS
\newtheorem{theorem}{Theorem}
\newtheorem*{theorem*}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{remark}{Remark}
\newtheorem{conjecture}{Conjecture}
\newtheorem{example}{Example}
\newtheorem{proposition}{Proposition}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{note}{Note}

%OPERATORS
\DeclareMathOperator{\dist}{dist}

%SYMBOLS
\def\a{\alpha}
\def\b{\beta}
\def\m{\mu}
\def\n{\nu}
\def\u{\upsilon}
\def\l{\lambda}
\def\CC{\mathbb{C}}
\def\R{\mathbb{R}}
\def\Q{\mathbb{Q}}
\def\Z{\mathbb{Z}}
\def\N{\mathbb{N}}
\def\T{\mathbb{T}}
\def\H{\mathbb{H}}
\def\S{\Sigma}
\def\s{\sigma}
\def\e{\epsilon}
\def\B{\mathcal{B}}
\def\O{\Omega}
\def\o{\omega}
\def\C{\mathcal{C}}
\def\U{\mathcal{U}}
\def\A{\mathcal{A}}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{Homework 7 Solutions - Discrete Math spring 2023}
\author{John Adamski}
\address{Department of Mathematics, Fordham University}
\email{adamski@fordham.edu}
\urladdr{www.johnadamski.com}

%\begin{abstract}
%Great stuff!
%\end{abstract}

%\tableofcontents

\maketitle 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{theorem*}\label{7.4}
  Given an integer $a$, then $a^2 + 4a + 5$ is odd if and only if $a$ is even.
\end{theorem*}

\begin{proof}
  We prove this biconditional statement in two steps. 
  First, we show directly that if $a$ is even then $a^2 + 4a + 5$ is odd.
  So let us assume that $a$ is even and set $a = 2n$ for some integer $n$.
  Then
  \begin{align*}
  	a^2 + 4a + 5 &= (2n)^2 + 4(2n) + 5 \\
  	  &= 2(2n^2 + 4n + 2) + 1.
  \end{align*}
  Since $2n^2 + 4n + 2$ is an integer, this shows that $a^2 + 4a + 5$ is odd.

  Next, we show that if $a^2 + 4a + 5$ is odd then $a$ is even.
  To do this we will prove the contrapositive statement: if $a$ is odd then $a^2 + 4a + 5$ is even.
  So let us assume that $a$ is odd and set $a = 2n + 1$ for some integer $n$.
  Then
  \begin{align*}
  	a^2 + 4a + 5 &= (2n + 1)^2 + 4(2n + 1) + 5 \\
  	  &= 2(2n^2 + 6n + 5).
  \end{align*}
  Since $2n^2 + 6n + 5$ is an integer, this shows that $a^2 + 4a + 5$ is even. This completes the proof.
\end{proof}





\begin{theorem*}\label{7.8}
  Suppose $a,b \in \Z$. Prove that $a \equiv b \pmod{10}$ if and only if $a \equiv b \pmod{2}$ and $a \equiv b \pmod{5}$.
\end{theorem*}
\begin{proof}
  First, let us assume that $a \equiv b \pmod{10}$ and show directly that $a \equiv b \pmod{2}$ and $a \equiv b \pmod{5}$.
  By definition, $a - b = 10n$ for some integer $n$, and so
  \begin{equation}
    a - b = 2(5n) = 5(2n).
  \end{equation}
  Since both $5n$ and $2n$ are integers, it follows that $a \equiv b \pmod{2}$ and $a \equiv b \pmod{5}$.

  Now let us prove the converse by assuming $a \equiv b \pmod{2}$ and $a \equiv b \pmod{5}$ then showing that $a \equiv b \pmod{10}$.
  By definition, we have $a - b = 2x$ and $a - b = 5y$ for some integers $x$ and $y$.
  Thus $2x = 5y$ and, in particular, $5y$ is even. Since $5$ is odd, it follows that $y$ must be even.
  That is, $y = 2m$ for some integer $m$.
  Therefore
  \begin{equation*}
    a - b = 5(2m) = 10m,
  \end{equation*}
  and so $a \equiv b \pmod{1-}$.
\end{proof}




\begin{theorem*}\label{7.16}
  Suppose $a, b \in \Z$. If $ab$ is odd, then $a^2 + b^2$ is even.
\end{theorem*}
\begin{proof}
  In order to prove the statement directly, let us assume that $ab$ is odd.
  It follows that both $a$ and $b$ are odd, for otherwise $ab$ would be even.
  Set $a = 2n + 1$ and $b = 2m + 1$ for some integers $m$ and $n$.
  Then
  \begin{align*}
  	a^2 + b^2 &= (2n + 1)^2 + (2m + 1)^2 \\
  	  &= 2(2n^2 + 2m^2 + 2n + 2m + 1).
  \end{align*}
  Since $2n^2 + 2m^2 + 2n + 2m + 1$ is an integer, this shows that $a^2 + b^2$ is even.
\end{proof}




\begin{theorem*}\label{7.22}
  If $n \in \Z$, then $4 \mid n^2$ or $4 \mid (n^2 - 1)$.
\end{theorem*}
\begin{proof}
  We break this into cases based on the parity of $n$. 
  If $n$ is even then set $n = 2x$ for some integer $x$.
  Then
  \begin{equation*}
    n^2 = (2x)^2 = 4x^2.
  \end{equation*}
  Since $x^2$ is an integer, this shows that $4 \mid n^2$.

  Now let us consider the case that $n$ is odd.
  Set $n = 2y + 1$ for some integer $y$.
  Then
  \begin{align*}
  	n^2 - 1&= (2y + 1)^2 - 1\\
  	  &= 4(y^2 + y).
  \end{align*}
  Since $y^2 + y$ is an integer, this shows that $4 \mid (n^2 - 1)$.
  In summary, for any integer $n$, it is true that $4 \mid n^2$ or $4 \mid (n^2 - 1)$.
\end{proof}



\begin{theorem*}\label{8.4}
  If $m,n \in \Z$, then $\{x \in \Z : mn \mid x\} \subseteq \{x \in \Z : m \mid x\} \cap \{ x \in \Z : n \mid x\}.$
\end{theorem*}
\begin{proof}
  Suppose $a \in \{x \in \Z : mn \mid x\}$. Then $a$ is an integer and $mn \mid a$.
  Set $a = (mn)b$ for some integer $b$.
  Then
  \begin{equation*}
    a = m(nb) = n(mb).
  \end{equation*}
  Since both $nb$ and $mb$ are integers, this shows that $m \mid a$ and $n \mid a$.
  Thus 
  \begin{equation*}
    a \in \{x \in \Z : m \mid x\} \cap \{ x \in \Z : n \mid x\}.
  \end{equation*}
  This completes the proof.
\end{proof}



\begin{theorem*}\label{8.6}
  Suppose $A,B$ and $C$ are sets. Prove that if $A\subseteq B$, then $A - C \subseteq B - C$.
\end{theorem*}
\begin{proof}
  To prove this directly, let us assume that $A \subseteq B$ and $x \in A - C$.
  We must show that $x \in B - C$.
  Since $x\in A - C$, by definition $x\in A$ and $x\notin C$.
  Since $A\subseteq B$, it follows that $x \in B$.
  Therefore, $x\in B$ and $x\notin C$.
  That is, by definition, $x \in B - C$.
\end{proof}



\begin{lemma}{(Distributive Rule)}\label{lemma}
   Let $P, Q$ and $R$ be statements. Then
   \begin{equation*}
     P \vee (Q \wedge R) = (P \vee Q) \wedge (P \vee R).
   \end{equation*}
\end{lemma}
\begin{proof}
  The following truth table proves the logical equivalence.
  \begin{center}
  \begin{tabular}{ c|c|c|c|c|c|c|c }
   $P$ & $Q$ & $R$ & $Q \wedge R$ & $P \vee Q$ & $P \vee R$ & $P \vee (Q \wedge R)$ & $(P \vee Q) \wedge (P \vee R)$ \\
   \hline 
   T	&T	&T	&T	&T	&T	&T	&T \\
   T	&T	&F	&F	&T	&T	&T	&T \\
   T	&F	&T	&F	&T	&T	&T	&T \\
   T	&F	&F	&F	&T	&T	&T	&T \\
   F	&T	&T	&T	&T	&T	&T	&T \\
   F	&T	&F	&F	&T	&F	&F	&F \\
   F	&F	&T	&F	&F	&T	&F	&F \\
   F	&F	&F	&F	&F	&F	&F	&F 
  \end{tabular}
  \end{center}
\end{proof}



\begin{theorem*}\label{8.8}
  If $A, B$ and $C$ are sets, then $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$.
\end{theorem*}
\begin{proof}
  We prove this directly using only definitions and logically equivalent statements.
  Note that the logical equivalence of lines 2 and 3 follows immediately from the previous lemma.\footnote{You are free to use without proof the distributive rule and all logical equivalences listed on page 52 of \href{https://www.people.vcu.edu/~rhammack/BookOfProof/}{Book of Proof}, by Richard Hammock.}
  \begin{align*}
  	A \cup (B \cap C)  &= \{x : (x \in A) \vee (x \in B \cap C)\} \\
  	  &= \{x : (x \in A) \vee ((x \in B) \wedge (x \in C))\} \\
  	  &= \{x : ((x \in A) \vee (x \in B)) \wedge ((x \in A) \vee (x \in C))\} \\
  	  &= \{x : (x \in A) \vee (x \in B)\} \cap \{x : (x \in A) \vee (x \in C)\} \\
  	  &= (A \cup B) \cap (A \cup C)
  \end{align*}
\end{proof}



\begin{theorem}\label{8.20}
  Prove that $\{9^n : n \in \Q\} = \{3^n : n \in \Q\}$.
\end{theorem}
\begin{proof}
  Set $A = \{9^n : n \in \Q\}$ and let $B = \{3^n : n \in \Q\}$. 
  We prove the statement in two steps by showing $A\subseteq B$ and $B \subseteq A$. 
  First we show that $A \subseteq B$.
  Let us assume that $x \in A$.
  Then there is a rational number $n$ such that 
  \begin{equation*}
    x = 9^n = (3^2)^n = 3^{2n}.
  \end{equation*}
  Since $2n \in \Q$, it follows that $x \in B$.

  Now assume that $x\in B$.
  Then there is a rational number $m$ such that
  \begin{equation*}
    x = 3^m = \left(9^{1/2}\right)^m = 9^{m/2}.
  \end{equation*}
  Since $m/2\in\Q$, it follows that $x \in A$.
  This completes the proof.
\end{proof}



\begin{theorem*}\label{8.28}
  Prove that $\{12a + 25b : a,b\in\Z\} = \Z$.
\end{theorem*}
\begin{proof}
  We prove the statement in two steps.
  First, Since $12$ and $25$ are integers, it is clear that whenever $a$ and $b$ are integers then so is $12a + 25b$.
  This shows that $\{12a + 25b : a,b\in\Z\} \subseteq \Z$.

  Next, let $n \in \Z$.
  Observe that
  \begin{equation*}
    1 = 12(-2) + 25(1),
  \end{equation*}
  and so
  \begin{equation*}
    n = n\cdot 1 = n\left( 12(-2) + 25(1) \right) = 12(-2n) + 25(n).
  \end{equation*}
  Since both $n$ and $-2n$ are integers, it follows that $n \in \{12a + 25b : a,b\in\Z\}$.
  Therefore $\Z \subset \{12a + 25b : a,b\in\Z\}$.
  This completes the proof.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{thebibliography}{99}

%\bibitem{}
%\newblock 
%\newblock 
   
%\end{thebibliography}

\end{document}