\documentclass[12pt]{amsart}

\usepackage{amsmath, amssymb, amsthm}
\usepackage[margin=0.5in]{geometry}
\usepackage[pdflang={en-US}]{hyperref}
\usepackage[shortlabels]{enumitem}

\usepackage{tikz}

\renewcommand{\thesection}{\Alph{section}}

\newcommand{\scs}[1]{\begin{scshape}#1\end{scshape}}
\newcommand*{\inv}{^{-1}}
\newcommand*{\RR}{\mathbb{R}}
\newcommand*{\QQ}{\mathbb{Q}}
\newcommand*{\ZZ}{\mathbb{Z}}
\newcommand*{\NN}{\mathbb{N}}

\newcommand*{\inte}[2][x]{\int #2\, d#1}
\newcommand*{\der}[2][x]{\frac{d}{d#1}\!\left[ #2 \right]}
\newcommand*{\lcm}{\text{lcm}}

\newtheorem*{theorem}{Theorem}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem{problem}{}
\newtheorem*{challenge}{Challenge}
\newtheorem*{example}{Example}
\newtheorem*{solution}{Solution}
\newtheorem*{method}{Method}
\newtheorem*{facts}{Facts}

\newcommand{\thm}[1]{\begin{theorem}#1\end{theorem}}
\newcommand{\prob}[1]{\begin{problem}#1\end{problem}}
\newcommand{\dfn}[1]{\begin{definition}#1\end{definition}}
\newcommand{\chal}[1]{\begin{challenge}#1\end{challenge}}
\newcommand{\eg}[1]{\begin{example}#1\end{example}}
\newcommand{\sol}[1]{\begin{solution}#1\end{solution}}
\newcommand{\mtd}[1]{\begin{method}#1\end{method}}
\newcommand{\fcts}[1]{\begin{facts}#1\end{facts}}

\newcommand{\abs}[1]{\left| #1 \right|}

\title{Proofs I}
\date{September 20--22, 2021}

\begin{document}
\ \vspace{-.25in}

\maketitle

\vspace{-.15in}

\dfn{
Let $a, b \in \ZZ$.
\begin{enumerate}[a)]

\item $a$ is \textbf{even} if there is $c \in \ZZ$ such that $a = 2c$. (This is the same as $2|a$).

\item $a$ is \textbf{odd} if there is $c \in \ZZ$ such that $a = 2c+1$.

\item \textbf{$a$ divides $b$}, written $a|b$, if there is $c \in \ZZ$ such that $ac = b$. (Also expressed ``$b$ is divisible by $a$'').

\item The \textbf{greatest common divisor} of $a$ and $b$, written $\gcd(a,b)$, is the largest integer that divides both $a$ and $b$.

\item The \textbf{least common multiple} of $a$ and $b$, written $\lcm(a,b)$, is the smallest positive integer divisible by both $a$ and $b$.

\end{enumerate}
}

\dfn{
Let $n \in \NN$.
\begin{enumerate}[a)]

\item If $n \geq 2$ and the only positive divisors $n$ are $1$ and $n$, then $n$ is \textbf{prime}.

\item If $n \geq 2$ and $n$ is not prime, then $n$ is \textbf{composite}.\footnote{1 is neither prime nor composite.}

\end{enumerate}
}

\fcts{ 
We assume (without proof) the following:
\begin{enumerate}[a)]
\item If $m$ and $n$ are integers, then $m+n$, $m-n$, and $mn$ are all integers.
\item Given integers $m$ and $n$ with $n >0$, there are unique integers $q$ and $r$ such that $m = qn +r$ and $0 \leq r < n$.
\end{enumerate}
}

\eg{
Let $a, b, c \in \ZZ$.
Prove that if $a|b$ and $a|c$, then $a | (b+c)$.
\begin{proof}
Let $a, b, c \in \ZZ$ and suppose $a|b$ and $a|c$.
By definition (of divides), there are integers $m$ and $n$ such that $am = b$ and $an=c$.
It follows that $b + c = am + an = a(m+n)$.
since $m+n$ is an integer, we see that $a|(b+c)$ (again by definition of divides).
\end{proof}
}


\prob{
Let $k, m, n \in \ZZ$.
Prove that if $k|m$ and $k|(m+n)$, then $k|n$.
}

\vfill

\newpage

\prob{
Let $a \in \ZZ$.
\begin{enumerate}[a)]

\item Prove that if $a$ is even, then $a^2$ is even.

\vfill

\item State the converse of the the statement in part a. Is the converse true or false?

\vspace{.5in}

\item Can you prove the converse?

\vspace{.5in}

\end{enumerate}
}

\prob{
Let $m, n \in \ZZ$.
Our goal is to prove that if either $m$ or $n$ is even, then $mn$ is even.\footnote{This should be easy, right?}

\begin{enumerate}[a)]

\item Write the contrapositive of the statement.
Note that the contrapositive has the same implicit quantifiers as the original statement.

\vspace{.5in}

\item Since any statement is logically equivalent to its contrapositive, proving either one suffices to prove both.
Which do you think will be easier?

\vspace{.5in}

\item Prove that if $m$ is even, then $mn$ is even.

\vfill

\item Is this enough to prove if either $m$ or $n$ is even, then $mn$ is even?

% \item[b) ] State the converse of ``if either $m$ or $n$ is even, then $mn$ is even''.
% Note that the converse has the same implicit quantifiers as the original statement.

% \vspace{.75in}

% \item[c) ] Is the converse true or false? (No need to prove it).

% \vspace{.75in}

% \item[d) ] It is also true that if $6|m$ or $6|n$, then $6|(mn)$.
% Is the converse of this statement true?
% Explain your reasoning.

% \vspace{2in}

\end{enumerate}
}

\chal{[write your solution on a separate sheet of paper]
Prove that if $n \in \NN$ and $n \geq 2$, then the numbers $n! + 2$, $n! + 3$, $n! + 4$, \dots, $n! + n$ are all composite.
(This means that $n! + 2$, $n! + 3$, $n! + 4$, \dots, $n! + n$ is a sequence of $n-1$ consecutive composite numbers, thus showing that there are arbitrarily large gaps between prime numbers).
}


%\prob{
%Prove that if two integers have the same parity (both odd or both even), then their sum is even.
%Hint: use cases.
%}

\end{document}