\documentclass[12pt]{article}
\usepackage[margin=0.7in]{geometry}
% amsthm is new this week; it provides "theorem-like" structures.
\usepackage{amsmath,amsfonts,amssymb,amsthm}
% Here we define several "theorem-like" environments.
\newtheorem{proposition}{Proposition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{corollary}{Corollary}
\usepackage{fancyhdr}
% lastpage may not be part of your installation; it's a somewhat
% nonstandard package that determines the page number of the last page
% of your document, and allows you to refer to it with
% \pageref{LastPage}. If you don't have it, it can be worked around.
\usepackage{lastpage}
% Uncomment the following line and actually put your name into the
% second pair of braces. This will make LaTeX resolve \studentname
% throughout the document as whatever you put in the braces. Note that
% if you don't uncomment this line, your source will not compile!
\newcommand{\studentname}{}
\pagestyle{fancy}
\lhead{MATH 311-02}
\chead{Problem Set \#3}
% This next line will fail to compile unless you uncomment the
% \newcommand up above!
\rhead{\studentname}
\lfoot{}
% If you're not using lastpage, then comment this command out and use
% the simpler version which is commented out below.
\cfoot{Page \thepage\ of \pageref{LastPage}}
%\cfoot{Page \thepage}
\rfoot{\bf due February 18}
\begin{document}
\begin{enumerate}
\item \textbf{(15 points)} \emph{Below are two proofs relating to
divisibility of products.}
\begin{enumerate}
\item \textbf{(7 points)} \emph{Determine the sufficient (and if
possible necessary) conditions on an integer $n$ for the
following statement to be true: ``For integers $a$ and $b$, if
$n\nmid ab$, then $n\nmid a$ and $n\nmid b$.''. Then state the
condition on $n$ and the resulting impliccation as a proposition
and prove it.}
\begin{proposition}
Let $n$ be an integer. If $a$ and $b$ are integers such
that $n\nmid ab$, then $n\nmid a$ and $n\nmid b$.
\end{proposition}
\begin{proof}
We shall prove the contrapositive of this statement: if either
$n\mid a$ or $n\mid b$, then $n\mid ab$. We may thus take as our
premise the fact that $n\mid a$ or $n\mid b$. WLOG we may assume
that, specifically, $n\mid a$. Thus $a=kn$ for some integer $k$,
so $ab=knb=(kb)n$. Since $kb$ is an integer, it thus follows
that $n\mid ab$.
\end{proof}
\item \textbf{(8 points)} \emph{Determine the sufficient (and if
possible necessary) conditions on an integer $n$ for the
following statement to be true: ``For integers $a$ and $b$, if
$n\mid ab$, then either $n\mid a$ or $n\mid b$.''. Then state the
condition on $n$ and the resulting impliccation as a proposition
and prove it.}
As seen in class this is \emph{not} true when, for instance, $n=6$,
$a=$, and $b=3$. However, it is true as long as $n$ is not
divisible into smaller factors, i.e. if $n$ is prime.
\begin{proposition}
Let $n$ be a prime integer. If $a$ and $b$ are integers such
that $n\mid ab$, then $n\mid a$ or $n\mid b$.
\end{proposition}
\begin{proof}
Our premise is that $n\mid ab$; thus $ab=kn$ for some integer
$k$. Since these two products of integers are equal, there is a
recombination of factors to regroup a product of four factors
into each of the two products: that is, we may consider four
integers $p$, $q$, $r$, and $s$ such that $ab=pqrs=kn$ such that
$pq=a$ and $rs=b$, while $pr=k$ and $qs=n$. Since $qs=n$, it
follows that $q\mid n$; but since $n$ is prime, it follows that
$q$ is either $\pm 1$ or $q$ is $\pm n$.
\textbf{Case I: $q=\pm 1$.} Then since $qs=n$, $s=\pm n$, so
$b=rs=\pm rn$; since $r$ is an integer, $n\mid b$.
\textbf{Case II: $q=\pm n$.} Then $a=pq=\pm pn$; since $p$ is an
integer, $n\mid a$.
\end{proof}
\end{enumerate}
\item \textbf{(12 points)} \emph{In class we saw a proof that $\sqrt{2}$ is irrational. Here we will explore variations on it.}
\begin{enumerate}
\item \textbf{(8 points)} \emph{Modify the proof of $\sqrt2$'s
irrationality to produce a proof that for integer $n$, $\sqrt n$
is irrational if $n$ is not exactly the square of some
integer.}
This one is actually quite difficult. We start by considering $n$
as a product of a square and a factor free of squares:
i.e. $n=m^2r$, where no integer square other than 1 divides
$r$. Since $n$ is not exactly a square, $r>1$. We can now adapt a
lemma from the lecture:
\begin{lemma}
For an integer $n$ and integer $r$ such that no square other than
$1$ divides $r$, $r\mid n^2$ if and only if $r\mid n$.
\end{lemma}
\begin{proof}
The implication in one direction is easy: if $r\mid n$, then $n$ is
equal to $rk$ for some integer $k$, so $n^2=(rk)^2=r(rk^2)$, so
$n^2$ is also divisible by $r$.
In the opposite direction, however, we are given that $r\mid
n^2$. Since $r$ has no square factors, it is a product of distinct
primes $p_1p_2p_3\ldots p_\ell$. Thus $n\cdot n=p_1p_2\cdots p_\ell
k$ for some integer $k$. Since any two equal multiplications of
integers can be broken down into prime terms and recombined, then
there must be a decomposition of $n^2=abcd$ with $a$, $b$, $c$, and
$d$ positive integers such that $ab=n$, $cd=n$, $ac=p_1\cdots
p_\ell$, and $bd=k$. We shall specifically focus on the fact that
$ac=p_1\cdots p_\ell$: since each $p_i$ is prime, either $a$ or $c$
is divisible by each $p_i$, so since $ab=n$ and $cd=n$, it will
follow that each $p_i\mid n$, so $r\mid n$.
\end{proof}
We can then adapt the argument for $\sqrt 2$ almost exactly:
\begin{theorem}
For an integer $n$ not a perfect square, the square root of $n$
is irrational.
\end{theorem}
\begin{proof}
The statement could be rephrased as an explicit implication: if
$x^2=n$, then $x$ is irrational. Let us proceed by
contradiction, and take as our premise the statement that
$x^2=n$ and $x$ is not irrational (i.e., $x$ is rational). We
may determine integers $m$ and $r$ such that $n=m^2r$, where no
integer square other than 1 divides $r$; since $n$ is not a
perfect square, $r>1$. Then, by the definition of a rational
number, $x$ may be expressed as a fraction $\frac pq$ in lowest
terms; that is, $x=\frac pq$ where $p$ and $q$ are integers
sharing no divisors greater than 1. Since $m^2r=x^2=\left(\frac
pq\right)^2=\frac{p^2}{q^2}$, we may see that
$p^2=rm^2q^2$. Thus $r\mid p^2$, and from the above lemma $r\mid
p$; let $p=rk$. Then $(rk)^2=rm^2q^2$, which simplifies
algebraically to $rk^2=m^2q^2$. Thus $r\mid q^2$, so $r\mid
p$. However, since both $p$ and $q$ are divisible by $r$, our
presumption that $\frac pq$ is in lowest terms is directly
contradicted.
\end{proof}
\item \textbf{(4 points)} \emph{Explain why this proof couldn't be
modified to prove that $\sqrt 4$ is irrational. Don't merely
point out that $\sqrt 4$ is rational; exhibit why the specific
proof of the irrationality of $\sqrt 2$ doesn't work when the 2
is replaced with a 4.}
The original proof does not yield an easy adaptation because the
assertion ``$4\mid n^2$ if and only if $4\mid n$'' is not true in
general (e.g. for $n=6$), and could not replace the similar
assertion about the number 2 (which \emph{is} true) in the
original proof. If we tried to run 4 through our proof above, we
would get that $r=1$, which would not present a problem until the
end, where the assertion that both $p$ and $q$ are divisible by
$r$ would not contradict our assertion that $\frac pq$ was in
lowest terms.
\end{enumerate}
\item \textbf{(7 points)} \emph{Let $a,b\in\mathbb Z$. Prove that if
$a^2+2b^2\equiv 0\pmod{3}$, then either $a$ and $b$ are both
congruent to zero modulo 3 or neither is congruent to zero modulo
3.}
\begin{proof}
We shall prove the contrapositive: if $a$ and $b$ are \emph{not}
either both congurent to zero or both noncongruent to zero, then
$a^2+2b^2\not\equiv 0\pmod 3$. Thus, one is congruent to zero and
the other is not congruent to zero. Which one is which is not
given, so we proceed with a casewise analysis:
\textbf{Case I: $a\equiv 0\pmod 3$ and $b\not\equiv 0\pmod 3$.}
Alternatively, $3\mid a$ and $3\nmid b$. Using the lemma from the
previous question (or an arbitrary-prime version of the one used
in class), we can see $3\mid a^2$ and $3\nmid b^2$; furthermore,
since $2$ is prime and not a divisor of 3, we can see that $3\nmid
2b^2$. Thus $a^2\equiv 0\pmod 3$ and $2b^2\not\equiv 0\pmod 3$, so
by additivity of modular arithmetic, we can see that
$a^2+2b^2\not\equiv 0\pmod 3$.
\textbf{Case I: $a\not\equiv 0\pmod 3$ and $b\equiv 0\pmod 3$.}
Alternatively, $3\nmid a$ and $3\mid b$. Using the lemma from the
previous question (or an arbitrary-prime version of the one used
in class), we can see $3\nmid a^2$ and $3\mid b^2$; furthermore,
we can see easily that $3\mid 2b^2$. Thus $a^2\not\equiv 0\pmod 3$
and $2b^2\equiv 0\pmod 3$, so by additivity of modular arithmetic,
we can see that $a^2+2b^2\not\equiv 0\pmod 3$.
\end{proof}
\item \textbf{(6 points)} \emph{Let $A$, $B$, and $C$ be sets. Prove
that $(A-B)\cup(A-C)=A-(B\cap C)$.}
\begin{proof}
We shall first prove that $(A-B)\cup(A-C)\subseteq A-(B\cap
C)$. Consider $x\in(A-B)\cup(A-C)$. By the definition of a union,
we know that either $x\in A-B$ or $x\in A-C$. We shall analyze
each case:
\textbf{Case I: $x\in A-B$.} Then $x\in A$ and $x\notin B$. Since
$x\notin B$, it follows that $x\notin B\cap C$. Thus, since $x\in
A$ and $x\notin B\cap C$, we can conclude that $x\in A-(B\cap
C)$.
\textbf{Case II: $x\in A-C$.} Then $x\in A$ and $x\notin C$. Since
$x\notin C$, it follows that $x\notin B\cap C$. Thus, since $x\in
A$ and $x\notin B\cap C$, we can conclude that $x\in A-(B\cap
C)$.
Since an arbitrary element of $(A-B)\cup(A-C)$ has been shown to
be in $A-(B\cap C)$, we may conclude that $(A-B)\cup(A-C)\subseteq
A-(B\cap C)$.
Now let us prove that $A-(B\cap
C)\subseteq(A-B)\cup(A-C)$. Consider $y\in A-(B\cap C)$. Thus
$y\in A$ but $y\notin B\cap C$. In order for $y$ to not be an
element of $B\cap C$, it must fail to be an element of either $B$
or $C$. We can investigate both possibilities casewise:
\textbf{Case I: $y\notin B$.} Then, together with the previously
seen fact that $y\in A$, we may conclude that $y\in (A-B)$, and
thus $y\in(A-B)\cup(A-C)$.
\textbf{Case I: $y\notin C$.} Then, together with the previously
seen fact that $y\in A$, we may conclude that $y\in(A-C)$, and
thus $y\in(A-B)\cup(A-C)$.
\end{proof}
\item \textbf{(4 point bonus)} \emph{Prove (possibly following the
structure of the similar proof in class) that if every two
vertices of a regular 17-sided polygon are joined with segments
colored red, green, or blue, then regardless of how the segments
are colored, some three vertices are joined by three edges of the
same color.}
\begin{proof}
Let us pick an arbitrary vertex of our 17-gon, and label it $x$;
now let us consider the 16 segments emenating from this vertex to
every other vertex of the polygon; each segment has been colored
red, green, or blue. Of the three colors, it is impossible that
they all appear 5 or fewer times among these 16 segments; that
could only color 15 segments. Thus, 6 of these segments with one
endpoint at $x$ must be the same color; WLOG we can presume that
color is red. Let us then name these six red segments' other
endpoints $y_1,y_2,y_3,y_4,y_5,y_6$.
There are two cases to be dealt with as we inspect the edges among
the vertices $y_1,\ldots,y_6$; either the color red is present
among these edges or it is not.
\textbf{Case I: the segment between some $y_i$ and $y_j$ is red.}
Then $x$, $y_i$, and $y_j$ are mutually connected by red segments.
\textbf{Case II: all of the segments among $y_1,\ldots,y_6$ are
blue or green.} Then we are drawing segments among 6 points in
two colors; by the result seen in class, a monochromatic triangle
must be produced.
\end{proof}
The field from which this question (and the 6-vertex example given
in class) are drawn is called \emph{Ramsey Theory}, which deals with
the monochromatic substructures which must arise when a large
structure is colored.
\end{enumerate}
\vfill
\begin{center}
\fbox{
\begin{minipage}{6in}
Die ganzen Zahlen hat der liebe Gott gemacht; alles andere ist
Menschenwerk. [The good Lord created the natural numbers; all
else is the work of man.]
\hfill ---attributed~to~Leopold~Kronecker
\end{minipage}
}
\end{center}
\end{document}