\documentclass[12pt]{article}
\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate}
%\def\rmdefault{bch} % Use Charter for main text font.

% =========================================================
\begin{document}

\begin{center}
{\LARGE
\textbf{CS 173: Discrete Structures, Fall 2009}
\\
\textbf{Homework 3}
\\[1ex]}

This homework contains 4 problems worth a total of 40 points.
It is due on Friday, September 18th at noon.   Turn in your
homework in our new homework dropboxes, in the Siebel basement
corridor (just east of the big window lounge area).   The
boxes will be labelled:   put yours in the correct box for
your discussion section.

\end{center}

Notice that you must used the stated proof method in problems 3 and
4, even though that may not be the only way to prove the claims.
This is because the main point of these problems is to learn how to
use these proof techniques.

\bigskip\hrule

\begin{enumerate}

%----------------------------------------------------------------------
\item \textbf{[10 points] Thinking about GCD}

Consider the following two claims.   For each, determine
whether it's true or false.   Justify your answer with a
counter-example (if the claim is false) or an explanation in terms
of prime factors (if the claim is true).

\begin{enumerate}
\item For any positive integers $p$, $q$, and $r$, if
$\gcd(p,q) = 1$ and $\gcd(q,r) = 1$, then
$\gcd(p,r) = 1$.
\item For any positive integers $p$, $q$, and $r$, if
$\gcd(p,q) = 1$ and $\gcd(p,qr) = 1$, then
$\gcd(p,r) = 1$.
\end{enumerate}

Hint:  try putting in some concrete values for $p$, $q$, and $r$.
This may help you figure out whether each claim is true or false,
and get a start on understanding why.

%----------------------------------------------------------------------
\item \textbf{[10 points] Proof with divides}

Prove the following claim directly from the definition of ``divides''
(i.e. don't use facts about divides proved in class or the book).
A direct proof should work.

\begin{quote}
Claim: For any integers $p$, $q$, and $r$, $p$ non-zero,
if $p \mid 3q$ and $3q \mid r$, then $p \mid 3q + r$.
\end{quote}


%----------------------------------------------------------------------
\item \textbf{[10 points] Proof by contrapositive}

Consider the following claim:

\begin{quote}
Claim: For any integers m and n, if $7m + 5n = 147$, then
$m$ is odd or $n$ is odd.
\end{quote}

\begin{enumerate}
\item State the converse of the claim.

\item State the contrapositive of the claim.

\item Use proof by contrapositive to prove the claim.  
\end{enumerate}

\newpage
%----------------------------------------------------------------------
\item \textbf{[10 points] Proof by contradiction}

Consider the following claim:

\begin{quote}
Claim: $ \sqrt{2} + \sqrt{6} < \sqrt{15}$
\end{quote}

\begin{enumerate}
\item State the negation of the claim.

\item Use proof by contradiction to prove the claim.  
\end{enumerate}

%----------------------------------------------------------------------
\end{enumerate}
\end{document}

