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

%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 6 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{5.8}
  Suppose $x\in\R$. If $x^5 - 4x^4 + 3x^3 - x^2 +3x - 4 \geq 0$, then $x\geq 0$.
\end{theorem*}
\begin{proof}
  We prove the contrapositive statement:
  \begin{equation*}
    \mbox{ If $x < 0$, then $x^5 - 4x^4 + 3x^3 - x^2 +3x - 4 < 0$.}
  \end{equation*}
  Assuming $x$ is negative, it follows that even powers of $x$ are positive and odd powers of $x$ are negative.
  In the given polynomial, even terms have negative coefficients and odd terms have positvie coefficients so that every term of the polynomial is negative.
  Therefore, the sum of all the terms is negative. That is, the polynomial $x^5 - 4x^4 + 3x^3 - x^2 +3x - 4 < 0$.
\end{proof}

\begin{theorem*}\label{5.12}
  Suppose $a\in\Z$. If $a^2$ is not divisible by 4, then $a$ is odd.
\end{theorem*}
\begin{proof}
  We prove the contrapositive statement: 
\begin{equation*}
  \mbox{ If $a$ is even, then $a^2$ is divisible by 4. }
\end{equation*}
  So let us assume $a$ is even. Then $a=2n$ for some integer $n$ and
  \begin{equation*}
    a^2 = (2n)^2 = 4n^2.
  \end{equation*}
  Therefore $a^2$ is divisible by 4.
\end{proof}

\begin{theorem*}\label{5.20}
  If $a\in\Z$ and $a \equiv 1 \pmod 5$, then $a^2 \equiv 1 \pmod 5$.
\end{theorem*}
\begin{proof}
  Here we procede by direct proof. Assume $a \equiv 1 \pmod 5$. By definition, this means that $5$ divides the difference $a-1$, and so $a-1 = 5n$ for some integer $n$.
  Thus $a = 5n +1$ and 
  \begin{equation*}
    a^2 = (5n + 1)^2 = 25n^2 + 10n + 1 = 5(5n^2 + 2n) +1.
  \end{equation*}
  Let $c$ equal the integer $5n^2 + 2n$. 
  We now have $a^2 = 5c +1$ and, equivalently, $a^2 - 1 = 5c$.
  Therefore, by definition, $a^2 \equiv 1 \pmod 5$.
\end{proof}

\begin{theorem*}\label{6.2}
  Suppose $n\in\Z$. If $n^2$ is odd, then $n$ is odd.
\end{theorem*}
\begin{proof}
  Assume, for the sake of contradiciton, that $n^2$ is odd and $n$ is even.
  Then $n=2a$ for some integer $a$ and
  \begin{equation*}
    n^2 = (2a)^2 = 4a^2 = 2(2a^2).
  \end{equation*}
  Since $2a^2$ is also an integer, this shows that $a^2$ is even, which contradicts our assumption.
\end{proof}

\begin{theorem*}\label{6.8}
  Suppose $a, b, c \in \Z$. If $a^2 + b^2 = c^2$, then $a$ or $b$ is even.
\end{theorem*}
\begin{proof}
  Assume, for the sake of contradiction, that $a^2 + b^2 = c^2$ and that $a$ and $b$ are both odd.
  Since the product of two odd integers is odd, it follows that $a^2$ and $b^2$ are both odd, and so $c^2 = a^2 + b^2$ is even.
  Again, since the product of two odd integers is odd, it must be that $c$ is even, for otherwise $c^2$ would be odd. 

  Now let us set $a = 2x +1$ and $b = 2y +1$ for some integers $x$ and $y$.
  We have
  \begin{align*}
  	c^2 &= a^2 + b^2 \\
  	  &= (2x + 1)^2 + (2y + 1)^2 \\
  	  &= 4(x^2 + y^2 + x + y) + 2.
  \end{align*}
  Setting $n$ equal to the integer $x^2 + y^2 + x + y$, this says that $c^2 = 4n + 2$. 
  In other words, $c^2 \equiv 2 \pmod 4$, and so $c^2$ is not divisible by $4$.
  From Chapter 5 Exercise 12 above, it follows that $c$ is odd, a contradiction.
\end{proof}

\begin{theorem*}\label{6.10}
  There exist no integers $a$ and $b$ for which $21a + 30b = 1$.
\end{theorem*}
\begin{proof}
  Assume, for the sake of contradiction, that $x$ and $y$ are integers such that
  \begin{equation*}
    21a + 30b = 1.
  \end{equation*}
  Then
  \begin{equation*}
    3(7a + 10b) =1,
  \end{equation*}
  and so 
  \begin{equation*}
    7a + 10b = \frac{1}{3}.
  \end{equation*}
  Since $7a + 10b$ is an integer and $1/3$ is not, this is a contradiction.
\end{proof}

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

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

\end{document}