diff options
Diffstat (limited to 'gupta/hw4.tex')
| -rw-r--r-- | gupta/hw4.tex | 218 |
1 files changed, 218 insertions, 0 deletions
diff --git a/gupta/hw4.tex b/gupta/hw4.tex new file mode 100644 index 0000000..fe80e3f --- /dev/null +++ b/gupta/hw4.tex @@ -0,0 +1,218 @@ +\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 |