path: root/gupta/hw4.tex

\newfam\bbold
\def\bb#1{{\fam\bbold #1}}
\font\bbten=msbm10
\font\bbsev=msbm7
\font\bbfiv=msbm5
\textfont\bbold=\bbten
\scriptfont\bbold=\bbsev
\scriptscriptfont\bbold=\bbfiv
\font\bigbf=cmbx12 at 24pt

\def\answer{\smallskip{\bf Answer.}\par}
\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt
depth 0pt{\parfillskip0pt\medskip}}
\let\endanswer\endproof
\def\section#1{\medskip\goodbreak\noindent{\bf #1}}
\let\impl\Rightarrow
\def\nmid{\not\hskip2.5pt\mid}

\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday
2022-02-03 at 11:59 pm}\hrule height .5pt}}

\centerline{\bigbf Homework 4 - Holden Rohrer}
\bigskip

\noindent{\bf Collaborators:} None

\section{Hammack 4: 26}

\item{26.} Prove the following with direct proof: every odd integer is a
difference of two squares.

\answer
Let $n$ be an odd integer.
We will show that there are two perfect squares $a^2$ and $b^2$ (with
$a,b\in\bb Z$) such that $n$ is their difference.

Because it is odd, there exists an integer $k$ such that $n = 2k+1.$
$$(k+1)^2-k^2 = k^2+2k+1-k^2 = 2k+1 = n,$$
so any odd integer can be written as the difference of two squares.
\endanswer

\section{Hammack 5: 6, 12, 18, 20, 24, 28}

\item{6.} Prove the following with contrapositive proof: suppose
$x\in\bb R.$ If $x^3-x>0,$ then $x>-1.$

\answer
For contrapositive proof, let $x \leq -1.$
We will prove that $x^3-x\leq 0.$

We obtain $x+1 \leq 0$ and $x-1 \leq -2.$
$$x(x-1)(x+1) \leq 0,$$
because the product of three non-positive numbers is non-positive.
% is this sufficient??
\endanswer

\item{12.} Prove the following with contrapositive proof: suppose
$a\in\bb Z.$ If $a^2$ is not divisible by 4, then $a$ is odd.

\answer
For contrapositive proof, let $a$ be not odd (even). We will show that
$a^2$ is divisible by 4.

By the definition of even, there exists $k$ such that $a = 2k.$
$a^2 = 4k^2,$ and $k^2\in\bb Z,$ so $a^2$ is divisible by 4.
\endanswer

\item{18.} Prove the following with either direct or contrapositive
proof: for any $a,b\in\bb Z,$ it follows that $(a+b)^3\equiv a^3+b^3
\pmod{3}$

\answer
Let $a,b\in\bb Z.$
We will prove that $(a+b)^3\equiv a^3+b^3\pmod{3}.$

$$(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3 = a^3 + b^3 + 3(a^2b+ab^2),$$
so $(a+b)^3\equiv a^3 + b^3 \pmod{3}$ by definition of modular
equivalence.
\endanswer

\item{20.} Prove the following with either direct or contrapositive
proof: if $a\in\bb Z$ and $a\equiv 1\pmod{5},$ then $a^2\equiv
1\pmod{5}.$

\answer
Let $a\in\bb Z$ and $a\equiv 1\pmod{5}.$
We will prove that $a^2\equiv 1\pmod{5}.$

There exists $k\in\bb Z$ such that $a = 5k+1.$
$$a^2 = (5k+1)^2 = 25k^2 + 10k + 1 = 5(5k^2+2k) + 1,$$
so $a^2 \equiv 1\pmod{5}.$
\endanswer

\item{24.} Prove the following with either direct or contrapositive
proof: if $a\equiv b \pmod{n}$ and $c\equiv d \pmod{n},$ then $ac\equiv
bd \pmod{n}.$

\answer
Let $a,b,c,d\in\bb R.$
Let $a\equiv b \pmod{n}$ and $c\equiv d \pmod{n}.$
We will show that $ac\equiv bd\pmod{n}.$

Therefore, there is $k\in\bb Z$ such that $a = b + nk,$ and there is
$j\in\bb Z$ such that $c = d + nj.$
$$ac = (b+nk)(d+nj) = bd + n(jb+dk+njk),$$
so $ac \equiv bd \pmod{n},$ because $jb+dk+njk\in\bb Z.$
\endanswer

\item{28.} Prove the following with either direct or contrapositive
proof: if $n\in\bb Z,$ then $4\nmid (n^2-3).$

\smallskip
{\bf Lemma.}
Let $n\in\bb Z.$ We will show that, for some $k\in\bb Z,$ $n^2 = 4k$ or
$n^2 = 4k+1.$
$n$ can be written as exactly one of $4j,$ $4j+1,$ $4j+2,$ and $4j+3,$
where $j\in\bb Z.$

In the first case $n = 4j,$ $n^2 = 16j^2 = 4(4j^2),$ so with $k=4j^2,$
$n^2 = 4k.$

In the second case $n = 4j+1,$ $n^2 = 16j^2 + 8j + 1 = 4(4j^2+2j) + 1,$
so with $k = 4j^2+2j,$ $n^2 = 4k + 1.$

In the third case $n = 4j+2,$ $n^2 = 16j^2 + 16j + 4 = 4(4j^2+4j+1),$ so
with $k = 4j^2+4j+1,$ $n^2 = 4k.$

In the fourth case $n = 4j+3,$ $n^2 = 16j^2 + 24j + 9 = 4(4j^2+6j+2)+1,$
so with $k = 4j^2+6j+2,$ $n^2 = 4k+1.$

All of these values of $k$ are integers by integer closure.

$n^2\neq 4k+2$ and $n^2\neq 4k+3$ for any integer $k$ because $n^2$ is
an integer and it can be written as exactly one of $4k,$ $4k+1,$ $4k+2,$
and $4k+3.$
\endproof

\answer
Let $n\in\bb Z.$
By the lemma, $n^2 = 4k$ or $n^2 = 4k+1.$
In the case $n^2 = 4k,$ $n^2 - 3 = 4k - 3 = 4(k-1) + 1,$
which is not divisible by $4.$
In the case $n^2 = 4k+1,$ $n^2 - 3 = 4k - 2 = 4(k-1) + 2,$
which is not divisible by $4.$
\endanswer

\section{Hammack 6: 4, 6, 8}

\item{4.} Prove the following by contradiction: $\sqrt 6$ is irrational.

\answer
For the sake of contradiction, assume that $\sqrt 6$ is rational.
Therefore, there exist coprime $p,q\in\bb Z$ such that $\sqrt 6 =
{p\over q}.$

$$p = q\sqrt 6 \to p^2 = 6q^2.$$
$p^2$ is even only if $p$ is even ($2\mid p$), so $4\mid p^2,$ so $2\mid
q^2,$ and thus $2\mid q.$
Therefore, $(q,p) = 2\neq 1,$ meaning they're not coprime.
\endanswer

\item{6.} Prove the following by contradiction: if $a,b\in\bb Z,$ then
$a^2-4b-2\neq 0.$

\answer
Let $a,b\in\bb Z,$ and for the sake of contradiction, let $a^2-4b-2 =
0.$
$$a^2-4b-2 \equiv 0 \equiv a^2-2 \to a^2 \equiv 2 \bmod{4}.$$
Therefore, there exists $k\in\bb Z$ such that $a^2 = 4k+2.$
By the lemma, $a^2 \neq 4k + 2.$
\endanswer

\item{8.} Prove the following by contradiction: suppose $a,b,c\in\bb Z.$
If $a^2+b^2=c^2,$ then $a$ or $b$ is even.

\answer
Let $a,b,c\in\bb Z$ such that $a^2+b^2=c^2.$
Suppose, for the sake of contradiction, $a$ and $b$ are odd.
There exists $j$ and $k$ such that $a=2k+1$ and $b=2j+1.$

Therefore, $a^2 + b^2 = (2k+1)^2 + (2j+1)^2 = 4k^2 + 4k + 1 + 4j^2 + 4j
+ 1 = 4(k^2+k+j^2+j) + 2 = c^2.$
By the lemma, $c^2 \neq 4k + 2.$
\endanswer

\section{Problems not from the textbok}

\item{1.} A perfect square is an integer $n$ for which there exists an
integer $k$ such that $n = k^2.$ Prove that if $n$ is a positive integer
such that $n\equiv 2\bmod 4$ or $n\equiv 3\bmod 4,$ then $n$ is not a
perfect square.

\answer
This has already been proven in the above lemma.
\endanswer

\item{2.} After a grueling slog through the snow to reach Ponce City
Market, you decide to reward yourself by buying three boxes of candy
from Collier’s. One box contains mint candies, one chocolate candies,
and the other is mixed. Unfortunately, all three boxes were incorrectly
labeled! What is the smallest number of candies that you need to remove
and sample to be able to correctly label all three boxes? Carefully
justify your reasoning.

\answer
We only need to sample one candy.
We sample the box labeled ``mixed,'' and without loss of generality we
get a chocolate candy. This is the chocolate box.
This box cannot be ``mixed'' because it is labeled incorrectly, and this
box cannot be ``mint'' because the mint box doesn't have chocolate
candy.
Now, the box labeled ``mint'' must be the mixed box because it cannot be
the chocolate box (we only have one of those) and it cannot be the mixed
box because it is incorrectly labeled.
By elimination, the last box is the mixed box.
\endanswer

\bye